隔板法

✍ dations ◷ 2025-10-22 12:27:33 #组合数学

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

相关

鸡尾酒疗法鸡尾酒疗法，专指一种治疗艾滋病的方法。它由华裔美籍科学家何大一发明，是目前公认的疗效最佳的艾滋病治疗方法。这项研发使何大一以“艾滋病研究者”（AIDS Researcher）的身份荣
平行演化平行演化是指两个或多个相关但不同种系的生物，因生活在相似环境而发育了相似的形状。
蛋化石蛋化石（Egg fossils）是指由远古动物产下的卵化石化之后的残留物。作为动物的生理化过程的见证，蛋化石被认为是遗迹化石的一个类型。在极少数情况下，蛋化石内可能还保存有曾经在
油饭油饭又称蒸糯米饭，是华南及台湾一种传统的米食料理，通常是以蒸熟的糯米，拌入炒香的佐料。佐料常见的有肉丝、香菇、红葱酥、干鱿鱼、虾米及栗子等等，并以麻油及酱油调味。依台湾
埃里克森社会心理发展阶段埃里克森社会心理发展阶段是根据爱利克·埃里克森描述，将正常人的一生，从婴儿期到成人晚期，分为8个发展阶段。在每个阶段，个人都面临、并克服新的挑战。每个阶段都建筑在成功完
厦门外国语学校厦门外国语学校，简称厦外，是与厦门经济特区同年诞生的全国17所外国语学校之一，也是福建省第一所外国语学校。学校现有初中部与高中部。初中部坐落于筼筜湖畔，高中部位于海沧区“
陆萼庭陆萼庭，1925年-2003年，中国昆曲研究专家。浙江镇海县（宁波）人，生于上海。1947年，毕业于上海复旦大学中文系，师从王佩诤、赵景深等研读戏曲史。大学期间，陆萼庭并在由赵景深主编的《
张登桂张登桂（越南语：Trương Đăng Quế／.mw-parser-output .han-nom{font-family:"Nom Na Tong","Han-Nom Gothic","Han-Nom Ming","HAN NOM A","HAN NOM B","Ming-Lt-HKSCS-UNI-
马里斯·斯特罗姆伯格斯马里斯·斯特罗姆伯格斯（拉脱维亚语：Māris Štrombergs，1987年3月10日－）生于瓦尔米耶拉，是一名拉脱维亚小轮车运动员。斯特罗姆伯格斯曾参加过三届奥运，在2008年北京奥运会上，他以3
张家宾张家宾（？－1886年）为中国清朝武官官员，本籍。1886年（光绪12年）奉旨接任杨在元担任台湾镇总兵。是台湾清治时期此期间，受台湾道制约的台湾地区最高军事首长。1886年，张家宾因疾卒于任。