← 学习库 Discrete Mathematics (Levin) · 中英对照 目录

1.5 Stars and Bars 隔板法

本页译自 LibreTexts · Discrete Mathematics (Levin) 第 1.5 章。公式经 MathJax 渲染，自定义宏已注入。

Investigate! 探究！

Suppose you have some number of identical Rubik's cubes to distribute to your friends. Imagine you start with a single row of the cubes.

假设你有一些完全相同的魔方要分给朋友们。想象你先把这些魔方排成单独的一行。
  1. Find the number of different ways you can distribute the cubes provided:
    1. You have 3 cubes to give to 2 people.
    2. You have 4 cubes to give to 2 people.
    3. You have 5 cubes to give to 2 people.
    4. You have 3 cubes to give to 3 people.
    5. You have 4 cubes to give to 3 people.
    6. You have 5 cubes to give to 3 people.
  2. Make a conjecture about how many different ways you could distribute 7 cubes to 4 people. Explain.
  3. What if each person were required to get at least one cube? How would your answers change?
  1. 求在以下各种情形下分配魔方的不同方式的总数：
    1. 把 3 个魔方分给 2 个人。
    2. 把 4 个魔方分给 2 个人。
    3. 把 5 个魔方分给 2 个人。
    4. 把 3 个魔方分给 3 个人。
    5. 把 4 个魔方分给 3 个人。
    6. 把 5 个魔方分给 3 个人。
  2. 猜想一下：把 7 个魔方分给 4 个人有多少种不同的分法？并说明理由。
  3. 如果要求每个人至少分到一个魔方，你的答案会如何改变？

Consider the following counting problem:

考虑下面的计数问题：

You have 7 cookies to give to 4 kids. How many ways can you do this?

你有 7 块饼干要分给 4 个孩子。有多少种不同的分法？

Take a moment to think about how you might solve this problem. You may assume that it is acceptable to give a kid no cookies. Also, the cookies are all identical and the order in which you give out the cookies does not matter.

先花点时间想想你会如何求解。你可以假定：某个孩子一块饼干都分不到，也是允许的。此外，所有饼干都是完全相同的，并且你分发饼干的先后顺序无关紧要。

Before solving the problem, here is a wrong answer: You might guess that the answer should be $4^7$ because for each of the 7 cookies, there are 4 choices of kids to which you can give the cookie. This is reasonable, but wrong. To see why, consider a few possible outcomes: we could assign the first six cookies to kid A, and the seventh cookie to kid B. Another outcome would assign the first cookie to kid B and the six remaining cookies to kid A. Both outcomes are included in the $4^7$ answer. But for our counting problem, both outcomes are really the same – kid A gets six cookies and kid B gets one cookie.

在解题之前，先看一个错误的答案：你可能会猜答案是 $4^7$，因为对 7 块饼干中的每一块，都有 4 个孩子可供选择。这个想法合理，却是错误的。要明白原因，考虑几种可能的结果：我们可以把前六块饼干分给 A，第七块分给 B；另一种结果则是把第一块分给 B，剩下六块分给 A。这两种结果都包含在 $4^7$ 这个答案里。但对我们的计数问题而言，这两种结果其实是同一种——A 得到六块饼干，B 得到一块。

What do outcomes actually look like? How can we represent them? One approach would be to write an outcome as a string of four numbers like this:

\begin{equation*} 3112, \end{equation*}

结果究竟是什么样子？我们该如何表示它？一种办法是把一个结果写成一串由四个数字组成的序列，例如：

which represent the outcome in which the first kid gets 3 cookies, the second and third kid each get 1 cookie, and the fourth kid gets 2 cookies. Represented this way, the order in which the numbers occur matters. 1312 is a different outcome, because the first kid gets a one cookie instead of 3. Each number in the string can be any integer between 0 and 7. But the answer is not $7^4\text{.}$ We need the sum of the numbers to be 7.

它表示第一个孩子得到 3 块饼干、第二个和第三个孩子各得 1 块、第四个孩子得到 2 块这样一种结果。以这种方式表示时，数字出现的顺序是有意义的。1312 是另一种不同的结果，因为第一个孩子得到的是 1 块而不是 3 块。序列中每个数字都可以是 0 到 7 之间的任意整数。但答案并非 $7^4\text{。}$ 我们需要的是这些数字的和等于 7。

Another way we might represent outcomes is to write a string of seven letters:

\begin{equation*} \mbox{ABAADCD} , \end{equation*}

另一种表示结果的方式，是写下一串由七个字母组成的序列：

which represents that the first cookie goes to kid A, the second cookie goes to kid B, the third and fourth cookies go to kid A, and so on. In fact, this outcome is identical to the previous one—A gets 3 cookies, B and C get 1 each and D gets 2. Each of the seven letters in the string can be any of the 4 possible letters (one for each kid), but the number of such strings is not $4^7\text{,}$ because here order does not matter. In fact, another way to write the same outcome is

它表示第一块饼干给了 A，第二块给了 B，第三、四块给了 A，依此类推。事实上，这个结果与上一个完全相同——A 得到 3 块，B 和 C 各得 1 块，D 得到 2 块。串中七个字母的每一个都可以是 4 个可能字母中的任意一个（每个孩子对应一个），但这种字符串的个数并不是 $4^7\text{，}$因为在这里顺序不重要。事实上，同一个结果还可以写成

\begin{equation*} \mbox{AAABCDD} . \end{equation*}

This will be the preferred representation of the outcome. Since we can write the letters in any order, we might as well write them in alphabetical order for the purposes of counting. So we will write all the A's first, then all the B's, and so on.

这将是该结果首选的表示方式。既然字母可以按任意顺序排列，为了计数方便，我们不妨按字母表顺序书写，即先写所有的 A，再写所有的 B，依此类推。

Now think about how you could specify such an outcome. All we really need to do is say when to switch from one letter to the next. In terms of cookies, we need to say after how many cookies do we stop giving cookies to the first kid and start giving cookies to the second kid. And then after how many do we switch to the third kid? And after how many do we switch to the fourth? So yet another way to represent an outcome is like this:

\begin{equation*} ***|*|*|** \end{equation*}

现在想想，你该如何确定这样一个结果。我们真正需要做的，只是说明何时从一种字母切换到下一种。用饼干来说，我们需要说明：在发完多少块饼干之后，停止发给第一个孩子、开始发给第二个孩子；再发完多少块之后切换到第三个孩子；又再发完多少块之后切换到第四个孩子？于是表示结果的另一种方式是这样的：

Three cookies go to the first kid, then we switch and give one cookie to the second kid, then switch, one to the third kid, switch, two to the fourth kid. Notice that we need 7 stars and 3 bars – one star for each cookie, and one bar for each switch between kids, so one fewer bars than there are kids (we don't need to switch after the last kid – we are done).

三块饼干给第一个孩子，然后切换，给第二个孩子一块；再切换，给第三个孩子一块；再切换，给第四个孩子两块。注意，我们需要 7 颗星和 3 道栏——每颗星对应一块饼干，每道栏对应一次孩子之间的切换，因此栏的数量比孩子数少一道（最后一个孩子之后无需再切换——分配就结束了）。

Why have we done all of this? Simple: to count the number of ways to distribute 7 cookies to 4 kids, all we need to do is count how many stars and bars charts there are. But a stars and bars chart is just a string of symbols, some stars and some bars. If instead of stars and bars we would use 0's and 1's, it would just be a bit string. We know how to count those.

我们为什么要做这一切？原因很简单：要统计把 7 块饼干分给 4 个孩子的分法数，我们只需数清有多少个隔板图。而一个隔板图不过是一串符号，其中有些是星、有些是栏。如果不用星和栏，而改用 0 和 1，它就只是一串比特串。而那种串我们是会数的。

Before we get too excited, we should make sure that really any string of (in our case) 7 stars and 3 bars corresponds to a different way to distribute cookies to kids. In particular consider a string like this:

\begin{equation*} |***||**** \end{equation*}

在过于兴奋之前，我们应当确认：真的任意一串（在我们的情形中是）7 颗星和 3 道栏，都对应一种不同的分饼干方式。特别地，考虑下面这样一串：

Does that correspond to a cookie distribution? Yes. It represents the distribution in which kid A gets 0 cookies (because we switch to kid B before any stars), kid B gets three cookies (three stars before the next bar), kid C gets 0 cookies (no stars before the next bar) and kid D gets the remaining 4 cookies. No matter how the stars and bars are arranged, we can distribute cookies in that way. Also, given any way to distribute cookies, we can represent that with a stars and bars chart. For example, the distribution in which kid A gets 6 cookies and kid B gets 1 cookie has the following chart:

它对应的是一种分饼干方案吗？是的。它表示：A 得到 0 块饼干（因为在有任何星之前就切换到了 B），B 得到 3 块（在下一道栏之前有 3 颗星），C 得到 0 块（在下一道栏之前没有星），D 得到剩下的 4 块。无论星和栏如何排列，我们都能按那种方式分配饼干。反过来，给定任意一种分饼干的方式，我们也都能用一个隔板图来表示它。例如，A 得 6 块、B 得 1 块这种分配方式，对应的图如下：

\begin{equation*} ******|*|| \end{equation*}

After all that work we are finally ready to count. Each way to distribute cookies corresponds to a stars and bars chart with 7 stars and 3 bars. So there are 10 symbols, and we must choose 3 of them to be bars. Thus:

在做了这么多工作之后，我们终于可以开始计数了。每一种分饼干的方式都对应一个含 7 颗星、3 道栏的隔板图。因此共有 10 个符号，我们必须从中选出 3 个作为栏。于是：

\begin{equation*} \mbox{ There are } {10 \choose 3}\mbox{ ways to distribute 7 cookies to 4 kids.} \end{equation*}

While we are at it, we can also answer a related question: how many ways are there to distribute 7 cookies to 4 kids so that each kid gets at least one cookie? What can you say about the corresponding stars and bars charts? The charts must start and end with at least one star (so that kids A and D) get cookies, and also no two bars can be adjacent (so that kids B and C are not skipped). One way to assure this is to only place bars in the spaces between the stars. With 7 stars, there are 6 spots between the stars, so we must choose 3 of those 6 spots to fill with bars. Thus there are ${6 \choose 3}$ ways to distribute 7 cookies to 4 kids giving at least one cookie to each kid.

顺带，我们还可以回答一个相关问题：把 7 块饼干分给 4 个孩子，且每个孩子至少分到一块，有多少种分法？对应的隔板图有什么特点？这些图必须以至少一颗星开头、以至少一颗星结尾（这样 A 和 D 才能分到饼干），而且任意两道栏不能相邻（这样 B 和 C 才不会被跳过）。保证这一点的一种办法是：只把栏放在星与星之间的空隙中。7 颗星之间有 6 个空隙，因此我们必须从这 6 个空隙中选出 3 个填入栏。于是，把 7 块饼干分给 4 个孩子、且每人至少一块的分法有 ${6 \choose 3}$ 种。

Another (and more general) way to approach this modified problem is to first give each kid one cookie. Now the remaining 3 cookies can be distributed to the 4 kids without restrictions. So we have 3 stars and 3 bars for a total of 6 symbols, 3 of which must be bars. So again we see that there are ${6 \choose 3}$ ways to distribute the cookies.

处理这个变形问题的另一种（也更一般的）办法，是先给每个孩子一块饼干。剩下的 3 块饼干便可以在不加限制的情况下分给 4 个孩子。于是我们有 3 颗星和 3 道栏，共 6 个符号，其中 3 个必须是栏。所以我们再次看到，分配饼干的方式有 ${6 \choose 3}$ 种。

Stars and bars can be used in counting problems other than kids and cookies. Here are a few examples:

隔板法不仅可以用于孩子分饼干这类问题，还可用于其他计数问题。下面举几个例子：

Example 1

示例 1

Your favorite mathematical pizza chain offers 10 toppings. How many pizzas can you make if you are allowed 6 toppings? The order of toppings does not matter but now you are allowed repeats. So one possible pizza is triple sausage, double pineapple, and onions.

你最爱的数学披萨连锁店提供 10 种配料。如果允许选 6 种配料，你能做出多少种披萨？配料的顺序无关紧要，但允许重复。所以有这样一种可能的披萨：三倍香肠、双倍菠萝加洋葱。

Solution

解答

We get 6 toppings (counting possible repeats). Represent each of these toppings as a star. Think of going down the menu one topping at a time: you see anchovies first, and skip to the next, sausage. You say yes to sausage 3 times (use 3 stars), then switch to the next topping on the list. You keep skipping until you get to pineapple, which you say yes to twice. Another switch and you are at onions. You say yes once. Then you keep switching until you get to the last topping, never saying yes again (since you already have said yes 6 times. There are 10 toppings to choose from, so we must switch from considering one topping to the next 9 times. These are the bars.

我们选 6 种配料（重复计入）。把每一种配料表示为一颗星。想象你顺着菜单一次看一种配料：你先看到鳀鱼，跳到下一种——香肠。你对香肠说「要」三次（用 3 颗星），然后切换到菜单上的下一种配料。你一直跳过，直到遇到菠萝，对它说「要」两次。再切换一次，你到了洋葱。你说「要」一次。然后你不断切换，直到最后一种配料，此后再也不说「要」（因为你已经说了 6 次「要」）。可供选择的配料共有 10 种，因此我们必须从考虑一种配料切换到下一种配料共 9 次。这些切换就是「栏」。

Now that we are confident that we have the right number of stars and bars, we answer the question simply: there are 6 stars and 9 bars, so 15 symbols. We need to pick 9 of them to be bars, so there number of pizzas possible is

既然已经确定星与栏的数目无误，我们直接回答问题：共有 6 颗星和 9 道栏，即 15 个符号。我们需要从中选出 9 个作为栏，因此可能做出的披萨数量为

\begin{equation*} {15 \choose 9}. \end{equation*}

Example 2

示例 2

How many 7 digit phone numbers are there in which the digits are non-increasing? That is, every digit is less than or equal to the previous one.

有多少个 7 位电话号码，其各位数字是非递增的？也就是说，每一位数字都小于或等于它前一位的数字。

Solution

解答

We need to decide on 7 digits so we will use 7 stars. The bars will represent a switch from each possible single digit number down the next smaller one. So the phone number 866-5221 is represented by the stars and bars chart

我们需要确定 7 个数字，因此用 7 颗星。栏表示从一个可能的单个数字向下切换到下一个更小的数字。于是电话号码 866-5221 可用如下隔板图表示：

\begin{equation*} |*||**|*|||**|*| \end{equation*}

There are 10 choices for each digit (0-9) so we must switch between choices 9 times. We have 7 stars and 9 bars, so the total number of phone numbers is

每一位数字都有 10 种选择（0–9），因此必须在各选择之间切换 9 次。我们有 7 颗星和 9 道栏，所以电话号码的总数为

\begin{equation*} {16 \choose 9}. \end{equation*}

Example 3

示例 3

How many integer solutions are there to the equation

下面这个方程有多少个整数解？

\begin{equation*} x_1 + x_2 + x_3 + x_4 + x_5 = 13. \end{equation*}

(An integer solution to an equation is a solution in which the unknown must have an integer value.)

（方程的解如果要求未知数取整数值，就称为该方程的整数解。）
  1. where $x_i \ge 0$ for each $x_i\text{?}$
  2. where $x_i > 0$ for each $x_i\text{?}$
  3. where $x_i \ge 2$ for each $x_i\text{?}$
  1. 每个 $x_i \ge 0$ 的情形？
  2. 每个 $x_i > 0$ 的情形？
  3. 每个 $x_i \ge 2$ 的情形？

Solution

解答

This problem is just like giving 13 cookies to 5 kids. We need to say how many of the 13 units go to each of the 5 variables. In other words, we have 13 stars and 4 bars (the bars are like the "+" signs in the equation).

这个问题就等同于把 13 块饼干分给 5 个孩子。我们需要说明这 13 个单位中有多少个分配给 5 个变量中的每一个。换句话说，我们有 13 颗星和 4 道栏（栏就像方程中的「+」号）。
  1. If $x_i$ can be 0 or greater, we are in the standard case with no restrictions. So 13 stars and 4 bars can be arranged in ${17 \choose 4}$ ways.
  2. Now each variable must be at least 1. So give one unit to each variable to satisfy that restriction. Now there are 8 stars left, and still 4 bars, so the number of solutions is ${12 \choose 4}\text{.}$
  3. Now each variable must be 2 or greater. So before any counting, give each variable 2 units. We now have 3 remaining stars and 4 bars, so there are ${7 \choose 4}$ solutions.
  1. 若 $x_i$ 可以取 0 或更大的值，那就是无限制的标准情形。于是 13 颗星与 4 道栏的排列方式有 ${17 \choose 4}$ 种。
  2. 现在每个变量至少为 1。因此先给每个变量分配 1 个单位以满足该限制。此时还剩 8 颗星，栏仍有 4 道，所以解的个数为 ${12 \choose 4}\text{。}$
  3. 现在每个变量必须至少为 2。因此计数之前，先给每个变量分配 2 个单位。此时还剩 3 颗星和 4 道栏，所以解的个数为 ${7 \choose 4}$。

Counting with Functions 用函数计数

Many of the counting problems in this section might at first appear to be examples of counting functions. After all, when we try to count the number of ways to distribute cookies to kids, we are assigning each cookie to a kid, just like you assign elements of the domain of a function to elements in the codomain. However, the number of ways to assign 7 cookies to 4 kids is ${10 \choose 7} = 120\text{,}$ while the number of functions $f: \{1,2,3,4,5,6,7\} \to \{a,b,c,d\}$ is $4^7 = 16384\text{.}$ What is going on here?

本章中的许多计数问题，初看起来似乎都是在计数函数。毕竟，当我们试图统计把饼干分给孩子的不同方式时，我们是在把每块饼干分配给孩子，正如你把函数定义域中的元素分配给上域中的元素。然而，把 7 块饼干分给 4 个孩子的方式数为 ${10 \choose 7} = 120\text{，}$而函数 $f: \{1,2,3,4,5,6,7\} \to \{a,b,c,d\}$ 的个数为 $4^7 = 16384\text{。}$ 这是怎么回事？

When we count functions, we consider the following two functions, for example, to be different:

在计数函数时，例如，我们认为下面这两个函数是不同的：

$f = \twoline{1 & 2 & 3 & 4& 5 & 6 & 7}{a & b & c & c & c & c & c} \qquad g = \twoline{1 & 2 & 3 & 4& 5 & 6 & 7}{b & a & c & c & c & c & c}.$

But these two functions would correspond to the same cookie distribution: kids $a$ and $b$ each get one cookie, kid $c$ gets the rest (and none for kid $d$).

但这两个函数对应的是同一个饼干分配方案：孩子 $a$ 和 $b$ 各得一块饼干，孩子 $c$ 得到其余的（孩子 $d$ 一块也没有）。

The point: elements of the domain are distinguished, cookies are indistinguishable. This is analogous to the distinction between permutations (like counting functions) and combinations (not).

关键在于：定义域中的元素是可区分的，而饼干是不可区分的。这正对应于排列（好比计数函数，元素可区分）与组合（并非如此，元素不可区分）之间的区别。