球与盒子的排列组合问题.docx

球与盒子的摆列组合问题（精髓版） 第一看一下分类，主要有 8种： 1）球 同，盒 同，无 空箱 2）球 同，盒 同，同意空箱 3）球 同，盒不一样，无 空箱 球同，盒不一样，同意空箱 球不一样，盒相同，无空箱 6）球不一样，盒相同，同意空箱 7)球不一样，盒不一样，无空箱 8）球不一样，盒不一样，同意空箱 做这类题型重点是要对号入坐，下边的解说剖析一致假定m个球，n个盒子。 m 先从最简单下手，第8种，每个球都有n种选择，因此是n 剩下的我们先以前四种（数字都不会太大，且剖析较简单）开始。 做题时一看到球同，盒同，就想到充数法，事实证明这是最快的一种方法。 如第（1）种，假定m=7，n=4.它的状况只有1114 1 12 3 1 2 2 2 这3种状况，因此答案是3. 第（2）种是在第（ 1）种的基础上延长 它的状况以下 0，0，0，7 0，0，1，6 0，0，2，5 0，0，3，4 0，1，1，5 0，1，2，4 0，1，3，3 0，2，2，3 1，1，1，4 1，1，2，3 1，2，2，2 因此答案是11种。 第（3）种，典型的插板法（不懂的网上搜一下） 。记着就行Cmn--11 n-1 第（4）种，是上边方法的延长，相同记着就行 Cm n-1 下边剖析球不一样的（５）（６）（７）３种状况 先给各位献上一张表，大家别看到数字就惧怕了，其实也就是近似与乘法口诀表，（５）（６） （７）的答案都能够在这个表上找到。 看一下列图上的数字是怎么来的，看下边解说 第一左右两边都是1，第几行就有几个数，比方第 5行就是1XXX1 第二S（n,k)=S(n-1,k-1)+k*S(n-1,k) ，含义是第N排的第K个数等于他上一排的上一个位 置数字加上一排的相同地点数字的 K倍 比如S（7，3）就是第 7排第3个数字，因此他等于上排第 6排第2个数字+第6排第3个 地点*3 因此绘图的话，显然第 1排是1，第2排1，1，推理第3排（左右两边都是1，只有中间那 个数字没确立） 因此S(3,2)=第2排第1个数字+第2排第2个数字两倍=1+1*2=3，因此第3排数字就是1,3,1. 同理S(4,2)=S(3,1)+2*S(3,2)=1+2*3=7, S(4,3)=S(3,2)+3*S(3,3)=3+3*1=6...... 这样类推三角形 因此第（5）种即：N不一样球，M同箱子，无空箱。一共有 S(N,M)种分法，比方7个不一样球， 4个相同箱子，每个箱子起码一个，则看三角形的第7行，第4个数字多少。 ---------------------------------------------------------------------------------------- 而种类6，N不一样球，M同箱，同意空的时候（在种类 5的基础上同意空箱）。显然是N个球不变，一个空 箱子都没有+有一个空箱子+有两个空箱子+有三个空箱子+，，，，，，都装在一个箱子。说的简单点一共有就是 S(N,1)+S(N,2)+S(N,3)+..........S(N,M)=  也就是说 第N排开始第  1个数字向来加到第  M个数字就是总的 分法 ---------------------------------------------------------------------------------------- 而种类  7相同是在种类  5的基础上涨华，由于  5是箱同的，而  7箱不一样，因此箱子自己多了  P(M,M)=M!倍 可能 因此种类7的公式就是M!乘以S(N,M)