CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
**格式**：英文/公式两边接汉字时请空格。

**内容**：建议找几个例题。

====== 隔板法（Stars and bars） ======

隔板法是解决某些组合问题的一种数学技术。每当要计算对相同对象进行分组的方式时，就可以使用隔板法。

===== 定理 =====

将$n$个相同对象放入$ k $个标记的盒子的方式有$$\binom {n+k-1} {n}。$$

证明包括将物体变成星星，然后使用条形分隔（因此得名）。例如。我们可以用$\bigstar | \bigstar \bigstar |~| \bigstar \bigstar$表示的情况如下：第一个盒子是一个对象，第二个盒子是两个对象，第三个是空的，最后一个盒子是两个对象。这是将5个对象分成4个盒子的一种方法。

显而易见，每个分区可以使用$n$个星号和$k-1$个条形表示，每个使用$n$个星号和$k-1$个条形图的星形和条形表示一个分区。因此，将$n$个相同对象放入$k$个标记的盒子的方法的数量与存在$n$个星型和$k-1$个条形的排列的数量相同。

===== 非负整数和的数量 =====

这个问题是定理的直接应用。

计算方程 $x_1 + x_2 + \dots + x_k = n,x_i \ge 0$的解数。

同样，我们可以使用隔板法表示解决方案。例如。对于$n = 4$，$k = 3$的解$1 + 3 + 0 = 4$可以用 $\bigstar | \bigstar \bigstar \bigstar |$表示。

不难看出，这正是隔板法定理。因此，解为$\binom {n + k-1} {n}$。

===== 下界整数和的数量 =====

可以很容易地将其扩展为具有不同下限的整数和。即我们想用$x_i \ge a_i$来计算方程$$x_1 + x_2 + \dots + x_k = n$$的解数。

替换$x_i':= x_i-a_i$之后，我们得到修改后的方程式$$(x_1' + a_i) + (x_2' + a_i) + \dots + (x_k' + a_k) = n$$ $$\Leftrightarrow ~ ~ x_1' + x_2' + \dots + x_k' = n - a_1 - a_2 - \dots - a_k$$ 和 $x_i' \ge 0$。

因此，我们将问题简化为$x_i'\ge 0$的简单情况，并且可以再次应用隔板法定理。
CVBB ACM Team

用户工具

站点工具

页面工具
