隔板法

✍ dations ◷ 2025-09-14 12:43:14 #组合数学

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

相关

五月广场母亲五月广场母亲（西班牙语：Madres de Plaza de Mayo）是在1976年和1983年间在阿根廷因为反对政府独裁内失去家属的人们所进行的运动。1976至1983年间阿根廷大约有三万名左翼学生、
马略卡岛参数所指定的目标页面不存在，建议更正成存在页面或直接建立下列一个页面（建立前请先搜寻是否有合适的存在页面可以取代）：注意如果条目名称是繁体字要使用繁体的“消歧義”，简体字
OpenCriticOpenCritic是电子游戏评论聚合网站。网站会收集众主流游戏媒体对各款游戏的评论，并计算该游戏的平均得分。网站还提供其他数据，如推荐该游戏的媒体百分比、游戏在OpenCritic的
郑淑珍郑淑珍，台湾生物化学家，中央研究院院士。1977年获台湾大学化学学士学位，1983年获杜克大学生物化学博士学位，之后先后在美国国立卫生研究院、加州理工学院做博士后研究。1988年-1
雷诺·加缪让·雷诺·加布里埃尔·加缪（/kæˈmuː/; 法语发音：.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","
萊斯·威廉姆斯萊斯·威廉姆斯（英语：Rhys Williams，1988年7月14日－）是一名澳大利亚职业足球运动员，威廉姆斯多才多艺，场上可以胜任后腰、中后卫和右后卫，最近更担任前腰，现时效力澳超俱乐部墨尔本胜
易伯坚易伯坚（？年－？年）。河南省信阳县人。民国37年（1948年）在河南省第四选区当选第一届立法委员。
星果凤梨星果凤梨（学名：），为凤梨科菠蒂亚属下的一个种。多年生常绿草本。原产于巴西东南部，生长在岩石或是海岸沙地上。关于星果凤梨的学名，其中属名Portea出于向法国植物学家 Marius Por
仁内建之仁内建之（日语：仁内建之，1933年2月21日－2000年4月12日），日本男演员、配音员。本名宝达晃一（日语：宝達晃一／ほうたつこういち）。从属于Theatre Echo。北海道带广市出身。日本大学毕
方法演技方法演技，又称演技方法，是令演员完全融入角色中的表演方式，除了演员本人的性格之外，也要创造角色本身的性格及生活，务求写实地演绎角色。方法演技由俄国戏剧大师史坦尼斯拉夫斯基