隔板法

✍ dations ◷ 2024-09-20 11:36:08 #组合数学

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

相关

白消安白消安（英语：Busulfan，商品名马利兰、白舒非）是一种从1959年开始使用的抗癌药。它是一种细胞周期非特异性烷化剂，属于烷基磺酸酯类型，化学结构全称是1,4-丁二醇二甲烷磺酸酯。白消
内部网内部网（Intranet），又称企业内部网或内联网，是指采用因特网技术的计算机网络，它以TCP/IP协议作为基础，以Web为核心应用构成统一和便利的信息交换平台，例如文件传输、文件管理、电子
第六分队海豹部队第六分队紧急狂暴行动贝鲁特人质危机阿基莱·劳伦号事件美国海军特种作战开发组（英语：United States Naval Special Warfare Development Group，缩写：NSWDG，常用缩写：DE
广延天女广延天女（天城体：उर्वशी，音译为优哩婆湿；字面意思为“宽广地延伸”）印度神话中一个著名的仙女，是一个具名的飞天女神。广延天女为神王因陀罗所属的天女。飞天女神是印度神话
塔西里·阿杰尔山脉阿杰尔的塔西利即阿杰尔高原（柏柏尔语：TasiliñAjjer，意为“有河流过的高原”，阿拉伯语：طاسيليناجر‎），是撒哈拉沙漠边缘的一处高原，位于阿尔及利亚与比利亚和尼日尔的交
箭箭，又称箭矢，指的是由弓或是弩所射出的武器，外型通常是一根坚硬的长杆，后方带有稳定装置，前方带有箭头。是人类自远古时代便开始利用的武器。除了作为武器用途外，另有一种“响箭”
沃罗涅日州坐标：50°51′32″N 39°51′52″E / 50.8589713°N 39.8644375°E / 50.8589713; 39.8644375沃罗涅日州（俄语：Воронежская область，罗马化：Voronezhskaya obl
圣保罗 (巴西)圣保罗（葡萄牙语：São Paulo，葡萄牙语发音：.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","
雅克·伊贝尔雅克·弗朗索瓦·安东·伊贝尔（法语：Jacques François Antoine Ibert，1890年8月15日－1962年2月5日），法国作曲家。早年就读于巴黎音乐学院，一战期间在海军服役，1919年获罗马大奖，到罗
蓝燕蓝燕可以指：