排列组合典型问题-分球入盒

排列组合典型问题-分球入盒（精选2篇）

排列组合典型问题-分球入盒 篇1

高二数学组 朱育璋

分球入盒问题（球在盒子的分布情况）是概率中常见的一类题型，如：

(1)生日问题：n个人的生日的可能情况（每个人生日是365天之一），相当于n个球放入N=365个盒子中的可能情况(设一年365天)；

（2）书籍分堆问题：6本画册分给3份，每份至少一本

（3）名额分配问题：7个参赛名额分给不同班级

（4）有n封信随机的投放在N个信筒中（筒内信数不限）；

此类问题具有背景丰富，应用广泛等特点。本文旨在总结解此类题的规律，理清思路，以便更好的更快的求解问题。

例题分析

【例1】 按下列要求分配6个不同的小球，各有多少种不同的分配方式？

(1)分成三份，1份1个，1份2个，1份3个；

(2)甲、乙、丙三人中，一人得1个，一人得2个，一人得3个；

分析：（1）为典型无序分组问题，可分三步完成，即拿出一个做第一份，拿出2个做第二份，拿出3个做第三份，完成分组，对于（2）为有序分组问题，可采取先按（1）分组，再进行分配，即排列。

归纳：从1,2问区分分组要求与分配要求，并掌握基本方法。另外，举出类似问题，一起归结为：不同小球投入相同的盒子，不同小球投入不同的盒子

(3)分成三份，1份4个，另外两份每份1个；

(4)甲、乙、丙三人中，一人得4个，另外两人每人得1个；

分析：（3）与（1）问题类型相同，同为分组要求，不同的地方：出现两份小球数目一样，即有均分组，此时按原方法计算会导致重复计算，举例：不妨记6个球为A、B、C、D、E、F，若第一步取了ABCD，第二步取了E，第三步取了F，记该种分法为(ABCD，E,F)，则同样分法中还有(ABCD,F,E)，共2种情况，而这2种情况仅是E，F的顺序

22不同，从排列角度易算出不同的分法为A2，需在原基础上除以A2，消去顺序。

归纳：在分组中出现均分组情况，需要消序，即除以均分组的组数全排列数

【例2】 按下列要求分配6个相同的小球，各有多少种不同的分配方式？

(1)分成三份，1份1个，1份2个，1份3个；

(2)甲、乙、丙三人中，一人得1个，一人得2个，一人得3个；

一.（1）通过穷举的办法算出结果，认识到分法差异在于各组小球数量的相对性

二.（2）分法差异在于不同的小组小球的数量，方法：先定数量分配，再分配入盒。归纳：

1.球不同，盒子同（分组问题）

方法：典型组合问题，首先明确各组小球的数量，然后逐步算出每一组的组合方式，再相乘。注意：平均分组时，需消序，即除以均分组的个数的全排列数

2.球不同，盒子不同（分配问题）

方法：先组合后排列，首先按1类型算出分组方法，然后将各组整体视为单个元素，再进行排列。

特别地：当每个盒子不限小球的个数时，可让每一个小球依

次选择盒子，各小球的选择方法有b种，总数 ba〃

3.球同，盒子不同（分法的差异：不同盒子所装小球的数量）

穷举法：

隔板法：将a个小球排成一列，小球间形成a-1个空位，从中选择b-1个空位插入隔板，等价于将元素分成b份。

注意;该法要求每个盒子至少有一个小球，不允许空盒

4.球同，盒子同（分法的差异：各盒子所装小球数量的相对性）

穷举法：即把每一个分法详细写出来。

分球入盒问题思考方式

1.如何辨认何种考题属于此题型？

特征：考察对象有两个，一个是待分配的，另一个对象具有容纳功能，常见问题：信件投信箱，多人人选房子住宿，赠书给人

2.辨别哪个是小球，哪个是盒子。

盒子：具有容纳的功能

3.辨别小球（盒子）同还是不同，确定问题的具体类型，准确选择方法。

排列组合典型问题-分球入盒 篇2

“分球入盒”问题是概率论中一种重要的古典概型。实际问题中的投信、分配、住宿、不定方程的求解问题都与“分球入盒”问题具有相通之处。根据球是否可辨、盒是否可辨，“分球入盒”问题又可分为不同类型，如果能对其进行正确归类，并逐个进行研究和比对分析，将会使学生对这类问题有清楚的认识，不致于产生混淆。针对不同的类型，要用到不同的分析方法，如隔板法、列举法等，有些方法稍嫌牵强甚至颇难理解。为此，本文试图以较浅显通俗的语言介绍重复排列、重复组合、第二类Stirling数等组合数学中的概念和公式，并将它们与不同类型的“分球入盒”问题一一对应起来，通过这些搭建起来的桥梁与对应关系，解决“分球入盒”问题时变得有章可循。同时，对于(广义)第二类Stirling数的计算，给出了递推公式，只要编写简单的程序即可完成。针对不同情形的“分球入盒”问题，我们精选了一些典型例子，利用对应的排列组合公式就可得到圆满解决。

1重复排列数与球、盒均可辨时的“分球入盒”问题

定义1[1]从n个不同元素中每次取出一个，放回后再取下一个，如此连续取r次所得到的排列，称为重复排列，其重复排列数为nr个。

由乘法原理可知，下面的球、盒均可辨时的“分球入盒”问题正好与重复排列数相对应。

模型1：将r个不同(即可辨)的球随机放入n个不同盒子中去，则分配方法共nr种。

例1某城市共有N辆汽车，车牌号码从1到N，有一人将他所遇到的n辆汽车的车牌号码(可能有重复的号码)全部抄下来，假设每辆汽车被遇到的机会相同，求他抄到的最大号码恰好是k(1

解：这个人抄到的每一个车牌号码都是1到N中的任一个，所抄到的n个号码有可能是重复的，由重复排列数可知，这n个号码的所有可能情况有Nn种。

在所抄到的n个号码中最大号码不大于k，只须从1到k个号码中有重复地抄到n个即可，共有kn种可能，同理，在所抄到的n个号码中最大号码不大于k-1的取法共(k-1)n种，因此他抄到的最大号码恰好是k的取法,共kn-(k-1)n种，从而所求的概率为

2重复组合数与球不可辨时的“分球入盒”问题

定义2[1]从n个不同元素中每次取出一个，放回后再取下一个，如此连续取r次所得到的组合，称为重复组合，其重复组合数记为Hnr。

重复组合数中取出的r个元素具有这样的特点：(1)这r个元素可重复;(2)r个元素之间不考虑次序，即不关心每个元素是在第几次被抽到的，而只关注其号码。陈信[2]的引理1对Hnr的计算给出了简洁而绝妙的证明，在此引用如下：

命题1[2]从集合Ω={1,2,…,n}中任取r个元素的每一种可重复组合都对应着从Ω={1,2,…,n+r-1}中任取r个元素的一种不重复组合，即有

模型2：将r个完全相同(即不可辨)的球随机放入n个不同的盒子中去，考虑有多少种分配方法。

此模型相当于从n个有不同编号的盒子中有放回地选取r个盒子，由于r个球完全相同，所以只须在选出的r个盒子中各放1个球即可，而不必考虑这r个盒子的次序，因为每个盒子放入哪个球都是一样的。此处选出的这r个盒子的编号也要满足两个条件：(1)r个编号可重复;(2)r个编号不讲次序。因此，模型2中的分球入盒的方法有Hnr=Crn+r-1个。

例2设方程x1+x2+x3+x4=32，试在下列三种情况下分别求它的整数解个数：(1)xi>0,10,15,x3,x4>7.

解：将这3种情况下方程的整数解个数的问题分别可以看成：

(1)将32个相同的球随机放入4个盒中的分法，故此时方程的整数解

(2)先让4个盒子中每盒各放1个球，再让其余的28个相同的球随机放入这4个盒子中的分法，则此时方程的整数解个数为

(3)先让前两个盒中各放5个球，后两个盒各放7个球，再将其余8个相同的球随机放入4个盒中，故此时方程的整数解个数为

像这样巧妙利用“分球入盒”的例子还有很多，如求多项式(x1+x2+…+xm)n的展开式中有多少项，由于每项都形如，其中n1+n2+…+nm=n,n1,n2,…,nm均为非负整数，可以设想将n个相同的球随机放入m个不同的盒子中去，展开式中每一项都对应着一种这样的分球入盒方法，故展开式中的项数共Hmn=Cnm+n-1项。

3（广义）第二类Stirling数与盒不可辨时的“分球入盒”问题

定义3[3]含有r个不同元素的一个集合恰好分成n个非空子集合的分拆数目称为第二类Stirling数，记作或S2(r,n)，并规定S2(0,0)以及r

定义4[3]含有r个不同元素的一个集合恰好分成n个至少都含有t(t>2)个元素的子集合的分拆数目称为广义第二类Stirling数，记作St+1(r,n)，并规定St+1(0,0)=0以及r

下面只讨论第二类Stirling数S2(r,n)与t=2时的广义第二类Stirling数S3(r,n)在“分球入盒”问题中的应用。

模型3：考虑将r个不同的球随机放入n个完全相同(不可辨)的盒中去的分法，(1)若要求每盒不空，则分法恰为S2(r,n);若要求每盒至少有2个球，则分法恰为S3(r,n)。

例3根据定义求S2(6,3)、S3(2r,r)(其中r≥1)的值。

解：由，将6个不同的元素拆分成3组，且各组不讲次序，这样的分拆数恰为S2(6,3)=

将2r个不同的元素拆分成r组，且每组至少有

2个元素，则只能拆分成，这样的拆分

为给出以下递推公式，先给出几个特殊值。对正整数r都有S2(r,1)=1,S2(r,r)=1;对大于2的正整数r都有S3(r,1)1,S 3(2r,r)

命题2[4]当r>n>1时第二类Stirling数满足

命题3当n>2,r>2n+1时，广义第二类Stirling数满足

证明：根据模型3可设S3(r,n)表示将编号为1,2,…,r的r个球随机放入n个相同的盒中去(且每盒至少有2个球)的分法，这样分球可分为以下两种情况：

(1)1号球所在的盒中除1号球之外仅有其它的一个球，为此可先从除1号球之外的r-1个球中任选1个放入1号球所在的盒子，再让剩下的r-2个不同的球随机放入其余的n-1个盒中去(且每盒至少有2个球)，故第(1)种情况含(r-1)·S3(r-2,n-1)种分法;

(2)1号球所在的盒中除1号球之外至少还有其它2个球，为此可先将1号球之外的r-1个不同的球放入n个相同的盒中(且每盒至少有2个球)，再将1号球放入任一个盒子中，故第(2)种情况含n·S3(r-1,n)种分法。

根据加法原理，可得S3(r,n)=(r-1)·S3(r-2,n-1)+n·S3(r-1,n)。命题得证。

利用公式(2)、(3)可求S2(r,n)、S3(r,n)，利用编程可更快得到它们的值。如可轻松求得S2(15,8)=216627840,S2(30,12)=1439467883,S3(11,4)=56980,S3(17,6)=190807236。

例4把8个人随机分成3个小组，执行同一种任务，在下面3种情况下，分别求事件A=“其中一组有2人，另两组各有3人”的概率：

(1)分组时要求每个小组至少1人;(2)分组时允许某个小组没人;(3)分组时要求每个小组至少2人。

解：由于事件A中包含3人的这两个组不分次序,所以A包含种分法,把题中三种情况对应的样本空间分别记为Ω1,Ω2,Ω3。

(1)Ω1包含的样本点数恰为S2(8,3)=966，故P1(A)=2809662069=;

(2)Ω2包括3类：将8个人分成3个小组(不空)，或分成2个小组(不空)，或分成1个小组(不空)，故P2(A)=

(3)Ω3包含的样本点数恰为S3(8,3)=490，故

例5将编号为1,2，…，r的r个球随机放入n(n>1,r≥2n+1)个形状一样(不可辨)的盒子中(且每盒至少有2个球)，求事件A=“1,2号球同在一盒”的概率。

解：将r个不同的球随机放入n个不可辨的盒子中(且每盒至少2个球)的分法共S3(r,n)个，事件包括以下两种情况：

(1)1、2号球所在的盒不再含有其它球，这意味着只须将其余r-2个不同的球放入其它n-1个相同的盒子中(且每盒至少2个球)，这样的分法共S3(r-2,n-1)个;

(2)1、2号球所在的盒中还含有其它球，则只须将1号球之外的r-1个不同的球放入n个相同的盒子中(且每盒至少2个球)，再将1号球放入2号球所在的盒中即可，这样的分法共S3(r-1,n)个。

通过以上分类讨论可以发现：实际中有不少类似的例子可以巧妙地转化为“分球入盒”问题。在处理时关键要先区分好哪个为球、哪个为盒，再根据球、盒是否可辨，分配方法是否讲先后次序，来相应选取适当的排列组合公式，使问题得到解决。

参考文献

[1]茆诗松,程依明,濮晓龙.概率论与数理统计教程[M].北京:高等教育出版社,2004:12～13.

[2]陈信.可重复组合与应用[J].甘肃高师学报,2003,8(2):14～16.

[3]吴跃生.第二类Stirling数S2(n,n-k)的一个公式[J].华东交通大学学报,2009,26(3):95～97.