首页 > 华体会登录手机版

隔板法详解(各种方法) 时间: 2024-04-17 05:53:59 |   作者: 华体会登录手机版


  分析:将10个球排成一排,球与球之间形成9个空隙,将两个隔板插入这些空隙中(每空至多插一块隔板),规定由隔板分成的左、中、右三部分的球数分别为x、y、z之值(如下图)。则隔法与解的个数之间建立了一一对立关系,故解的个数为C(n-1,m-1)=C(9,2)=36(个)。

  分析:注意到x、y、z可以为零,故例1解法中的限定“每空至多插一块隔板”就不成立了,怎么办呢?只要添加三个球,给x、y、z各添加一个球,这样原问题就转化为求 x+y+z=13的正整数解的个数了,则问题就等价于把13个相同小球放入3个不同箱子,每个箱子至少一个,有几种情况?易得解的个数为C(n+m-1,m-1)=C(12,2)=66(个)。

  例3:把10个相同小球放入3个不同箱子,第一个箱子至少1个,第二个箱子至少3个,第三个箱子可以放空球,有几种情况?

  我们可以在第二个箱子先放入10个小球中的2个,小球剩8个放3个箱子,然后在第三个箱子放入8个小球之外的1个小球,则问题转化为把9个相同小球放3不同箱子,每箱至少1个,几种方法?C(8,2)=28

  分析:先在编号1,2,3,4的四个盒子内分别放0,1,2,3个球,剩下14个球,有1种方法;再把剩下的球分成4组,每组至少1个,由例1知方法有C(13,3)=286(种)。

  例5:有一类自然数,从第三个数字开始,每个数字都恰好是它前面两个数字之和,直至不能再写为止,如257,1459等等,这类数共有几个?

  因为前2位数字唯一对应了符合标准要求的一个数,只要求出前2位有几种情况即可,设前两位为ab

  我们要把9个1分成两组,但b可以为0,我们先给b一个1,然后就等于10个小球放入两个(a,b)不同的箱子,每一个箱子至少放一个,C(9,1),但这是错误的,为什么?因为1不一定要全部放入。其实解决这一个问题可以这么想,我们在引进一个盒子c来放ab取完剩下的1,所以报证c中球数大于0,所以要在增加一个球,题目就等价于,11个小球放入两个(a,b)不同的箱子,每一个箱子至少放一个,所以一共有c(10,2)=45.

  1-1-1-1-1-1-1-1-1-- 1代表9个1,-代表10个空位(第一个没有因a不能为0),我们大家可以在这9个空位中插入2个板,分成3组,第一组取到a个1,第二组取到b个1,但此时第二组始终不能取空,若多添加第10个空时,设取到该板时第二组取空,即b=0,所以一共有c(10,2)=45

  例6:有10粒糖,如果每天至少吃一粒(多不限),吃完为止,求有多少种不同吃法?

  10块糖,9个空,插入9块板,每个板都可以再一次进行选择放或是不放,相邻两个板间的糖一天吃掉

  例7:小梅有15块糖,如果每天至少吃3块,吃完为止,那么共有多少种不同的吃法?

  此问题不能用插板法的原因主要在于没有规定一定要吃几天,因此我们应该对吃的天数进行分类讨论

  2:吃2天,每天预先吃2块,即问11块糖,每天至少吃1块,吃2天,几种情况?C(10,1)=10

  3:吃3天,每天预先吃2块,即问9块糖,每天至少1块,吃3天?C(8,2)=28

  4:吃4天,每天预先吃2块,即问7块糖,每天至少1块,吃4天?c(6,3)=20

  例8:在一张节目单中原有6个节目,若保持这些节目相对次序不变,再添加3个节目,共有几种情况?

  可以用一个节目去插7个空位,再用第二个节目去插8个空位,用最后个节目去插9个空位

  首先我们拿出m个小球,还剩下n-m个小球。这n-m个小球一共有n-m+1个空(左右两边也可以),把这m个小球插入到这n-m+1个空里就是答案,即

  有n个不同的盒子,在每个盒子中放一些球(可以不放),使得总球数≤m,求方案数(mod p)

  这个题和原来不一样的地方:总球数≤m,一般我们就是总球数就是m,所以我们大家可以增加一个盒子,现在n+1个盒子,现在假设就要放m个球,n来来放k个球,剩下的m-k就放在那个我们增加的盒子里,这样n个盒子的组合球数就是我们要求的,所以题目等价于m个球放入n+1个盒子中,盒子有里球数可以为0,添元素插板法,每一个盒子都增加一个球,即m+n+1个球放入n+1个盒子,c(m+n,n)为答案。