隔板法

✍ dations ◷ 2025-11-27 09:56:29 #组合数学

隔板法是组合数学的方法，用来处理 $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$

相关

疏密波纵波，又称为疏密波，是指在传播介质中质点的振动方向与波的传播方向平行的一类波，形成的波是疏密相间的波形。非电磁波的纵波的例子有声波（压力的传递、粒子位移、弹性物质中粒子
HappyCash远鑫电子票证，是台湾的电子票证发行商之一，于2014年6月27日获行政院金融监督管理委员会核准成立。其发行的票证为有钱卡，并结合同集团鼎鼎联合行销的HAPPY GO集点卡。核心业务
机车机车可能是指：
副食副食品（英语：Non-staple food）是营养学的一个分类，指主食以外的食物；其具体指涉范围因不同饮食文化对“主食”的定义而异。一般而言，米、小麦、玉米、马铃薯等淀粉含量较多，以提供
詹姆斯·布莱恩特·科南特詹姆斯·布莱恩特·科南特（英语：James Bryant Conant，1893年3月26日－1978年2月11日），美国化学家、政治家和教育家，曾任哈佛大学校长及美国驻西德大使。1893年3月26日，科南特出生于美
我和我的小鬼们《墙壁之间》（法语：Entre les murs），2008年法国电影，由洛宏·康铁导演。根据法国作家弗朗索瓦·贝戈多（法语：François Bégaudeau）的2006年同名小说改编，小说是根据作者在巴黎的内城
拉斯帕尔马斯大加那利岛拉斯帕尔马斯（西班牙语：Las Palmas de Gran Canaria，西班牙语：.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucid
沃西詹姆斯·阿格·沃西（英语：James Ager Worthy，1961年2月27日－），美国NBA联盟前职业前篮球运动员，身高六呎九寸，体重二百二十五磅，担任小前锋，在1982至1994年间为洛杉矶湖人队效力长达十
CW电视台CW电视联播网（英语：The CW Television Network；简称：CW电视网 / The CW）是美国一家英语免费电视联播网，由CW电视网有限责任公司（The CW Network, LLC）负责运营。CW电视网有限责任公
2017年7月逝世人物列表2017年7月逝世人物列表，是用于汇总2017年7月期间逝世人物的列表。