看似很简单的问题其实非常复杂,球是否相同,箱是否相同?是否允许有空盒 不难看出一共8类情况 1)球同,盒同,无空箱 2)球同,盒同,允许空箱 3)球同,盒不同,无空箱 4)球同,盒不同,允许空箱 5)球不同,盒相同,无空箱 6)球不同,盒相同,允许空箱 7)球不同,盒不同,无空箱 6)球不同,盒不同,允许空箱 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 先来看3,4.这个就是最典型的公考中经常遇见的插板法(关于插板法的解释我懒的说了,自己搜,论坛百度都容易找的到) 只是需要注意是否允许空箱 3的公式是把n个球排成一排,(一种方法),它们中间有n-1个空。取m-1个小棍,放到空上,就把它们分成m部分,由于小棍不相邻,所以没有空箱子。它的方法数有C(N-1,M-1),也就是球减1里面挑M-1个箱子做组合 4的公式在3的基础上升华出来的,为了避免空箱子,先在每一个箱子假装都放一个球,这样就有n+m个球,C(n+m-1,m-1),多了M个元素而已 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 关于1,2类情况,本来我想教大家一个特殊三角形的,但画起来比较麻烦,速度还不如穷举快,所以就略了,愿意学的我还是可以教他,不会真的还不如穷举来的快。个人建议还是用最常见的凑数法,而且公考中不会出现球和盒子数字比较大的情况。 法,例如7个相同球放入4个相同盒子,每盒至少一个(1号情况),则先4个盒子每个放1个,多余3个。只需要考虑这3个球的去处就OK,由于盒子相同,所以只需要凑数就OK,不必考虑位置。 比如300,211,111只有三种 例如7个相同球放入4个相同盒子,可以空盒,则还是凑数,大的化小的,小的化更小的。。。。。。 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种 1,2,3,4公考常见类型,必须学会!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1234都是球相同的情况。但如果球不同怎么办??? 先来分析最特殊的8号:N球不同,M箱不同,允许空。每个球都有M种选择,N个球就有M的N次方分法。 关于5,6,7这情况,我先教大家一个非常特殊的三角形,这个你在狗哥百度非常难以找的到的,秘传型,一般人我不会告诉他的。我画了个图,如果看不到的话直接看这个地址 http://tu.1pian.com/upload/1245501262x1996894379.jpg 看起来很复杂,其实很简单 第一左右两边都是1,第几行就有几个数,比如第5行就是1XXX1 第2 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) ------------------------------------------------------------------------------------------- 综上所述,所有8种类型都有一定的解法了 大家可以到云淡的帖子http://bbs.qzzn.com/read-htm-tid-9919765.html,练习一下,看看他的其中,5,6,7类型种情况是不是比我的办法慢很多。 例如8个不同的球放进3个相同的盒子里,有几种方法 球不同,箱同,可以空,则就是S(N,1)+S(N,2)+S(N,3)+..........S(N,M) 看三角形就知道第8行前3个数字的和1 127 966=1094, 8个不同的球放进3个相同的盒子里,每盒至少一个,有几种方法 球不同箱同,非空,公式S(N,M)即第8行第3个966 8个不同的球放进3个不同的盒子里,每盒至少一个,有几种方法 球不同,盒不同,非空,公式M!*S(N,M)=3!*S(8,3)=6*966=5796 |
引文来源 排列组合之“捆绑法”、“插空法”、“插板法”_李委明_新浪博客
1:8个相同的球放进3个相同的盒子里,每盒至少一个,有几种方法
取球最少的盒子取1,取球第二少的盒子可以取[1,3] 3种
取球最少的盒子取2,取球第二少的盒子可以取[2,3] 2种
取球最少的盒子取3,此情况不存在,一共5种
按取球多寡来分类讨论可以做到不遗漏,不重复
-------------------------------------------------------------------------
2:8个相同的球放进3个不同的盒子里,每盒至少一个,有几种方法
插板法,c7 2=21
--------------------------------------------------------------------------
4:8个不同的球放进3个相同的盒子里,每盒至少一个,有几种方法
取球最少盒子取1时,有116,125,134三种情况,分别有c8 6=28, c8 1*c7 2=168, c8 1*c73=280
取球最少盒子取2时,有224,233二种情况,分别有c82*c62/2=210,c83×c53/2=280
一共28+168+280+210+280=966
-------------------------------------------------------------------------------
3:8个不同的球放进3个不同的盒子里,每盒至少一个,有几种方法
4问中的966种情况,每种情况的三个元素都是互异的,比如 116(因为球是不同的),这三个元素进行全排列p33=6,乘以966=5796即为所求
------------------------------------------------------------------------------------
5:8个相同的球放进3个相同的盒子里,有几种方法
最少盒子取0,次盒子取[0,4]
最少盒子取1,次盒子取[1,3]
最少盒子取2,次盒子取[2,3]
一共5+3+2=10种
------------------------------------------------------------------------------
6:8个相同的球放进3个不同的盒子里,有几种方法
预先在三个盒子种各放入一小球,则问题转化为11同球放3不同盒子,每盒至少1个,几种方法? 用插板法,c10 2=45
----------------------------------------------------------------------------
7:8个不同的球放进3个不同的盒子里,有几种方法
每个球都有3种选择,8个球就有3^8=6561
-----------------------------------------------------------------------------
8:8个不同的球放进3个相同的盒子里,有几种方法
7问中的一般情况(3个元素都相异),比如116,一共有6种排列(球是不同的),此问中,盒子是相同的,因此这6种排列都只算一种情况。
但如果2个元素相同的时候,有且只有 008,只有3种排列,我们多添加3种进去,令其也重复6次,则(6561+3)就是 所有的情况都重复了6次,(6561+3)/6=1094即为所求。
联系客服