球与盒子的排列组合问题(精华版)(3页).doc

《球与盒子的排列组合问题(精华版)(3页).doc》由会员分享，可在线阅读，更多相关《球与盒子的排列组合问题(精华版)(3页).doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-球与盒子的排列组合问题(精华版)-第 3 页球与盒子的排列组合问题（精华版）首先看一下分类，主要有8种：1）球 同，盒 同，无 空箱 2）球 同，盒 同，允许空箱 3）球 同，盒不同，无 空箱 4) 球 同，盒不同，允许空箱 5) 球不同，盒相同，无 空箱 6）球不同，盒相同，允许空箱 7) 球不同，盒不同，无 空箱 8）球不同，盒不同，允许空箱做这种题型关键是要对号入座，下面的解释分析统一假设m个球，n个盒子。先从最简单入手，第8种，每个球都有n种选择，所以是剩下的我们先从前四种（数字都不会太大，且分析较简单）开始。做题时一看到球同，盒同，就想到凑数法，事实证明这是最快的一种方法。如第（1

2、）种，假设m=7，n=4.它的情况只有 1 1 1 41 1 2 31 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）种，典型的插板法（不懂的网上搜一下）。记住就行第（4）种，是上面方法的延伸，同样记住就行下面分析球不同的 （） （）（）种情况先给各位献上一张表，大家别看到数字就害怕了，其实也就是类似与乘法口诀表，（）（）（）的答案都可以在这个表上找到。看一

3、下图上的数字是怎么来的，看下面解释第一左右两边都是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

4、, 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)