隔板法：修订间差异

以互动方式浏览历史

←上一版本

删除的内容添加的内容

可视化wikitext

行内

2022年7月29日 (五) 04:48的最新版本

隔板法是组合数学的方法，用来处理 $n$ 个无差别的球放进 $k$ 个不同的盒子的问题。可一般化为求不定方程的解数，并利用母函数解决问题。

隔板法与插空法的原理一样。^[1]

例子

现在有 $10$ 个球，要放进 $3$ 个盒子里

●●●●●●●●●●

隔 $2$ 个板子，把 $10$ 个球被隔开成 $3$ 个部份

●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、......

如此类推， $10$ 个球放进 $3$ 个盒子的方法总数为 ${\binom {10-1}{3-1}}={\binom {9}{2}}=36$

$n$ 个球放进 $k$ 个盒子的方法总数为 ${\binom {n-1}{k-1}}$

问题等价于求 $x_{1}+x_{2}+...+x_{k}=n$ 的可行解数，其中 $x_{1},x_{2},...,x_{k}$ 为正整数。

空盒子推广

现在有 $10$ 个球，要放进 $3$ 个盒子里，并允许空盒子。考虑 $10+3$ 个球的情况：

●|●|●●●●●●●●●●●、●|●●|●●●●●●●●●●、●|●●●|●●●●●●●●●、●|●●●●|●●●●●●●●、●|●●●●●|●●●●●●●、......

每个盒子的球都被拿走一个，得到一种情况，如此类推：

||●●●●●●●●●●、|●|●●●●●●●●●、|●●|●●●●●●●●、|●●●|●●●●●●●、|●●●●|●●●●●●、......

$n$ 个球放进 $k$ 个盒子的方法总数（允许空盒子），等同於 $n+k$ 个球放进 $k$ 个盒子的方法总数（不允许空盒子），即 ${\binom {n+k-1}{k-1}}$ ^[2]

问题等价于求 $x_{1}+x_{2}+...+x_{k}=n$ 的可行解数，其中 $x_{1},x_{2},...,x_{k}$ 为非负整数。

${\binom {n+k-1}{k-1}}$ 也是 $(a_{1}+a_{2}+...+a_{k})^{n}$ 展开式的项数 $\sum _{n_{1}+n_{2}+...+n_{k}=n}1$ ^[3]

参见

参考资料

^ 樊友年. “插空法”应用系列. 数学通报. 1995, (1) [2014-05-06]. （原始内容存档于2019-01-09）.
^ 徐浩全. “隔板法”在解不定方程方面的应用及其推广. 中学教学参考. 2010, (5) [2014-04-28]. （原始内容存档于2018-10-08）.
^ 徐国文. 多项式(a1+a2+a3+…+am)~n展开式的项数. 高中数学教与学. 2002, (7) [2014-07-15]. （原始内容存档于2016-03-04）.

[1] 樊友年. “插空法”应用系列. 数学通报. 1995, (1) [2014-05-06]. （原始内容存档于2019-01-09）.

[2] 徐浩全. “隔板法”在解不定方程方面的应用及其推广. 中学教学参考. 2010, (5) [2014-04-28]. （原始内容存档于2018-10-08）.

[3] 徐国文. 多项式(a1+a2+a3+…+am)~n展开式的项数. 高中数学教与学. 2002, (7) [2014-07-15]. （原始内容存档于2016-03-04）.

[1]

[2]

[3]

@@ 第1行： / 第1行： @@
+'''隔板法'''是[[组合数学]]的方法，用来处理<math>n</math>个无差别的球放进<math>k</math>个不同的盒子的问题。可一般化为求[[不定方程]]的解数，并利用[[母函数#不定方程的解数|母函数]]解决问题。
-{{refimprove|time=2014-04-28T09:37:58+00:00}}
-'''隔板法'''是[[组合数学]]的方法，用来处理n个球放进k个盒子的问题，并可推广到[[整数分拆]]与[[不定方程]]的可行解数问题。
+'''隔板法'''与[[插空法]]的原理一样。<ref>{{cite journal|author=樊友年|year=1995|title=“插空法”应用系列|journal=数学通报|issue=1|url=http://www.cnki.com.cn/Article/CJFDTotal-SXTB501.008.htm|access-date=2014-05-06|archive-date=2019-01-09|archive-url=https://web.archive.org/web/20190109182343/http://www.cnki.com.cn/Article/CJFDTotal-SXTB501.008.htm}}</ref>
-==思想==
-现在有10个球，要放进3个盒子里
+==例子==
+现在有<math>10</math>个球，要放进<math>3</math>个盒子里
 :●●●●●●●●●●
-隔2个板子，把10个球被隔开成3个部份
+隔<math>2</math>个板子，把<math>10</math>个球被隔开成<math>3</math>个部份
 :●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、......
-如此类推，10个球放进3个盒子的方法总数为<math>\binom {10-1}{3-1}=\binom {9}{2}=36</math>
-n个球放进k个盒子的方法总数为<math>\binom {n-1}{k-1}</math>
+如此类推，<math>10</math>个球放进<math>3</math>个盒子的方法总数为<math>\binom {10-1}{3-1}=\binom {9}{2}=36</math>
+<math>n</math>个球放进<math>k</math>个盒子的方法总数为<math>\binom {n-1}{k-1}</math>
 问题等价于求<math>x_1+x_2+...+x_k=n</math>的可行解数，其中<math>x_1,x_2,...,x_k</math>为[[正整数]]。
-==推广==
+==空盒子推广==
+现在有<math>10</math>个球，要放进<math>3</math>个盒子里，并允许空盒子。考虑<math>10+3</math>个球的情况：
-===允许空盒子===
-现在有10个球，要放进3个盒子里，并允许空盒子。考虑10+3个球的情况：
+:●|●|●●●●●●●●●●●、●|●●|●●●●●●●●●●、●|●●●|●●●●●●●●●、●|●●●●|●●●●●●●●、●|●●●●●|●●●●●●●、......
-:●|●|●●●●●●●●●●●
-从3个盒子里各拿走一个，得到一种情况，如此类推：
+每个盒子的球都被拿走一个，得到一种情况，如此类推：
 :||●●●●●●●●●●、|●|●●●●●●●●●、|●●|●●●●●●●●、|●●●|●●●●●●●、|●●●●|●●●●●●、......
-n个球放进k个盒子的方法总数（允许空盒子）为<math>\binom {n+k-1}{k-1}</math><ref>{{cite web|url=http://www.cnki.com.cn/Article/CJFDTotal-ZJCA201005032.htm|title=“隔板法”在解不定方程方面的应用及其推广}}</ref>
+<math>n</math>个球放进<math>k</math>个盒子的方法总数（允许空盒子），等同於<math>n+k</math>个球放进<math>k</math>个盒子的方法总数（不允许空盒子），即<math>\binom {n+k-1}{k-1}</math><ref>{{cite journal|author=徐浩全|year=2010|title=“隔板法”在解不定方程方面的应用及其推广|journal=中学教学参考|issue=5|url=http://www.cnki.com.cn/Article/CJFDTotal-ZJCA201005032.htm|access-date=2014-04-28|archive-date=2018-10-08|archive-url=https://web.archive.org/web/20181008191701/http://www.cnki.com.cn/Article/CJFDTotal-ZJCA201005032.htm}}</ref>
 问题等价于求<math>x_1+x_2+...+x_k=n</math>的可行解数，其中<math>x_1,x_2,...,x_k</math>为[[非负整数]]。
-===骰子===
-[[File:6sided dice.jpg|right|thumb]]
-现在有2颗[[骰子]]，求点数和为12的事件数，设2个骰子的点数为<math>x_1,x_2</math>，其中<math>x_1,x_2</math>包含1,2,3,4,5,6六个整数。
-:<math>x_1+x_2=12</math>
-个骰子的点数和为12'''只有6+6一种可能性'''，此时<math>\binom {12-1}{2-1}=11</math>此值与事实不符，因为骰子的点数不包含所有正整数。
-设<math>x_i</math>为所有正整数的事件为全集、<math>x_i</math>包含1,2,3,4,5,6的事件为<math>A_i</math>，<math>x_i</math>为大于6的所有正整数的事件为补集<math>\overline{A_i}</math>
-[[容斥原理]]与[[德·摩根定理]]结合，得到<math>\bigcap_{i=1}^n A_i =|U|-\sum_{i=1}^n\left|\overline{A_i}\right|+\sum_{i,j\,:\,i\neq j}\left|\overline{A_i}\cap \overline{A_j}\right|-\sum_{i,j,k\,:\,i\neq j\neq k}\left|\overline{A_i}\cap \overline{A_j}\cap \overline{A_k}\right|+\ \cdots\cdots\ \pm \left|\overline{A_1}\cap\cdots\cap \overline{A_n}\right|</math>
-设<math>y_i</math>为所有正整数，且<math>x_i=y_i+6</math>，考虑每一个情况：
-:<math>(y_1+6)+x_2=12,y_1+x_2=6</math>
-:<math>x_1+(y_2+6)=12,x_1+y_2=6</math>
-:<math>(y_1+6)+(y_2+6)=12,y_1+y_2=0</math>
-求和得到：
-:<math>\sum_{r=0}^2 (-1)^r \binom {2}{r} \binom {12-6r-1}{2-1}=11-2(5)+0=1</math>
-k个骰子的点数和为n的事件数为<math>\sum_{r=0}^k (-1)^r \binom {k}{r} \binom {n-6r-1}{k-1}</math>
-===一次不定方程===
-====逐项求和法====
-<math>a_1x_1+x_2+...+x_k=n</math>，其中<math>x_i</math>为正整数
-变换成<math>x_2+...+x_k=n-a_1x_1</math>，可行解数为<math>\sum_{r=1}^{\frac{n-k+1}{a_1}} \binom{n-a_1r-1}{k-2}</math><ref>{{cite web|url=http://www.cnki.com.cn/Article/CJFDTotal-HZJS201105007.htm|title=一次不定方程的解数问题讨论}}</ref>
-====剩余系换元法====
-利用[[剩余系]]换元凑出[[公约数]]，并观察方程。
-例如<math>2x_1+3x_2=90</math>
-设<math>x_1=3x_{11}-2,3x_{12}-1,3x_{13}</math>、<math>x_1=2x_{21}-1,2x_{22}</math>，其中<math>x_{11},x_{12},x_{13},x_{21},x_{22}</math>为正整数
-<math>\begin{cases}
-(3x_{11}-2)+3(2x_{21}-1)=90,6x_{11}+6x_{21}=97 \\
-(3x_{11}-2)+3(2x_{22})=90,6x_{11}+6x_{22}=94 \\
-(3x_{12}-1)+3(2x_{21}-1)=90,6x_{12}+6x_{21}=95 \\
-(3x_{12}-1)+3(2x_{22})=90,6x_{12}+6x_{22}=92 \\
-(3x_{13})+3(2x_{21}-1)=90,6x_{13}+6x_{21}=93 \\
-(3x_{13})+3(2x_{22})=90,x_{13}+x_{22}=15 \\
-\end{cases}</math>
+<math>\binom {n+k-1}{k-1}</math>也是<math>(a_1+a_2+...+a_k)^n</math>展开式的项数<math>\sum_{n_1+n_2+...+n_k=n} 1</math><ref>{{cite journal|author=徐国文|year=2002|title=多项式(a1+a2+a3+…+am)~n展开式的项数|journal=高中数学教与学|issue=7|url=http://www.cnki.com.cn/Article/CJFDTotal-GSJX200207017.htm|access-date=2014-07-15|archive-date=2016-03-04|archive-url=https://web.archive.org/web/20160304080248/http://www.cnki.com.cn/Article/CJFDTotal-GSJX200207017.htm}}</ref>
-:仅<math>x_{13}+x_{22}=15</math>有解，<math>2x_1+3x_2=90</math>的可行解数为<math>\binom{15-1}{2-1}=14</math>
 ==参见==
 *[[组合数]]
+*[[多项式定理]]
+*[[整数分拆]]
 ==参考资料==