排列组合插板法.doc

『原创』排列组合问题之插板法应用不完全小结!管理提醒:本帖被puki设置为精华(2009-06-18)没吃午饭写的,看完后如果觉得有用,请顶贴!插板法就是在n个元素间的(n-1)个空中插入若干个(b)个板,可以把n个元素分成(b+1)组的方法。应用插板法必须满足三个条件:(1)这n个元素必须互不相异(2)所分成的每一组至少分得一个元素(3)分成的组别彼此相异举个很普通的例子来说明把10个相同的小球放入3个不同的箱子,每个箱子至少一个,问有几种情况?问题的题干满足条件(1)(2),适用插板法,c92=36下面通过几道题目介绍下插板法的应用===================================================a凑元素插板法(有些题目满足条件(1),不满足条件(2),此时可适用此方法)例1:把10个相同的小球放入3个不同的箱子,问有几种情况?3个箱子都可能取到空球,条件(2)不满足,此时如果在3个箱子种各预先放入1个小球,则问题就等价于把13个相同小球放入3个不同箱子,每个箱子至少一个,有几种情况?显然就是c122=66-------------------------------------------------例2:把10个相同小球放入3个不同箱子,第一个箱子至少1个,第二个箱子至少3个,第三个箱子可以放空球,有几种情况?我们可以在第二个箱子先放入10个小球中的2个,小球剩8个放3个箱子,然后在第三个箱子放入8个小球之外的1个小球,则问题转化为把9个相同小球放3不同箱子,每箱至少1个,几种方法?c82=28==================================================b添板插板法例3:把10个相同小球放入3个不同的箱子,问有几种情况?-o-o-o-o-o-o-o-o-o-o-o表示10个小球,-表示空位11个空位中取2个加入2块板,第一组和第三组可以取到空的情况,第2组始终不能取空此时若在第11个空位后加入第12块板,设取到该板时,第二组取球为空则每一组都可能取球为空c122=66--------------------------------------------------------例4:有一类自然数,从第三个数字开始,每个数字都恰好是它前面两个数字之和,直至不能再写为止,如257,1459等等,这类数共有几个?因为前2位数字唯一对应了符合要求的一个数,只要求出前2位有几种情况即可,设前两位为ab显然a+b<=9,且a不为01-1-1-1-1-1-1-1-1--1代表9个1,-代表10个空位我们可以在这9个空位中插入2个板,分成3组,第一组取到a个1,第二组取到b个1,但此时第二组始终不能取空,若多添加第10个空时,设取到该板时第二组取空,即b=0,所以一共有c102=45-----------------------------------------------------------例5:有一类自然数,从第四个数字开始,每个数字都恰好是它前面三个数字之和,直至不能再写为止,如2349,1427等等,这类数共有几个?类似的,某数的前三位为abc,a+b+c<=9,a不为01-1-1-1-1-1-1-1-1---在9个空位种插如3板,分成4组,第一组取a个1,第二组取b个