水果的划分问题

wayne

这里有一堆水果, 10个苹果,11个橘子,12个香蕉,13个葡萄,
把这么多水果 掺杂在一块, 分成2小堆 有多少种方法,
分成3小堆,
4小堆呢?
(不能为空)

KeyTo9_Fans

假设苹果、橘子、香蕉和葡萄都是一样的，

分成的$2$堆也不区分第$1$堆还是第$2$堆，

并且某堆可以为空，

那么一共有$(11*12*13*14)/2=12012$种分法。

wayne

2# KeyTo9_Fans

不能为空， 如果2堆可以为空，就不是2堆，而是一堆了

mathe

能否可以包含空堆不重要。比如这里就差一个结果。
如果可以包含空堆的解为S(k) (k堆),不可以包含空堆的解为T(k),那么T(k)=S(k)-S(k-1).
所以我们可以仅考虑包含空堆的情况。而首先可以分析区分不同堆的情况的数目，然后利用枚举定理可以算出不区分堆的情况的数目

mathe

对于区分不同堆的情况，相当于计算一些方程组的解的数目，比如这里分三堆，就变成方程组
x1+x2+x3=10
y1+y2+y3=11
z1+z2+z3=12
w1+w2+w3=13
的解的数目（然后计算各个方程解的数目用乘法原理相乘即可）
而为了利用枚举定理，我们还需要计算在某些变换下的不变量的数目，比如交换第一和第二堆不变换的解的数目，也就是x1=x2,y1=y2,z1=z2,w1=w2下解的数目，很容易计数

mathe

原来是Burnside's Lemma即可

mathe

比如三堆的情况，由于置换三堆后相同的结果我们认为是等价的。所以我们需要分析置换群G=S3
根据Burnside's Lemma,我们需要计算对于G中各元素下不变量的数目
由于所有结果都是恒等变换的不变量，所以对于恒等元，不变量数目就是5#中方程解的数目，其中
比如x1+x2+x3=10(xi>=0)的解的数目为$C_12^2$,同理算出另外三组方程，所以总数目为
$C_12^2C_13^2C_14^2C_15^2$
而S3中置换两个元素的变换有3个，它们相互都类似，我们只用讨论置换前两堆的情况，那么就对应方程
2x1+x3=10,2y1+y3=11等，解的数目分别为6,6,7,7,所以总数目为6*6*7*7
此外S3中还有轮换3个元素的变换，对应方程3x1=10等，必然无解，也就是数目为0.
所以最后我们得到结果为1/6(1*C_12^2C_13^2C_14^2C_15^2+3*6*6*7*7+2*0)=8199072
当然这个包含了2楼中的情况，如果我们要求三堆都不空，就要再减去2楼中数目

wayne

可否给出一般化的公式呢
假如有n种水果, 每种水果分别有p1,p2,p3, ...pn 个.
求分成m个非空的小堆 的方案数目

wayne

此题我们可以等价成:
将 一个整数分解成多个因子的无序的乘积的形式,  共有多少种方法.

wayne

2堆,非空, 答案应该是  Ceil [(1+p1)(1+p2)...(1+pn)/2] -1