n个数分成m组，有多少种方法。的多种情况的解法

2017-04-28 10:50阅读：

http://blog.sina.cn/dpool/blog/u/2536920992

上述有多种情况
1 n 个数完全相同，即无差别，分成m组且每组不为空
2 n 个数完全相同，即无差别，分成m组，组可为空
3 n 个数不同，分成m组且每组不为空
4 n 个数不同，分成m组，每组可为空（不考虑了）

下面解答
情况一 ：n 个数完全相同，即无差别，分成m组且每组不为空 (下面的算法是组是有区别的的例三个人分成两组那么1,2 和 2,1 是两组。)
解答：可采用插空法
将N个数排成一列，那么这列数有N-1个空隙，从N-1个空隙中选出m-1个隔板
C(N-1,m-1)=（N-1）！/(m-1)!
例子：：将20个优秀学生名额分给18个班，每班至少1个名额，有多少种不同的分配方法？

分析：本题是名额分配问题，用隔板法.
解析：将20个名额分配给18个班，每班至少1个名额，相当于将20个相同的小球分成18组，每组至少1个，将20个相同的小球分成18组，需要17块隔板，先将20个小球排成一排，因小球相同，故小球之间无顺序，是组合，只有1种排法，再在20个小球之间的19个空档中，选取17个位置放隔板，因隔板无差别，故隔板之间无序，是组合问题，故隔板有C19 17种不同的放法，根据分步计数原理，共有C(19,17)种不同的方法，因17块隔板将20个小球分成18组，从左到右可以看成每班所得的名额数，每一种隔板与小球的排法对应于一种分法，故有C(m-1,n-1)种分法.(这里优秀学生名额也是无差别的。
情况二： n 个数完全相同，即无差别，分成m组，组可为空
举个例子： from： http://www.mamicode.com/info-detail-227656.html
（上下楼梯的题目也是这种解法）
将20个大小形状完全相同的小球放入3个不同的盒子，允许有盒子为空，但球必须放完，有多少种不同的方法？
分析：本题中的小球大小形状完全相同，故这些小球没有区别，问题等价于将小球分成三组，允许有若干组无元素，用隔板法.
解析：将20个小球分成三组需要两块隔板，因为允许有盒子为空，不符合隔板法的原理，那就人为的再加上3个小球，保证每个盒子都至少分到一个小球，那就符合隔板法的要求了（分完后，再在每组中各去掉一个小球，即满足了题设的要求）。然后就变成待分小球总数为23个，球中间有22个空档，需要在这22个空档里加入2个隔板来分隔为3份，共有C（22，2）=231种不同的方法.
点评：对n件相同物品（或名额）分给m个人（或位置），允许若干个人（或位置）为空的问题,可以看成将这n件物品分成m组，允许若干组为空的问题.将n件物品分成m组，需要m-1块隔板，将这n件物品和m-1块隔板排成一排，占n+m-1位置，从这n+m-1个位置中选m-1个位置放隔板，因隔板无差别，故隔板之间无序，是组合问题，故隔板有C(n+m-1, m-1)种不同的方法，再将物品放入其余位置，因物品相同无差别，故物品之间无顺序，是组合问题，只有1种放法，根据分步计数原理，共有C(n+m-1,m-1)×1=C(n+m-1,m-1)种排法.
情况三： n 个数不同，分成m组且每组不为空（string number）
将n个元素，分成 m 个非空子集，不同的分配方法种数，称为斯特林数（Stirling Number），记为 S(n,m)
下面图片公式不能加载的话网址：http://baike.baidu.com/link?url=l9_HlTpzmebizwExB9xbNEOWv-E8lDdvDXmlAO7lOqs1cMILdysNEFIR80zsLJBhm1IkiWVU64HGN6o3Im3AXkaH0pLMWWHHI-Vm8tNEoCfqxmGk3s-p1goQwrT-zOEk （我在百科上找的）
无符号第一类Stirling数的递推式可以从其定义来推导：
考虑其定义如果要将n+1元素构成m个圆排列，考虑第n+1个元素：
（1）如果n个元素构成了m-1个圆排列，那么第n+1个元素独自构成一个圆排列。方案数：