排列组合

隔板法是组合数学的方法，用来处理n个无差别的球放进k个不同的盒子的问题。可一般化为求不定方程的解数，并利用母函数解决问题。隔板法与插空法的原理一样。

例1.现在有10个球，要放进3个盒子里●●●●●●●●●●隔2个板子，把10个球被隔开成3个部分

●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、……如此类推，10个球放进3个盒子的方法总数为 ${\displaystyle {\binom {10-1}{3-1}}={\binom {9}{2}}=36}$

n个球放进k个盒子的方法总数为 ${\displaystyle {\binom {n-1}{k-1}}}$(普通隔板法)

问题等价于求${\displaystyle x_{1}+x_{2}+…+x_{k}=n}$的可行解数，其中 ${\displaystyle x_{1},x_{2},…,x_{k}}$为正整数。

隔板法就是在n个元素间的（n-1）个空插入k-1个板子，把n个元素分成k组的方法。

应用隔板法必须满足的3个条件：

公式

将n个相同的求放到m个不同的盒子里的个数为：$C_{n-1}^{m-1}$

例如，把10个相同的球放入3个不同的箱子，每个箱子至少一个，问有几种情况？ $C_{n-1}^{m-1}=C_{9}^{2}=36$

例2.现在有10个球，要放进3个盒子里，并允许空盒子。考虑10+3个球的情况：

●|●|●●●●●●●●●●●、●|●●|●●●●●●●●●●、●|●●●|●●●●●●●●●、●|●●●●|●●●●●●●●、●|●●●●●|●●●●●●●、……

每个盒子的球都被拿走一个，得到一种情况，如此类推：

||●●●●●●●●●●、|●|●●●●●●●●●、|●●|●●●●●●●●、|●●●|●●●●●●●、|●●●●|●●●●●●、……

则问题就等价于把13个相同小球放入3个不同箱子，每个箱子至少一个，有几种情况？

$C_{n+m-1}^{m-1}=C_{12}^{2}=66$

n个球放进k个盒子的方法总数（允许空盒子），等同于n+k个球放进k个盒子的方法总数（不允许空盒子），即${\displaystyle {\binom {n+k-1}{k-1}}}$

问题等价于求${\displaystyle x_{1}+x_{2}+…+x_{k}=n}$的可行解数，其中${\displaystyle x_{1},x_{2},…,x_{k}}$为非负整数。

例3.把10个相同的小球放到3个不同的箱子，第一个箱子至少1个，第二个箱子至少3个，第3个箱子可以为空，有几种情况？

分析: 我们可以在第二个箱子先放入10个小球中的2个，小球剩8个放3个箱子，然后在第三个箱子放入8个小球之外的1个小球（即补充了一个球），则问题转化为把9个相同小球放3不同箱子，每箱至少1个，几种方法？ $C_{8}^{2}=28$

例4. 将20个相同的小球放入编号分别为1，2，3，4的四个盒子中，要求每个盒子中的球数不少于它的编号数，求放法总数。

分析：先在编号1，2，3，4的四个盒子内分别放0，1，2，3个球，剩下14个球，再把剩下的球分成4组，每组至少1个，由例1知方法有$C_{13}^{3}=286$种.

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

分析：因为前2位唯一确定了整个序列，只要求出前两位的所有情况即可，设前两位为a和b

显然a + b