隔板法

✍ dations ◷ 2025-06-30 17:59:46 #组合数学

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

相关

西加拿大加拿大西部（Western Canada）是加拿大的地理概念，通常也被称作西部省份或者直呼西部。包含了安大略西部的英属哥伦比亚、艾伯塔、萨斯喀彻温和马尼托巴四省。西加拿大又可以根据
中央大平原大平原（英语：Great Plains），多称北美大平原、北美大草原，是北美洲中部一块广袤的平原地区，大致位于密西西比河以西、落基山脉以东、格兰德河以北。自然植被以草为主。大平原东西长
2104多伦多小行星2104（英语：2104 Toronto）是一颗围绕太阳公转的小行星。1963年8月15日，K. W. Kamper在陶腾堡发现了此天体，并以多伦多大学命名。这也是加拿大的天文台所发现的第一颗小行星
雪蝎蛉科雪蝎蛉科，俗称雪蝎蛉、雪蚤，是长翅目的昆虫。该科仅包含30个物种，全都分布在北半球的极地或高海拔地区。2008年的DNA及蛋白质分析，发现该科的演化支与蚤目的亲缘关系较接近，反而
丹尼尔·卡尔顿·盖杜谢克丹尼尔·卡尔顿·盖杜谢克（Daniel Carleton Gajdusek，1923年9月9日－2008年12月12日），美国科学家，具有斯洛伐克和匈牙利血统。由于在苦鲁病上的贡献，他与巴鲁克·塞缪尔·布隆伯格一
巫传统宗教仪式：神明秘密社会：巫觋是指能运用超自然力的人，通称巫。说文解字：“能斋肃事神明者，在男曰觋，在女曰巫”，男性称为.mw-parser-output ruby.zy{text-align:justify;text-ju
2000年土耳其人口普查2000年土耳其人口普查是土耳其自1927年的15次人口普查，也是土耳其最后一次采用传统问卷式普查，此后土耳其改采地址登记式普查。由土耳其统计局 (Türkiye İstatistik Kurumu,
塞萨尔·巴尔达奇尼塞萨尔·巴尔达奇尼（法语：César Baldaccini，1921年1月1日－1998年12月6日），法国现代雕塑家。他的青铜作品同时融合了两项现代雕塑的元素：承袭自传统的雕塑品质及组合技法，后者尤为塞
瓦尔泰尔·弗雷尔-奥尔邦于贝尔·约瑟夫·瓦尔泰尔·弗雷尔-奥尔邦（Hubert Joseph Walthère Frère-Orban，1812年4月22日－1896年1月2日），比利时政治家，自由党改革派首领，两次出任首相（1868—1870，1878—1884
太阳快运航空太阳快运航空公司（Güneş Ekspress Havacılık A.Ş.，一般称为太阳快运航空）是一家土耳其的航空公司，总部设在安塔利亚。太阳快运航空主要运营欧洲、亚洲和北非地区的航线，其子