1.2 Binomial Coefficients 二项式系数

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

Investigate! 探究！

In chess, a rook can move only in straight lines (not diagonally). Fill in each square of the chess board below with the number of different shortest paths the rook, in the upper left corner, can take to get to that square. For example, one square is already filled in. There are six different paths from the rook to the square: DDRR (down down right right), DRDR, DRRD, RDDR, RDRD and RRDD.

在国际象棋中，车（rook）只能沿直线移动（不能斜走）。请在下方棋盘每一格中填入：位于左上角的车到达该格的不同最短路径数。例如，已有一个格子填好了。从车到该格共有六条不同路径：DDRR（下下右右）、DRDR、DRRD、RDDR、RDRD 以及 RRDD。

Here are some apparently different discrete objects we can count: subsets, bit strings, lattice paths, and binomial coefficients. We will give an example of each type of counting problem (and say what these things even are). As we will see, these counting problems are surprisingly similar.

以下是一些看似不同、却都可计数的离散对象：子集、位串、格路径，以及二项式系数。我们将为每一类计数问题各举一例（并说明这些概念究竟是什么）。正如我们将看到的，这些计数问题出奇地相似。

Subsets 子集

Subsets should be familiar, otherwise read over Section 0.3 again. Suppose we look at the set $A = \{1,2,3,4,5\}$. How many subsets of $A$ contain exactly 3 elements?

子集应是熟悉的概念，否则请重读第 0.3 节。假设我们考虑集合 $A = \{1,2,3,4,5\}$。集合 $A$ 有多少个恰好含 3 个元素的子集？

First, a simpler question: How many subsets of $A$ are there total? In other words, what is $|\pow(A)|$ (the cardinality of the power set of $A$)? Think about how we would build a subset. We need to decide, for each of the elements of $A\text{,}$ whether or not to include the element in our subset. So we need to decide “yes” or “no” for the element 1. And for each choice we make, we need to decide “yes” or “no” for the element 2. And so on. For each of the 5 elements, we have 2 choices. Therefore the number of subsets is simply $2\cdot 2\cdot 2 \cdot 2\cdot 2 = 2^5$ (by the multiplicative principle).

首先问一个更简单的问题：集合 $A$ 一共有多少个子集？换言之，$|\pow(A)|$ 是多少（即 $A$ 的幂集的基数）？想想我们该如何构造一个子集。对 $A$ 中的每一个元素，我们都要决定是否把它纳入子集。所以对元素 1，我们要决定「是」或「否」；而每做一次选择，又要对元素 2 决定「是」或「否」，依此类推。对 5 个元素中的每一个，都有 2 种选择。因此子集的总数就是 $2\cdot 2\cdot 2 \cdot 2\cdot 2 = 2^5$（依据乘法原理）。

Of those 32 subsets, how many have 3 elements? This is not obvious. Note that we cannot just use the multiplicative principle. Maybe we want to say we have 2 choices (yes/no) for the first element, 2 choices for the second, 2 choices for the third, and then only 1 choice for the other two. But what if we said “no” to one of the first three elements? Then we would have two choices for the 4th element. What a mess!

在这 32 个子集中，有多少个含 3 个元素？这并不显然。注意，我们不能简单地套用乘法原理。也许我们会想：对第一个元素有 2 种选择（是/否），第二个有 2 种，第三个有 2 种，而剩下两个都只有 1 种选择。可是，如果我们对前三个元素中的某一个说了「否」，那对第 4 个元素就有 2 种选择。一团乱麻！

Another (bad) idea: we need to pick three elements to be in our subset. There are 5 elements to choose from. So there are 5 choices for the first element, and for each of those 4 choices for the second, and then 3 for the third (last) element. The multiplicative principle would say then that there are a total of $5 \cdot 4 \cdot 3 = 60$ ways to select the 3 element subset. But this cannot be correct ($60 > 32$ for one thing). One of the outcomes we would get from these choices would be the set $\{3,2,5\}\text{,}$ by choosing the element 3 first, then the element 2, then the element 5. Another outcome would be $\{5,2,3\}$ by choosing the element 5 first, then the element 2, then the element 3. But these are the same set! We can correct this by dividing: for each set of three elements, there are 6 outcomes counted among our 60 (since there are 3 choices for which element we list first, 2 for which we list second, and 1 for which we list last). So we expect there to be 10 3-element subsets of $A$.

另一个（错误）的想法：我们需要挑出三个元素放入子集。可供选择的元素有 5 个。于是第一个元素有 5 种选择，在此基础上第二个有 4 种，第三个（最后一个）有 3 种。按乘法原理，选出这个 3 元子集的方式共有 $5 \cdot 4 \cdot 3 = 60$ 种。但这不可能正确（单凭 $60 > 32$ 便可见）。这样选出来的结果中，会包含集合 $\{3,2,5\}$，即先选元素 3、再选 2、再选 5。另一种结果是 $\{5,2,3\}$，即先选 5、再选 2、再选 3。可这两个结果是同一个集合！我们可以通过除法纠正：对每个三元集合，在那 60 种结果中都被数了 6 次（因为列出三个元素时，第一个有 3 种选法、第二个有 2 种、第三个有 1 种）。所以我们预期 $A$ 的 3 元子集共有 10 个。

Is this right? Well, we could list out all 10 of them, being very systematic in doing so, to make sure we don't miss any or list any twice. Or we could try to count how many subsets of $A$ don't have 3 elements in them. How many have no elements? Just 1 (the empty set). How many have 5? Again, just 1. These are the cases in which we say “no” to all elements, or “yes” to all elements. Okay, what about the subsets which contain a single element? There are 5 of these. We must say “yes” to exactly one element, and there are 5 to choose from. This is also the number of subsets containing 4 elements. Those are the ones for which we must say “no” to exactly one element.

这正确吗？我们可以把全部 10 个系统列出，确保不重不漏。或者，我们可以转而计数 $A$ 中不含 3 个元素的子集。含 0 个元素的子集有几个？只有 1 个（空集）。含 5 个元素的呢？同样只有 1 个。这两种情形分别对应：对所有元素都说「否」，或对都说「是」。那么，只含一个元素的子集呢？共有 5 个——我们必须恰好对一个元素说「是」，而可供选择的元素有 5 个。这也等于含 4 个元素的子集个数，因为那正是恰好对一个元素说「否」的情形。

So far we have counted 12 of the 32 subsets. We have not yet counted the subsets with cardinality 2 and with cardinality 3. There are a total of 20 subsets left to split up between these two groups. But the number of each must be the same! If we say “yes” to exactly two elements, that can be accomplished in exactly the same number of ways as the number of ways we can say “no” to exactly two elements. So the number of 2-element subsets is equal to the number of 3-element subsets. Together there are 20 of these subsets, so 10 each.

至此我们已数出 32 个子集中 12 个。含 2 个元素与含 3 个元素的子集尚未数。两类合计还剩 20 个子集待分配。但这两类的数目必然相等！因为恰好对两个元素说「是」的方式数，恰好等于恰好对两个元素说「否」的方式数。于是 2 元子集的个数等于 3 元子集的个数。两类合计 20 个，故各为 10 个。

Number of elements	0	1	2	3	4	5
Number of subsets	1	5	10	10	5	1

上表汇总了各元素个数对应的子集个数：当元素个数为 0、1、2、3、4、5 时，子集个数分别为 1、5、10、10、5、1。

Bit Strings 位串

“Bit” is short for “binary digit,” so a bit string is a string of binary digits. The binary digits are simply the numbers 0 and 1. All of the following are bit strings:

「位」（bit）是「二进制数字」（binary digit）的简称，因此位串（bit string）就是由二进制数字组成的串。二进制数字就是 0 和 1。以下都是位串：

\begin{equation*} 1001 \quad 0 \quad 1111 \quad 1010101010 \end{equation*}

The number of bits (0's or 1's) in the string is the length of the string; the strings above have lengths 4, 1, 4, and 10 respectively. We also can ask how many of the bits are 1's. The number of 1's in a bit string is the weight of the string; the weights of the above strings are 2, 0, 4, and 5 respectively.

串中位（0 或 1）的个数称为该串的长度（length）；上面的串长度分别为 4、1、4、10。我们也可以问其中有多少个位是 1。位串中 1 的个数称为该串的权（weight）；上面各串的权分别为 2、0、4、5。

Definition: Bit Strings 定义：位串

An $n$-bit string is a bit string of length $n$. That is, it is a string containing $n$ symbols, each of which is a bit, either 0 or 1.
The weight of a bit string is the number of 1's in it.
$\B^n$ is the set of all $n$-bit strings.
$\B^n_k$ is the set of all $n$-bit strings of weight $k$.

长度为 $n$ 的位串称为 $n$ 位串（$n$-bit string）。也就是说，它是由 $n$ 个符号组成的串，每个符号都是 0 或 1 的位。
位串的权是其内部 1 的个数。
$\B^n$ 是所有 $n$ 位串构成的集合。
$\B^n_k$ 是所有权为 $k$ 的 $n$ 位串构成的集合。

For example, the elements of the set $\B^3_2$ are the bit strings 011, 101, and 110. Those are the only strings containing three bits exactly two of which are 1's.

例如，集合 $\B^3_2$ 的元素是位串 011、101 和 110。它们正是仅有的、含三个位且其中恰有两个为 1 的串。

The counting questions: How many bit strings have length 5? How many of those have weight 3? In other words, we are asking for the cardinalities $|\B^5|$ and $|\B^5_3|$.

计数问题：长度为 5 的位串有多少个？其中权为 3 的又有多少个？换言之，我们要求的是基数 $|\B^5|$ 与 $|\B^5_3|$。

To find the number of 5-bit strings is straight forward. We have 5 bits, and each can either be a 0 or a 1. So there are 2 choices for the first bit, 2 choices for the second, and so on. By the multiplicative principle, there are $2 \cdot 2 \cdot 2\cdot 2 \cdot 2 = 2^5 = 32$ such strings.

求 5 位串的个数很直接。我们有 5 个位，每个位可以取 0 或 1。于是第一个位有 2 种选择，第二个有 2 种，依此类推。根据乘法原理，这样的串共有 $2 \cdot 2 \cdot 2\cdot 2 \cdot 2 = 2^5 = 32$ 个。

Finding the number of 5-bit strings of weight 3 is harder. Think about how such a string could start. The first bit must be either a 0 or a 1. In the first case (the string starts with a 0), we must then decide on four more bits. To have a total of three 1's, among those four remaining bits there must be three 1's. To count all of these strings, we must include all 4-bit strings of weight 3. In the second case (the string starts with a 1), we still have four bits to choose, but now only two of them can be 1's, so we should look at all the 4-bit strings of weight 2. So the strings in $\B^5_3$ all have the form $1\B^4_2$ (that is, a 1 followed by a string from $\B^4_2$) or $0\B^4_3$. These two sets are disjoint, so we can use the additive principle:

求权为 3 的 5 位串个数则更难。考虑这样的串可能以什么开头。第一个位只能是 0 或 1。第一种情况（串以 0 开头）下，我们还要决定另外四个位。要使 1 的总数为 3，那四个剩余位中必须有三个是 1。要数出所有这些串，我们必须计入全部权为 3 的 4 位串。第二种情况（串以 1 开头）下，仍要选四个位，但其中至多两个能为 1，所以应考察全部权为 2 的 4 位串。因此 $\B^5_3$ 中的串都具有 $1\B^4_2$（即先是一个 1，后接 $\B^4_2$ 中的一个串）或 $0\B^4_3$ 的形式。这两个集合不相交，故可用加法原理：

\begin{equation*} |\B^5_3| = |\B^4_2| + |\B^4_3|. \end{equation*}

This is an example of a recurrence relation. We represented one instance of our counting problem in terms of two simpler instances of the problem. If only we knew the cardinalities of $\B^4_2$ and $\B^4_3$. Repeating the same reasoning,

这是一个递推关系（recurrence relation）的例子。我们把计数问题的一个实例，表示成该问题两个更简单的实例。若我们晓得 $\B^4_2$ 与 $\B^4_3$ 的基数就好了。重复同样的推理，

\begin{equation*} |\B^4_2| = |\B^3_1| + |\B^3_2| \quad \mbox{and} \quad |\B^4_3| = |\B^3_2| + |\B^3_3|. \end{equation*}

We can keep going down, but this should be good enough. Both $\B^3_1$ and $\B^3_2$ contain 3 bit strings: we must pick one of the three bits to be a 1 (three ways to do that) or one of the three bits to be a 0 (three ways to do that). Also, $\B^3_3$ contains just one string: 111. Thus $|\B^4_2| = 6$ and $|\B^4_3| = 4\text{,}$ which puts $\B^5_3$ at a total of 10 strings.

我们还可以继续往下，但到此应该够了。$\B^3_1$ 与 $\B^3_2$ 都恰含 3 个位串：我们必须从三个位中选一个作为 1（有 3 种选法），或从三个位中选一个作为 0（也有 3 种选法）。此外，$\B^3_3$ 只含一个串：111。于是 $|\B^4_2| = 6$，而 $|\B^4_3| = 4\text{，}$进而 $\B^5_3$ 共有 10 个位串。

But wait —32 and 10 were the answers to the counting questions about subsets. Coincidence? Not at all. Each bit string can be thought of as a code for a subset. For the set $A = \{1,2,3,4,5\}\text{,}$ we would use 5-bit strings, one bit for each element of $A$. Each bit in the string is a 0 if its corresponding element of $A$ is not in the subset, and a 1 if the element of $A$ is in the subset. Remember, deciding the subset amounted to a sequence of five yes/no votes for the elements of $A$. Instead of yes, we put a 1; instead of no, we put a 0.

可是稍等——32 和 10 正是关于子集的那些计数问题的答案。巧合吗？绝非如此。每个位串都可以看作一个子集的编码。对集合 $A = \{1,2,3,4,5\}\text{，}$我们可用 5 位串，串中每一位对应 $A$ 的一个元素。若 $A$ 中对应元素不在子集里，则该位为 0；若在，则为 1。回想一下，确定子集等价于对 $A$ 的元素依次投出五次「是/否」票。我们只是把「是」换成 1、把「否」换成 0 罢了。

For example, the bit string 11001 represents the subset $\{1,2,5\}$ since the first, second and fifth bits are 1's. The subset $\{3,5\}$ would be coded by the string 00101. What we really have here is a bijection from $\pow(A)$ to $\B^5$.

例如，位串 11001 表示子集 $\{1,2,5\}$，因为第一、二、五位都是 1。子集 $\{3,5\}$ 则由串 00101 编码。我们这里得到的其实是从 $\pow(A)$ 到 $\B^5$ 的一个双射。

Now for a subset to contain exactly three elements, the corresponding bit string must contain exactly three 1's. In other words, the weight must be 3. Thus counting the number of 3-element subsets of $A$ is the same as counting the number 5-bit strings of weight 3.

现在，一个子集要恰好含三个元素，对应的位串就必须恰好含三个 1。换言之，其权必须为 3。因此，计数 $A$ 的 3 元子集个数，等同于计数权为 3 的 5 位串个数。

Lattice Paths 格路径

The integer lattice is the set of all points in the Cartesian plane for which both the $x$ and $y$ coordinates are integers. If you like to draw graphs on graph paper, the lattice is the set of all the intersections of the grid lines.

整数格（integer lattice）是笛卡尔平面中所有横、纵坐标均为整数的点组成的集合。如果你喜欢在方格纸上画图，整数格就是所有网格线的交点。

A lattice path is one of the shortest possible paths connecting two points on the lattice, moving only horizontally and vertically. For example, here are three possible lattice paths from the points $(0,0)$ to $(3,2)\text{:}$

格路径（lattice path）是连接格上两点、只沿水平与竖直方向行进的最短可能路径之一。例如，下面是从点 $(0,0)$ 到 $(3,2)$ 的三条可能格路径：

Notice to ensure the path is the shortest possible, each move must be either to the right or up. Additionally, in this case, note that no matter what path we take, we must make three steps right and two steps up. No matter what order we make these steps, there will always be 5 steps. Thus each path has length 5.

注意，为确保路径尽可能短，每一步都必须向右或向上。此外，在此情形下，不论走哪条路径，都必须向右走三步、向上走两步。无论这些步以何种顺序进行，总是恰好 5 步。因此每条路径的长度都是 5。

The counting question: how many lattice paths are there between $(0,0)$ and $(3,2)\text{?}$ We could try to draw all of these, or instead of drawing them, maybe just list which direction we travel on each of the 5 steps. One path might be RRUUR, or maybe UURRR, or perhaps RURRU (those correspond to the three paths drawn above). So how many such strings of R's and U's are there?

计数问题：从 $(0,0)$ 到 $(3,2)$ 共有多少条格路径？我们可以尝试把它们全画出来；或者，不画出来，只列出每一步的方向。一条路径可能是 RRUUR，也可能是 UURRR，或是 RURRU（这些对应上面画的三条路径）。那么，这样的由 R 和 U 组成的串一共有多少个？

Notice that each of these strings must contain 5 symbols. Exactly 3 of them must be R's (since our destination is 3 units to the right). This seems awfully familiar. In fact, what if we used 1's instead of R's and 0's instead of U's? Then we would just have 5-bit strings of weight 3. There are 10 of those, so there are 10 lattice paths from $(0,0)$ to $(3,2)$.

注意，每个这样的串都恰含 5 个符号。其中恰有 3 个必须是 R（因为目的地在右侧 3 个单位处）。这听起来无比耳熟。其实，若我们把 R 换成 1、把 U 换成 0 呢？那样就只是权为 3 的 5 位串罢了。这样的串有 10 个，故从 $(0,0)$ 到 $(3,2)$ 的格路径也有 10 条。

The correspondence between bit strings and lattice paths does not stop there. Here is another way to count lattice paths. Consider the lattice shown below:

位串与格路径之间的对应还不止于此。下面是另一种计数格路径的方法。考虑下图所示格子：

Any lattice path from $(0,0)$ to $(3,2)$ must pass through exactly one of $A$ and $B$. The point $A$ is 4 steps away from $(0,0)$ and two of them are towards the right. The number of lattice paths to $A$ is the same as the number of 4-bit strings of weight 2, namely 6. The point $B$ is 4 steps away from $(0,0)$, but now 3 of them are towards the right. So the number of paths to point $B$ is the same as the number of 4-bit strings of weight 3, namely 4. So the total number of paths to $(3,2)$ is just $6+4$. This is the same way we calculated the number of 5-bit strings of weight 3. The point: the exact same recurrence relation exists for bit strings and for lattice paths.

任何从 $(0,0)$ 到 $(3,2)$ 的格路径都必然恰好经过 $A$、$B$ 之一。点 $A$ 距离 $(0,0)$ 为 4 步，其中两步向右。到 $A$ 的格路径数，等于权为 2 的 4 位串个数，即 6。点 $B$ 距离 $(0,0)$ 也是 4 步，但其中三步向右。所以到 $B$ 的路径数，等于权为 3 的 4 位串个数，即 4。于是到达 $(3,2)$ 的路径总数就是 $6+4$。这正是我们之前计算权为 3 的 5 位串个数的方法。要点在于：位串与格路径满足完全相同的递推关系。

Binomial Coefficients 二项式系数

Binomial coefficients are the coefficients in the expanded version of a binomial, such as $(x+y)^5$. What happens when we multiply such a binomial out? We will expand $(x+y)^n$ for various values of $n$. Each of these are done by multiplying everything out (i.e., FOIL-ing) and then collecting like terms.

二项式系数（binomial coefficients）是二项式展开式中的系数，例如 $(x+y)^5$。当我们把这个二项式乘开时会发生什么？我们将对不同的 $n$ 展开 $(x+y)^n$。每种情形都是先把所有项乘开（即用 FOIL 法），再合并同类项。

\begin{equation*} (x+y)^1 = x + y \end{equation*} \begin{equation*} (x+y)^2 = x^2 + 2xy + y^2 \end{equation*} \begin{equation*} (x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3 \end{equation*} \begin{equation*} (x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4. \end{equation*}

In fact, there is a quicker way to expand the above binomials. For example, consider the next one, $(x+y)^5$. What we are really doing is multiplying out,

其实，展开上述二项式有更快的办法。例如，考虑下一个，$(x+y)^5$。我们真正在做的事，是把下式乘开：

\begin{equation*} (x+y)(x+y)(x+y)(x+y)(x+y). \end{equation*}

If that looks daunting, go back to the case of $(x+y)^3 = (x+y)(x+y)(x+y)$. Why do we only have one $x^3$ and $y^3$ but three $x^2y$ and $xy^2$ terms? Every time we distribute over an $(x+y)$ we create two copies of what is left, one multiplied by $x\text{,}$ the other multiplied by $y$. To get $x^3\text{,}$ we need to pick the “multiplied by $x$” side every time (we don't have any $y$'s in the term). This will only happen once. On the other hand, to get $x^2y$ we need to select the $x$ side twice and the $y$ side once. In other words, we need to pick one of the three $(x+y)$ terms to “contribute” their $y$.

若这看起来吓人，回到 $(x+y)^3 = (x+y)(x+y)(x+y)$ 的情形。为什么我们只有一个 $x^3$ 项和一个 $y^3$ 项，却有三个 $x^2y$ 项和三个 $xy^2$ 项？每当我们对 $(x+y)$ 分配展开时，都会把剩下的部分复制成两份：一份乘以 $x\text{，}$另一份乘以 $y$。要得到 $x^3\text{，}$必须每次都选「乘以 $x$」的那一侧（该项里不含任何 $y$）。这种情况只会出现一次。另一方面，要得到 $x^2y$，就得选两次 $x$ 侧、一次 $y$ 侧。换言之，我们要从三个 $(x+y)$ 因子中挑一个来「贡献」它的 $y$。

Similarly, in the expansion of $(x+y)^5\text{,}$ there will be only one $x^5$ term and one $y^5$ term. This is because to get an $x^5\text{,}$ we need to use the $x$ term in each of the copies of the binomial $(x+y)\text{,}$ and similarly for $y^5$. What about $x^4y\text{?}$ To get terms like this, we need to use four $x$'s and one $y\text{,}$ so we need exactly one of the five binomials to contribute a $y$. There are 5 choices for this, so there are 5 ways to get $x^4y\text{,}$ so the coefficient of $x^4y$ is 5. This is also the coefficient for $xy^4$ for the same (but opposite) reason: there are 5 ways to pick which of the 5 binomials contribute the single $x$. So far we have

类似地，在 $(x+y)^5$ 的展开式中，只会有一个 $x^5$ 项和一个 $y^5$ 项。这是因为要得到 $x^5\text{，}$必须在每个二项式因子 $(x+y)$ 中都取 $x$ 项，对 $y^5$ 亦然。那么 $x^4y$ 呢？要得到这类项，需要用四个 $x$ 和一个 $y\text{，}$所以五个二项式中必须恰有一个贡献 $y$。这有 5 种选法，故得到 $x^4y$ 的方式有 5 种，从而 $x^4y$ 的系数为 5。出于相同（却相反）的理由，$xy^4$ 的系数也是 5：从五个二项式中挑出贡献那个 $x$ 的因子，有 5 种选法。至此我们得到

\begin{equation*} (x+y)^5 = x^5 + 5x^4y + \underline{~?~}~x^3y^2 + \underline{~?~}~x^2y^3 + 5 xy^4 + y^5. \end{equation*}

We still need the coefficients of $x^3y^2$ and $x^2y^3$. In both cases, we need to pick exactly 3 of the 5 binomials to contribute one variable, the other two to contribute the other. Wait. This sounds familiar. We have 5 things, each can be one of two things, and we need a total of 3 of one of them. That's just like taking 5 bits and making sure exactly 3 of them are 1's. So the coefficient of $x^3y^2$ (and also $x^2y^3$) will be exactly the same as the number of bit strings of length 5 and weight 3, which we found earlier to be 10. So we have:

我们还缺 $x^3y^2$ 与 $x^2y^3$ 的系数。两种情形中，都要从五个二项式中恰挑 3 个来贡献某一种变量，其余两个贡献另一种。等等，这听起来耳熟。我们有 5 个对象，每个可取其两种可能之一，而总共要取其中某一种 3 个。这正像是取 5 个位、并确保其中恰有 3 个为 1。因此 $x^3y^2$（以及 $x^2y^3$）的系数，将恰好等于长度为 5、权为 3 的位串个数，而我们前面已求得其为 10。于是有：

\begin{equation*} (x+y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5 xy^4 + y^5. \end{equation*}

These numbers we keep seeing over and over again. They are the number of subsets of a particular size, the number of bit strings of a particular weight, the number of lattice paths, and the coefficients of these binomial products. We will call them binomial coefficients. We even have a special symbol for them: ${n \choose k}$.

这些数我们一而再、再而三地遇到。它们是特定大小的子集个数、特定权的位串个数、格路径条数，也是这些二项式乘积中的系数。我们称之为二项式系数（binomial coefficients）。我们甚至为它们准备了一个专门的记号：${n \choose k}$。

Definition: Binomial Coefficients 定义：二项式系数

For each integer $n \ge 0$ and integer $k$ with $0 \le k \le n$ there is a number

对每个整数 $n \ge 0$ 以及满足 $0 \le k \le n$ 的整数 $k$，都对应一个数

\begin{equation*} {n\choose k} \end{equation*}

read “$n$ choose $k$.” We have:

读作「$n$ 选 $k$」。我们有：

${n\choose k} = |\B^n_k|\text{,}$ the number of $n$-bit strings of weight $k$.
${n \choose k}$ is the number of subsets of a set of size $n$ each with cardinality $k$.
${n \choose k}$ is the number of lattice paths of length $n$ containing $k$ steps to the right.
${n \choose k}$ is the coefficient of $x^ky^{n-k}$ in the expansion of $(x+y)^n$.
${n \choose k}$ is the number of ways to select $k$ objects from a total of $n$ objects.

${n\choose k} = |\B^n_k|\text{，}$即权为 $k$ 的 $n$ 位串个数。
${n \choose k}$ 是大小为 $n$ 的集合中、基数为 $k$ 的子集个数。
${n \choose k}$ 是长度为 $n$、含 $k$ 步向右的格路径条数。
${n \choose k}$ 是 $(x+y)^n$ 展开式中 $x^ky^{n-k}$ 项的系数。
${n \choose k}$ 是从 $n$ 个对象中选出 $k$ 个对象的方式数。

The last bullet point is usually taken as the definition of ${n \choose k}$. Out of $n$ objects we must choose $k$ of them, so there are $n$ choose $k$ ways of doing this. Each of our counting problems above can be viewed in this way:

最后一条通常会被当作 ${n \choose k}$ 的定义。从 $n$ 个对象中我们必须挑出 $k$ 个，所以做这件事的方式有「$n$ 选 $k$」种。上面每一个计数问题都可以这样看待：

How many subsets of $\{1,2,3,4,5\}$ contain exactly 3 elements? We must choose 3 of the 5 elements to be in our subset. There are ${5 \choose 3}$ ways to do this, so there are ${5 \choose 3}$ such subsets.
How many bit strings have length 5 and weight 3? We must choose 3 of the 5 bits to be 1's. There are ${5 \choose 3}$ ways to do this, so there are ${5 \choose 3}$ such bit strings.
How many lattice paths are there from $(0,0)$ to $(3,2)$? We must choose 3 of the 5 steps to be towards the right. There are ${5 \choose 3}$ ways to do this, so there are ${5 \choose 3}$ such lattice paths.
What is the coefficient of $x^3y^2$ in the expansion of $(x+y)^5\text{?}$ We must choose 3 of the 5 copies of the binomial to contribute an $x$. There are ${5 \choose 3}$ ways to do this, so the coefficient is ${5 \choose 3}$.

集合 $\{1,2,3,4,5\}$ 中有多少个子集恰好含 3 个元素？我们必须从 5 个元素中挑 3 个放入子集。这样做有 ${5 \choose 3}$ 种方式，因此这样的子集有 ${5 \choose 3}$ 个。
有多少个长度为 5、权为 3 的位串？我们必须从 5 个位中挑 3 个作为 1。这样做有 ${5 \choose 3}$ 种方式，因此这样的位串有 ${5 \choose 3}$ 个。
从 $(0,0)$ 到 $(3,2)$ 有多少条格路径？我们必须从 5 步中挑 3 步向右。这样做有 ${5 \choose 3}$ 种方式，因此这样的格路径有 ${5 \choose 3}$ 条。
在 $(x+y)^5$ 的展开式中，$x^3y^2$ 的系数是多少？我们必须从 5 个二项式因子中挑 3 个来贡献一个 $x$。这样做有 ${5 \choose 3}$ 种方式，所以该系数就是 ${5 \choose 3}$。

It should be clear that in each case above, we have the right answer. All we had to do is phrase the question correctly and it became obvious that ${5 \choose 3}$ is correct. However, this does not tell us that the answer is in fact 10 in each case. We will eventually find a formula for ${n \choose k}\text{,}$ but for now, look back at how we arrived at the answer 10 in our counting problems above. It all came down to bit strings, and we have a recurrence relation for bit strings:

显然，上述每种情形我们的答案都是正确的。我们只需把问题表述正确，便不难看出 ${5 \choose 3}$ 是对的。然而，这并不能告诉我们每种情形下答案确实都是 10。我们终将得到 ${n \choose k}$ 的一个公式，但眼下，请回顾我们在上面的计数问题中是如何得到答案 10 的。一切都归结到位串，而位串满足如下递推关系：

\begin{equation*} |\B^n_k| = |\B^{n-1}_{k-1}| + |\B^{n-1}_k|. \end{equation*}

Remember, this is because we can start the bit string with either a 1 or a 0. In both cases, we have $n-1$ more bits to pick. The strings starting with 1 must contain $k-1$ more 1's, while the strings starting with 0 still need $k$ more 1's.

记住，这是因为位串可以以 1 或 0 开头。两种情况下，都还要再选 $n-1$ 个位。以 1 开头的串必须再含 $k-1$ 个 1，而以 0 开头的串仍需再含 $k$ 个 1。

Since $|\B^n_k| = {n \choose k}\text{,}$ the same recurrence relation holds for binomial coefficients:

由于 $|\B^n_k| = {n \choose k}\text{，}$同样的递推关系对二项式系数也成立：

Recurrence relation for ${n \choose k}$ ${n \choose k}$ 的递推关系

\begin{equation*} {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} \end{equation*}

Pascal's Triangle 帕斯卡三角形

Let's arrange the binomial coefficients ${n \choose k}$ into a triangle like follows:

我们把二项式系数 ${n \choose k}$ 排成如下的三角形：

This can continue as far down as we like. The recurrence relation for ${n \choose k}$ tells us that each entry in the triangle is the sum of the two entries above it. The entries on the sides of the triangle are always 1. This is because ${n \choose 0} = 1$ for all $n$ since there is only one way to pick 0 of $n$ objects and ${n \choose n} = 1$ since there is one way to select all $n$ out of $n$ objects. Using the recurrence relation, and the fact that the sides of the triangle are 1's, we can easily replace all the entries above with the correct values of ${n \choose k}$. Doing so gives us Pascal's triangle.

这可以一直向下延伸，任意长度皆可。${n \choose k}$ 的递推关系告诉我们：三角形中每个条目都等于它上方两个条目之和。三角形两侧边缘的条目恒为 1。这是因为对所有 $n$ 都有 ${n \choose 0} = 1$（从 $n$ 个对象中挑 0 个只有一种方式），且 ${n \choose n} = 1$（从 $n$ 个对象中挑全部 $n$ 个也只有一种方式）。利用递推关系，再加上两侧边缘都是 1 这一事实，我们就能轻而易举地把上面所有条目换成正确的 ${n \choose k}$ 值。这样便得到帕斯卡三角形（Pascal's triangle）。

We can use Pascal's triangle to calculate binomial coefficients. For example, using the triangle below, we can find ${12 \choose 6} = 924$.

我们可以用帕斯卡三角形来计算二项式系数。例如，借助下面的三角形，可求得 ${12 \choose 6} = 924$。