隔板法

✍ dations ◷ 2025-09-19 09:55:22 #组合数学

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

隔板法与插空法的原理一样。

现在有 $10 {\displaystyle 10}$ $10$ 个球，要放进 $3 {\displaystyle 3}$ $3$ 个盒子里

隔 $2 {\displaystyle 2}$ $2$ 个板子，把 $10 {\displaystyle 10}$ $10$ 个球被隔开成 $3 {\displaystyle 3}$ $3$ 个部分

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

$n {\displaystyle n}$ $n$ 个球放进 $k {\displaystyle k}$ $k$ 个盒子的方法总数为 ${\binom {n-1}{k-1}}$ ${\binom {n-1}{k-1}}$

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

现在有 $10 {\displaystyle 10}$ $10$ 个球，要放进 $3 {\displaystyle 3}$ $3$ 个盒子里，并允许空盒子。考虑 $10+3$ $10+3$ 个球的情况：

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

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

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

${\binom {n+k-1}{k-1}}$ ${\binom {n+k-1}{k-1}}$ 也是 $(a_{1}+a_{2}+...+a_{k})^{n}$ $(a_{1}+a_{2}+...+a_{k})^{n}$ 展开式的项数 $\sum _{n_{1}+n_{2}+...+n_{k}=n}1$ $\sum _{{n_{1}+n_{2}+...+n_{k}=n}}1$

相关

新石器时代新石器时代（Neolithic），在考古学上是石器时代的最后一个阶段，以磨制石器和制作陶器为主，大约从1万年前开始，结束时间从距今10000多年至2000多年不等。不过，在有些地区，如中美洲，在西
波罗的-斯拉夫语族波罗的-斯拉夫语族（Baltic-Slavic language）是印欧语系中波罗的语族和斯拉夫语族的合称。波罗的语族的语言和斯拉夫语族的语言共同点较多，两者较为接近。但波罗的诸语和斯拉夫
自杀炸弹自杀攻击或称自杀式袭击、人肉炸弹，是一种将自杀扩大为伤害自己及目标者的行为，现代的自杀式攻击通常是由自杀者在身上绑好炸弹，走到目标地，或是以装满炸弹的车冲撞特定目标然后
阿尔卑斯冰川山谷冰川是指在高山雪线以上的冰原当中。如果冰层开始往下面移动，且过雪线后继续下移，流动情形酷似山谷中的河川，因此称为山谷冰川,简称谷冰川。山谷冰川的范围是以雪线来当作
沃克斯霍尔桥沃克斯霍尔桥（Vauxhall Bridge）是一座位于英国伦敦中心区泰晤士河上的拱桥，是二级登录建筑。此桥的南岸是沃克斯霍尔，北岸是皮姆利科，其上是A202号公路。1906年时为了取代1809年
白天白昼、白天、日间，是地球表面受到日光直接或间接照射之时，即日出至日落之间。相对之下，其它的行星，在旋转之下也会因为被恒星照亮，也会经历白昼的状态。但是此处主要论述地球上的
哲学剃刀哲学剃刀（Philosophical razor）指的是能指导人们排除（剃掉）一个现象中不太可能的解释或避免不必要行动的一个原则或经验法则。有名的剃刀如下：
机器语言机器语言（machine language）是一种指令集的体系。这种指令集称为机器代码（machine code），是电脑的CPU可直接解读的数据。机器代码有时也被称为原生码（Native Code），这个名词比较强调
法国雅典学院法国雅典学院（École française d'Athènes，缩写EfA）是建立在雅典的一个法国高等教育机构，致力于开展对希腊的语言、历史以及古文明的研究。它建于七月王朝期间的1846年，在十九
废除工作《废除工作》（The Abolition of Work）是鲍伯·布莱克（Bob Black）于1985年写下的文章，又称为《工作时代的终结》。该文章收入于文选集《废除工作与其他文章》（The Abolition of Wor