水果的划分问题

mathe

Burnside's Lemma还是比价容易理解的，其中
$|X/G|=1/|G|\sum_{g \in G}X^g$
这里X是一个集合比如这里X就可以选择为将水果划分成k个不同的堆的所有方案。
而我们需要计算不区分不同的堆的方案数目，也就是通过置换不同的堆能够相互得到的结果认为是相同的。
所以我们这里可以选择群G为各个堆之间的置换，而k个堆的所有置换构成的群是置换群$S_k$。
而记号X/G就是指将通过G中元素能够相互变换的X中元素看成相同的以后的集合。而集合$X^g$指的是X中变换g的不变元，就是${x \in X| g(x)=x}$

mathe

同样如果我们要分析四堆的情况，那么这是$G=S_4$.我们首先要分析$S_4$中各种置换，其中恒等变换I一个(保持不变)，然后交换两个堆的置换$C_4^2=6$个，比如$(12)$(也就是交换第一第二堆，余下两个堆不变），两两交换的${C_4^2}/2=3$个，比如$(12)(34)$(也就是交换第一第二堆并且交换第三第四堆)。交换三个堆的置换有$2!*C_4^3=8$个，比如$(123)$(也就四第一个堆变成第二个堆，第二个变第三个，第三个变第一个).而四个堆轮换的有$3! =6$个。
其中I等价于方程组
${(x_1+x_2+x_3+x_4=10),(y_1+y_2+y_3+y_4=11),(z_1+z_2+z_3+z_4=12),(w_1+w_2+w_3+w_4=13):}$的解的数目，所以是$C_{10+4-1}^{4-1}C_{11+4-1}^{4-1}C_{12+4-1}^{4-1}C_{13+4-1}^{4-1}=26525699200$
$(12)$的不变元数目等价于方程组
${(2x_1+x_3+x_4=10),(2y_1+y_3+y_4=11),(2z_1+z_3+z_4=12),(2w_1+w_3+w_4=13):}$的解的数目,
分别计算得出数目为36*42*49*56=4148928
而$(12)(34)$的不变元等价于方程组
${(2x_1+2x_3=10),(2y_1+2y_3=11),(2z_1+2z_3=12),(2w_1+2w_3=13):}$的解的数目，显然无解，结果为0.
而$(123)$的不变元等价于方程组
${(3x_1+x_4=10),(3y_1+y_4=11),(3z_1+z_4=12),(3w_1+w_4=13):}$的解的数目，显然为4*4*5*5=400
而$(1234)$不变元显然也无解，数目为0.
所以总结果为$(1*26525699200+6*4148928+3*0+8*400+6*0)/24=1106274832$
同样如果不允许空堆需要扣除8199072结果为1098075760

mathe

可否给出一般化的公式呢
假如有n种水果, 每种水果分别有p1,p2,p3, ...pn 个.
求分成m个非空的小堆 的方案数目
wayne 发表于 2012-9-16 09:12

写成通用公式样子比较困难，但是通过分解$S_m$的各种分类，我们就可以通过计算机来计算了。复杂度不是很大，但是比较难给出定量的分析