天字一号

管理提醒： 本帖被 puki 设置为精华(2009-06-18) 没吃午饭写的，看完后如果觉得有用，请顶贴！

插板法就是在n个元素间的（n-1）个空中插入 若干个（b）个板，可以把n个元素分成（b+1）组的方法。

应用插板法必须满足三个条件： （1） 这n个元素必须互不相异 （2） 所分成的每一组至少分得一个元素 (3) 分成的组别彼此相异 举个很普通的例子来说明

把10个相同的小球放入3个不同的箱子，每个箱子至少一个，问有几种情况？ 问题的题干满足 条件（1）（2），适用插板法，c9 2=36 下面通过几道题目介绍下插板法的应用

===================================================

a 凑元素插板法 （有些题目满足条件（1），不满足条件（2），此时可适用此方法） 例1 ：把10个相同的小球放入3个不同的箱子，问有几种情况？

3个箱子都可能取到空球，条件（2）不满足，此时如果在3个箱子种各预先放入

1个小球，则问题就等价于把13个相同小球放入3个不同箱子，每个箱子至少一个，有几种情况？ 显然就是 c12 2=66

-------------------------------------------------

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

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

================================================== b 添板插板法

例3：把10个相同小球放入3个不同的箱子，问有几种情况？

-o - o - o - o - o - o - o - o - o - o - o表示10个小球，-表示空位

11个空位中取2个加入2块板，第一组和第三组可以取到空的情况，第2组始终不能取空 此时 若在 第11个空位后加入第12块板，设取到该板时，第二组取球为空 则每一组都可能取球为空 c12 2=66 --------------------------------------------------------

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

因为前2位数字唯一对应了符合要求的一个数，只要求出前2位有几种情况即可，设前两位为ab 显然a+b<=9 ,且a不为0

1 -1- 1 -1 -1 -1 -1 -1 -1 - - 1代表9个1，-代表10个空位

我们可以在这9个空位中插入2个板，分成3组，第一组取到a个1，第二组取到b个1，但此时第二组始终不能取空，若多添加第10个空时，设取到该板时第二组取空，即b=0，所以一共有 c10 2=45 -----------------------------------------------------------

例5：有一类自然数，从第四个数字开始，每个数字都恰好是它前面三个数字之和，直至不能再写为止，如2349，1427等等，这类数共有几个？

类似的，某数的前三位为abc，a+b+c<=9,a不为0 1 -1- 1 -1 -1 -1 -1 -1 -1 - - -

在9个空位种插如3板，分成4组，第一组取a个1，第二组取b个1，第三组取c个1，由于第二，第三组都不能取到空，所以添加2块板

设取到第10个板时，第二组取空，即b=0；取到第11个板时，第三组取空，即c=0。所以一共有c11 3=165

============================================ c 选板法

例6： 有10粒糖，如果每天至少吃一粒(多不限)，吃完为止，求有多少种不同吃法？ o - o - o - o - o - o - o - o - o - o o代表10个糖，-代表9块板

10块糖，9个空，插入9块板，每个板都可以选择放或是不放，相邻两个板间的糖一天吃掉 这样一共就是 2^9= 512啦

============================================= d 分类插板

例7： 小梅有15块糖，如果每天至少吃3块，吃完为止，那么共有多少种不同的吃法？ 此问题不能用插板法的原因在于没有规定一定要吃几天，因此我们需要对吃的天数进行分类讨论 最多吃5天，最少吃1天

1： 吃1天或是5天，各一种吃法 一共2种情况

2：吃2天，每天预先吃2块，即问11块糖，每天至少吃1块，吃2天，几种情况？ c10 1=10 3：吃3天，每天预先吃2块，即问9块糖，每天至少1块，吃3天? c8 2=28 4：吃4天，每天预先吃2块，即问7块糖，每天至少1块，吃4天？c6 3=20 所以一共是 2+10+28+20=60 种

================================= e 二次插板法

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

-o - o - o - o - o - o - 三个节目abc

可以用一个节目去插7个空位，再用第二个节目去插8个空位，用最后个节目去插9个空位 所以一共是 c7 1×c8 1×c9 1=504种 -----------------------------------------------------------

暂时写到这里了，可能还有很多好方法没有被总结到，权当抛砖引玉了。

『原创』管中窥豹，8道排列组合题解析

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即为所求。

关于排列组合问题之全错位排列递推公式的推导！

把编号 1-------------n的小球放到编号1------n的盒子里，全错位排列（1号球不在1号盒，2号球不在2号盒，依次类推），共有几种情况？ ------------------------------------------------------ 设n个球全放错的情况有 s（n）种

1号盒子可以选[2,n] 共（n-1）种选择，设1号盒选择某号球后对应的错排次数是 a （n-1）个选择对应的错排次数是相同的 ，则 s（n）=（n-1）a 不妨设1号盒选择2号球

1： 2号盒选择1号球，剩下 （n-2）个球去错排，有 s（n-2）种情况

2： 2号盒不选择1号球，则后面总有一个盒子选择1号球，我们可以把1号球换成2号球， 对问题没有影响，此时就相当于对（n-1）个球去错排，有s（n-1）种情况 于是a= s（n-1)+s(n-2)

s(n)=(n-1) [ s（n-1）+s（n-2）] s(2)=1,s(3)=2 s(4)=3*(1+2)=9 s(5)=4*(2+9)=44

s(6)=5*(9+44)=265 ....................

关于篮球传接球回到初始人次数的公式总结！

关于篮球传接球回到初始人次数的公式总结！！！

先看看这道典型题， 四人进行篮球传接球练习，要求每人接球后再传给别人。开始由甲发球，并作为第一次传球，若第五次传球后，球又回到甲手中，则共有传球方式多少种?

一种方法是进行分类讨论，得出答案是60。还有人用这么个式子求解 3^5 /4=60.75，理由是一共有 3^5种传球方式，而最后球回到甲乙丙丁的概率是相同的，每个人是1/4,所以上式除以4便是所求，显然这方法是错误的，因为不存在0.75种传球方式。 ----------------------------

先考虑 m个人进行传球，甲第一次传球，传了2次，最后回到甲的次数是多少？

把m个人分成2类，甲和非甲，回到(m-1)个非甲的次数显然是相同的，因为他们彼此不具有特殊性 传了2次，回到甲的次数 a=（m-1）×1，总的传球方式b=（m-1）^2 回到非甲的次数c= （b-a)/ (m-1)= m-1-1=a-1

即回到甲的次数比回到非甲的次数多1

如果是传了3次的情况，考虑 回到甲 和回到乙 （代表非甲）的次数

1 甲传乙，持球人是乙，再传2次，由上面的讨论可知，回到乙的次数比甲的次数多1 2 甲传给 非乙 球回到甲，乙的次数相同（ 因为此时甲乙都不是持球人，是对称的） 所以传3次的情况是 回到乙的次数比回到甲次数多1，即回到 甲次数比 非甲 的次数 少1 由归纳法，可知 球传了奇数次 回到甲的次数比回到非甲的次数 少1 球传了偶数次 回到甲的次数比回到非甲的次数 多1

因此，对于一般的问题， m个人传球，甲第一次传，传了n次，球又回到甲手中，有几种方式？ 设有x种方式，则 x+（m-1）（x+1）=（m-1）^n n为奇数

x+（m-1）（x-1）=（m-1）^ n n为偶数 解这个一元一次方程显然比分类讨论要快捷的多了。 -------------------

以前发过了，奇怪今天怎么找不到了，再发一次吧

『原创』幼儿园买来9种不同的书籍，每个小朋友领3本，问至少几个小朋友

幼儿园买来9种不同的书籍，每个小朋友领3本，问至少几个小朋友领过后，一定会出现两个小朋友领的书是相同的？

0 0 0 0 0 0 0 0 0 - - 9个0代表不同书籍 （1） 3本都不同 c9 3，从9个0里选3个

（2）2本不同，可能第一个0取2本，可能第二个0取2本， 分别对应00-（第一个-） 和00- （第二个-）

（3）1本不同 对应 取到0 --

如此从11个位置选3个，对应了3种分类，答案是c11 3+1=166 -------------------------------------------------------

幼儿园买来9种不同的书籍，每个小朋友领5本，问至少几个小朋友领过后，一定会出现两个小朋友领的书是相同的？

0 0 0 0 0 0 0 0 0 - - - -

（1）5本不同，从9个0里选5个

（2）4本不同(选了4个0），可能第1或第2或第3或第4 个0取到2本，分别对应0000 - （有4个-可选，对应前面4个0）

（3）3本不同(选了3个0），还有2本分配到3个位置，有6种情况，选了3个0，再从4个-里选2个-，也是c4 2=6，对应了前面6种分类

（4）2本不同(选了2个0），还有3本分配到2个位置，有4种情况，选了2个0，再从4个-里选3个-，c4 3=4 对应了前面4种分类

（5）1本不同(选了1个0），选了一个0，还要从4个-里选4个-，c4 4=1，与前面一一对应 所以从13个空里选 5个的算法 包括了上述的5种分类，且不遗漏，不重复，答案是c13 5+1=1288 =================================== 第一个问题的分类验证： （1）3本不同 c9 3=84 （2）2本不同 c9 2× c2 1=72 （3）1本不同(3本相同） c9 1=9 84+72+9=165 165+1=166

----------------------------------------- 第二个问题的分类验证： （1）5本不同： c9 5=126 （2）4本不同： c9 4× c4 1=504

（3）3本不同：c9 3×c4 2（插板法）=504 （4）2本不同：c9 2×c4 1（插板法）=144 （5）1本不同（5本相同）： c9 1=9 126+504+504+144+9=1287 1287+1=1288

~~~~~~~~~~~~~~~~~~~~~~~~~~~

n种元素 (每种元素足够多） 选m个的公式： c(n+m-1,m) （附上简证）

c（n+m-1，m）= ∑ c（n，i）*c（m-1，m-i） ， i 取[1,m] { 表示从n个中取i个出来，再从剩下的m-1个中取 m-i 个出来}

其中c（n，i）对应 从 n个元素里选 i个选素，此时还有 m-i个名额（相同）分配到 这i个元素（不同）中

由插板法有 c（m-i +i -1，i-1）=c（m-1，i-1）=c（m-1，m-i） 这样 i取尽[1,m],就包含了所有的选法

也即 ∑ c（n，i）*c（m-1，m-i）=c（n+m-1，m）

a+b+c<=10 ，a+b+c+d<=10

a+b+c<=10 ，a+b+c+d<=10

以上两个不等式的非负整数解各有几种？没事做做 ---------------------------------------------------------------- x=a+1,y=b+1,z=c+1,则 x，y，z为正整数 x+y+z<=13

0- 0- 0- 0- 0 -0 -0 -0 -0 -0- 0- 0 -0- 0代表13个1，-代表空位 13个空 选3个插入3板，13个1被分成4部分，前3部分分别对应x，y，z 满足x，y，z>=1,且x+y+z<=13, 共有 c13 3=286种 一个xyz与一个abc唯一对应，所以共有286个abc

p.s 这里取3个空，而不取2个空，是由于前三个数和可以小于13 ------------------------------------------------------ a+b+c+d<=10

x=a+1,y=b+1,z=c+1,t=d+1,x，y，z，t为正整数，x+y+z+t<=14 分析方法同上，需要从14个空选4个 c14 4=1001

----------------------------- 模型应用举例

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

小梅有12颗糖，4天内有几种吃法（不一定吃完）？

五个人排成一排，甲不在排头，乙不在正中间，丙不在排尾的

五个人排成一排，甲不在排头，乙不在正中间，丙不在排尾的，问共有几种排法？

甲不在排头，乙不在正中间，丙不在排尾的情况有x种

题干的否命题是甲在排头（a）或 乙在中间（b）或丙在排尾（c），对应情况为y x+y=p55 （所有的情况） y=a并b并c

a并b并c=a+b+c-a交b-a交c-b交c+a交b交c （三集合容斥原理） =3p44-3p33+p22=56 x=p55-y=120-56=64