12个相同小球分成3个相同组的合法分法计数问题求助
12个相同小球分成3个相同组的合法分法计数问题求助
我现在在解决这个问题:把12个相同的小球分成3个相同的组,每个组至少1个球,最多6个球。我的思路是先假设组是不同的,然后再调整到相同组的情况,现在卡在调整的步骤了,想请大家帮忙看看!
我的尝试过程是这样的:
- 首先,因为每个组至少要有1个球,所以先给每个组分配1个球,这样剩下的小球数量就是12-3=9个,问题转化为把9个相同的球分到3个不同的组(此时每组可以是0个及以上),对应的方程是
x+y+z=9。 - 根据隔板法,这种分配方式的总数是
C(11,2)=55种(也就是${11 \choose 2}=55$)。 - 接下来要排除掉那些有组超过6个球的情况(原问题要求每组最多6个,加上一开始给的1个,所以分配剩下的球时,某个组最多能加5个,也就是如果某个组加了6个及以上,总球数就会超过6)。
- 计算违规的情况:先选1个组,有
C(3,1)种选法,给这个组额外加6个球(这样这个组的总球数就变成1+6=7,违反了最多6个的限制),剩下的球数是9-6=3个,这3个球再分给3个组的方式是C(5,2)=10种。所以违规的总共有3*10=30种。 - 减去违规情况后,得到符合条件的不同组的分法是55-30=25种。
到这里我就卡住了,因为我最开始假设组是不同的,但实际问题里组是相同的,所以需要把这25种不同组的分法转换成相同组的情况。我手动数出来相同组的合法分法有6种,分别是:
- 6,5,1
- 6,4,2
- 6,3,3
- 5,5,2
- 4,4,4
现在想请教大家,怎么从这25种不同组的分法中调整得到6种相同组的分法?也就是我该怎么减去那些重复的情况呢?
备注:内容来源于stack exchange,提问作者Vasu Gupta




