隔板法

✍ dations ◷ 2025-03-07 10:45:25 #组合数学

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

相关

中非共和国2019冠状病毒病中非共和国疫情，介绍在2019新型冠状病毒疫情中，在中非共和国发生的情况。2020年3月14日，中非共和国确诊首例新冠肺炎病例。患者为意大利人，8日飞抵中非共和国首都
白普理白普理（英文：Bradbury），是美国加利福尼亚州洛杉矶县下属的一座城市。建市于1957年7月26日，面积大约为1.96平方英里 (5.1平方公里)。根据2010年美国人口普查，该市有人口1,048人。
2019冠状病毒病摩纳哥疫情2019冠状病毒病摩纳哥疫情，介绍在2019新型冠状病毒疫情中，在摩纳哥发生的情况。2020年2月28日，摩纳哥确诊首例新冠肺炎病例，已被隔离，将送往法国尼斯治疗。3月12日，摩纳哥确诊第2
超级橄榄球联赛超级橄榄球联赛（英语：Super Rugby）是南半球及亚洲最大的联合式橄榄球俱乐部锦标赛，目前由澳洲、新西兰、南非、阿根廷、日本五国共15支俱乐部球队参加。超级橄榄球联赛的前身是
联合全面行动计划谈判进程《联合全面行动计划谈判进程》是对伊朗核计划达成全面的协议中的谈判最后阶段的话题。参与的国家为伊朗和“P5+1”（美国、俄罗斯、中国、法国、英国、德国、欧洲联盟）。协议针
布雷斯劳号小巡洋舰陛下之舰布雷斯劳号（德语：SMS Breslau）是德意志帝国海军于1910年代建造的四艘马格德堡级小巡洋舰的二号舰，以西里西亚省首府布雷斯劳命名。它于1910年在斯德丁的伏尔铿船厂开始
超高速超高速（英语：Hypervelocity）是指一个非常高的速度，一般超过3,000m/s（6,700mph，11,000km/h，10,000ft/s，或8.8马赫）。在超高速的速度下发生碰撞时，材料的强度与惯性应力相比会变得非常小
噪点图像噪声（image noise）是图像中一种亮度或颜色信息的随机变化(被拍摄物体本身并没有)，通常是电子噪声的表现。它一般是由扫描仪或数码相机的传感器和电路产生的，也可能是受胶片
酸性火成岩酸性火成岩，也叫做“花岗岩-流纹岩，是火成岩的一大类，其中富含二氧化硅，含量达65-75%。酸性岩包括花岗岩、花岗斑岩、流纹岩等，其中浅色的含有钾长石、斜长石、石英等，深色的含有
凯尔·林格伦凯尔·诺伍德·林格伦（英语：Kjell Norwood Lindgren，1973年1月23日－），生于台湾台北市，美国国家航空航天局（NASA）太空人。2009年，获选成为太空总署第20太空小组（NASA Astronaut Group 20