隔板法

✍ dations ◷ 2025-02-24 07:21:39 #组合数学

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

相关

阿尔伯塔省阿尔伯塔省（英语、法语：Alberta），简称艾省、亚省、阿省，是加拿大的一个省。阿尔伯塔是加拿大西部草原三省之一，西部与不列颠哥伦比亚相邻，东部与萨斯喀彻温相邻，北部与西北地区相邻，
巴贝特之宴《巴贝特之宴》（丹麦语：Babettes gæstebud），是一部1987年上映的丹麦剧情电影，首映是在当年的戛纳电影节上。该电影由盖布里尔·亚斯里执导，基于凯伦·白烈森原著故事改编。巴贝特
炎陵县炎陵县，原名.mw-parser-output ruby.zy{text-align:justify;text-justify:none}.mw-parser-output ruby.zy>rp{user-select:none}.mw-parser-output ruby.zy>rt{font-feature
碳-氢键碳-氢键是指碳原子与氢原子之间的共价键，是有机化合物中最常看到的共价键。碳-氢键的键长约1.09 Å (1.09 × 10−10 m)，键能约413 kJ/mol，相关于98.7kcal/mol（参见下方的表）。碳
梅肯 (佐治亚州)梅肯（英语：Macon /ˈmeɪkən/），正式名称梅肯-比伯县（Macon–Bibb County），位于美国佐治亚州首府亚特兰大市东南约81英里（约130公里）处，人口约15万，是该州第五大城市、工业重镇，其传统产
阿里-礼萨·法加尼阿里-礼萨·法加尼（波斯语：عليرضا فغانى‎，1978年3月21日－）是伊朗的足球裁判，于伊朗足球顶级联赛波斯湾职业联赛执教多个赛季，2008年起成为亚足联和国际足联认定的国际
乔·舒斯特约瑟夫·乔·舒斯特，（英语：Joseph "Joe" Shuster，/ˈʃuːstər/，1914年7月10日－1992年7月30日）是一位加拿大裔美国人，最知名的是和Jerry Siegel共同创造了DC漫画的角色超人。
弗朗西斯·莱特法兰西斯·莱特（Francis Light）(1740年－1794年10月21日) ，是马来半岛槟榔屿于英国殖民时期的第一任总督。常被称做莱特船长（Captain Francis Light）。约1740年出生于英国的萨福克
中子星碰撞中子星碰撞（英语：Neutron Star collision），又称中子星合并、中子星并合（Neutron star merger），是一种恒星碰撞，其发生方式类似于两颗白矮星合并所致的Ia超新星。当两颗中子星紧密地
莉莉斯莉莉斯（莉丽丝，希伯来语：לִּילִית‎，Lilith）最早出现于苏美尔神话，亦同时记载于犹太教的拉比文学。在这些文学中，她被指为亚当的第一个妻子，由上帝用泥土所造。因不愿雌伏在