第 5 章二项式系数

EX1

Prove Pascal's formula by substituting the values of the binomial coefficients as given in equation (5.1).

从右向左证明帕斯卡公式

\begin{aligned} (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) = & \frac{(n - 1)!}{(k - 1)! (n - k)!} + \frac{(n - 1)!}{k! (n - k - 1)!} \\ = & \frac{(n - 1)!}{(k - 1)! (n - k - 1)!} \times (\frac{1}{n - k} + \frac{1}{k}) \\ = & \frac{(n - 1)!}{(k - 1)! (n - k - 1)!} \times \frac{k + (n - k)}{k (n - k)} \\ = & \frac{n!}{k! (n - k)!} = (\binom{n}{k}) \end{aligned}

EX2

Fill in the rows of Pascal's triangle corresponding to n = 9 and 10.

验证程序

CPP

#include <iostream>
#include <vector>
using namespace std;

const int tableSize = 67;
vector<vector<long long>> combinTable(tableSize, vector<long long>(tableSize, 0));
void buildCombinTable() {
    for(int i = 1; i < tableSize; ++ i) {
        combinTable[i][i] = combinTable[i][0] = 1;
    }
    for(int i = 2; i < tableSize; ++ i) {
        for(int j = i/2; j > 0; -- j) {
            combinTable[i][j] = combinTable[i-1][j-1] + combinTable[i-1][j];
   combinTable[i][i-j] = combinTable[i][j];
        }
    }
}
long long getCombin(int n, int m) {
    return combinTable[n][m];
}

int main() {
    buildCombinTable();
    int n = 10;
    printf("\t");
    for(int i = 0; i <= n; ++ i) {
        printf("%d\t", i);
    }
    printf("\n");
    for(int i = 0; i <= n; ++ i) {
        printf("%d\t", i);
        for(int j = 0; j <= i; ++ j) {
            printf("%lld\t", combinTable[i][j]);
        }
        printf("\n");
    }
    return 0;
}

EX3

Consider the sum of the binomial coefficients along the diagonals of Pascal's triangle running upward from the left. The first few are 1,1,1 + 1 = 2,1 + 2 = 3, 1 + 3 + 1 = 5, 1 + 4 + 3 = 8. Compute several more of these diagonal sums, and determine how these sums are related. (Compare them with the values of the counting function f in Exercise 4 of Chapter 1.)

可以发现所求序列就是每条斜对角线之和构成的序列，

F (n) = \sum (\binom{n - k}{k})

并且 k 要满足， $k \geq 0, n - k \geq k$ ，所以 k 的取值范围为 $0 \leq k \leq ⌊ n / 2 ⌋$ 。

显然，我们有平凡的解， $F (0) = 1, F (1) = 1$ ，设 Z 为每一项中 k 的定义域，当 $n \geq 2$ 时，对于每一项使用帕斯卡公式展开，并且记 $h = k - 1$ 。

\begin{aligned} F (n) = & \sum_{k \in Z} (\binom{n - k}{k}) = \sum_{k \in Z} (\binom{n - k - 1}{k}) + \sum_{k \in Z^{″}} (\binom{n - k - 1}{k - 1}) \\ = & \sum_{k \in Z^{'}} (\binom{(n - 1) - k}{k}) + \sum_{k \in Z} (\binom{(n - 2) - (k - 1)}{k - 1}) \\ = & \sum_{k \in Z^{'}} (\binom{(n - 1) - k}{k}) + \sum_{h \in Z} (\binom{(n - 2) - h}{h}) \\ = & F (n - 1) + F (n - 2) \end{aligned}

第一章 EX4 中的 f(x) 就是斐波那契数列。

EX4

Expand $(x + y)^{5}$ and $(x + y)^{6}$ using the binomial theorem.

x^{5} + 5 x^{4} y + 10 x^{3} y^{2} + 10 x^{2} y^{3} + 5 x y^{4} + y^{5} x^{6} + 6 x^{5} y + 15 x^{4} y^{2} + 20 x^{3} y^{3} + 15 x^{2} y^{4} + 6 x y^{5} + y^{6}

EX5

Expand $(2 x - y)^{7}$ using the binomial theorem.

\sum_{i = 0}^{7} (\binom{7}{i}) {(2 x)}^{(7 - i)} {(- y)}^{i} = 128 x^{7} - 448 x^{6} y + 672 x^{5} y^{2} - 560 x^{4} y^{3} + 280 x^{3} y^{4} - 84 x^{2} y^{5} + 14 x y^{6} - y^{7}

EX6

What is the coefficient of $x^{5} y^{13}$ in the expansion of $(3 x - 2 y)^{18}$ ? What is the coefficient of $x^{8} y^{9}$ ? (There is not a misprint in this last question!)

从 18 项中选择 5 项 x，其余项为 y，因此 $x^{5} y^{13}$ 的系数为 $(\binom{18}{5}) \times 3^{5} \times (- 2)^{13} = - 17055940608$ ； $8 + 9 \neq 18$ ，不存在 $x^{8} y^{9}$ 的项。

EX7

Use the binomial theorem to prove that
$3^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) 2^{k}$
Generalize to find the sum
$\sum_{k = 0}^{n} (\binom{n}{k}) r^{k}$
for any real number r.

(x + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} 1^{n - k} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k}

带入 x=2 即有，

3^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) 2^{k}

所以，带入 x=r 有，

\sum_{k = 0}^{n} (\binom{n}{k}) r^{k} = (r + 1)^{n}

EX8

Use the binomial theorem to prove that
$2^{n} = \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) 3^{n - k}$

\sum_{k = 0}^{n} (\binom{n}{k}) (- 1)^{k} \cdot 3^{n - k} = (- 1 + 3)^{n} = 2^{n}

EX9

Evaluate the sum
$\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) 10^{k}$

\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) 10^{k} = \sum_{k = 0}^{n} (\binom{n}{k}) (- 10)^{k} \cdot 1^{n - k} = (- 10 + 1)^{n} = (- 1)^{n} \cdot 9^{n}

EX10

Use combinatorial reasoning to prove the identity (5.2).

设 x 是 ${1, 2 \dots, n}$ 的 k 子集，y 是 x 中的一个元素，有如下两种方式构造 (x, y) 元组。

先构造 x，从 n 个元素中选 k 个，有 $(\binom{n}{k})$ 种方法，再从 x 中选择 y，共有 k 种方法，由乘法原理共有 $k (\binom{n}{k})$ 种方法。
先选 y，从 n 个元素中选 1 个，有 n 种方法，再添加 n-1 个元素补全 x，有 $(\binom{n - 1}{k - 1})$ 种方法，由乘法原理共有 $n (\binom{n - 1}{k - 1})$ 种方法。

因为 1 和 2 是相同问题的不同解法，因此结果等价，

k (\binom{n}{k}) = n (\binom{n - 1}{k - 1})

有助于理解的方法

方法一：从 n 位同学中先选出 k 位班委，再从 k 位班委中选出 1 位班长；

方法二：先从 n 位同学中选出 1 位班长，再从剩余 n-1 位同学中选出剩余 k-1 位班委。

EX11

Use combinatorial reasoning to prove the identity (in the form given)
$(\binom{n}{k}) - (\binom{n - 3}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 2}{k - 1}) + (\binom{n - 3}{k - 1})$
(Hint: Let S be a set with three distinguished elements a, b, and c and count certain k-subsets of S.)

设 S 是 ${1, 2, \dots, n}$ 的 k 子集， $S_{1}$ 是包含 1 的 k 子集， $S_{2}$ 是包含 2 但不包含 1 的 k 子集， $S_{3}$ 是包含 3 但不包含 1 和 2 的 k 子集， $S_{4}$ 是不包含 1，2，3 的 k 子集。由定义可以计算，

| S | = (\binom{n}{k}), | S_{1} | = (\binom{n - 1}{k - 1}), | S_{2} | = (\binom{n - 2}{k - 1}), | S_{3} | = (\binom{n - 3}{k - 1}), | S_{4} | = (\binom{n - 3}{k})

下面考虑问题：集合 ${1, 2, \dots, n}$ 的 k 子集中包含 1，2，3 中至少一个的 k 子集数目。有如下两种解法，

所有的 k 子集数减去不包含 1，2，3 的 k 子集数；
包含 1，包含 2 但不包含 1，包含 3 但不包含 1，2 三种 k 子集数之和。

我们给出直观的图来判断集合之间的关系：

EX11

两种解法等价，因此有，

| S | - | S_{4} | = | S_{1} | + | S_{2} | + | S_{3} | \Rightarrow (\binom{n}{k}) - (\binom{n - 3}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 2}{k - 1}) + (\binom{n - 3}{k - 1})

EX12

Let n be a positive integer. Prove that
$\sum_{k = 0}^{n} (- 1)^{k} {(\binom{n}{k})}^{2} = {\begin{cases} 0, & if n is odd \\ (- 1)^{n} (\binom{2 m}{m}) & if n=2m. \end{cases}$
(Hint: For n = 2m, consider the coefficient of $x^{n}$ in $(1 - x^{2})^{n} = (1 + x)^{n} (1 - x)^{n}$ .)

(1 - x^{2})^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) (- x^{2})^{k} = \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) x^{2 k} (1 + x)^{n} (1 - x)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) (- x)^{k} \sum_{j = 0}^{n} (\binom{n}{j}) x^{j}

当 $n = 2 m + 1, m \geq 0$ 时，对比两式 $x^{n}$ 的系数，前者只有偶数项，因此系数为 0；后者前半部分取 k 阶时，后半部分只能取 n-k 阶，因此有

\sum_{k = 0}^{n} (\binom{n}{k}) (- x)^{k} (\binom{n}{n - k}) x^{n - k} = \sum_{k = 0}^{n} (- 1)^{k} {(\binom{n}{k})}^{2} x^{n} = 0

因此有，

\sum_{k = 0}^{n} (- 1)^{k} {(\binom{n}{k})}^{2} = 0

当 $n = 2 m, n \geq 0$ 时，对比两式 $x^{n}$ 的系数，前者 k 取 m，有 $(- 1)^{m} (\binom{n}{m}) x^{2 m}$ ，后者前半部分取 k 阶时，后半部分只能取 n-k 阶，因此有 $\sum_{k = 0}^{n} (\binom{n}{k}) (- x)^{k} (\binom{n}{n - k}) x^{n - k} = \sum_{k = 0}^{n} (- 1)^{k} {(\binom{n}{k})}^{2} x^{n}$ ，代换 n=2m，进而有，

\sum_{k = 0}^{n} (- 1)^{k} {(\binom{n}{k})}^{2} = (- 1)^{m} (\binom{2 m}{m})

综上，证毕。

EX13

Find one binomial coefficient equal to the following expression:
$(\binom{n}{k}) + 3 (\binom{n}{k - 1}) + 3 (\binom{n}{k - 2}) + (\binom{n}{k - 3})$

连续使用帕斯卡公式进行合并。

\begin{aligned} 原式 = & ((\binom{n}{k}) + (\binom{n}{k - 1})) + 2 ((\binom{n}{k - 1}) + (\binom{n}{k - 2})) + ((\binom{n}{k - 2}) + (\binom{n}{k - 3})) \\ = & (\binom{n + 1}{k}) + 2 (\binom{n + 1}{k - 1}) + (\binom{n + 1}{k - 2}) \\ = & (\binom{n + 2}{k}) + (\binom{n + 2}{k - 1}) \\ = & (\binom{n + 3}{k}) \end{aligned}

EX14

Prove that
$(\binom{r}{k}) = \frac{r}{r - k} (\binom{r - 1}{k})$
for r a real number and k an integer with $r \neq k$ .

对于实数 r，有二项式系数定义，

(\binom{r}{k}) = {\begin{cases} \frac{r (r - 1) \dots (r - k + 1)}{k!} & k \geq 1 \\ 1 & k = 0 \\ 0 & k \leq - 1 \end{cases}

因此，当 $k = 0$ 或 $k \leq - 1$ 时，等式显然成立，当 $k \geq 1$ 时，

\frac{r}{r - k} (\binom{r - 1}{k}) = \frac{r}{r - k} \times \frac{(r - 1) (r - 2) \dots (r - k)}{k!} = \frac{r (r - 1) \dots (r - k + 1)}{k!} = (\binom{r}{k})

EX15

Prove, that for every integer n > 1,
$(\binom{n}{1}) - 2 (\binom{n}{2}) + 3 (\binom{n}{3}) + \dots + (- 1)^{n - 1} n (\binom{n}{n}) = 0$

(x + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k}

两边同时求一阶导数，

n (x + 1)^{n - 1} = \sum_{k = 1}^{n} k (\binom{n}{k}) x^{k - 1}

两边同时带入 x=-1，即证明上式。

EX16

By integrating the binomial expansion, prove that, for a positive integer n,
$1 + \frac{1}{2} (\binom{n}{1}) + \frac{1}{3} (\binom{n}{2}) + \dots + \frac{1}{n + 1} (\binom{n}{n}) = \frac{2^{n + 1} - 1}{n + 1}$

(x + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k}

两边同时对 x 进行积分，

\frac{(x + 1)^{n + 1}}{n + 1} + C = \sum_{k = 0}^{n} (\binom{n}{k}) \frac{x^{k + 1}}{k + 1}

两边同时带入 x=0，求得 $C = - \frac{1}{n + 1}$ ；再带入 x=1 证明上式成立。

EX17

Prove the identity in the previous exercise by using (5.2) and (5.3).

\begin{matrix} (5.2) & k (\binom{n}{k}) = n (\binom{n - 1}{k - 1}) \end{matrix}

\begin{matrix} (5.3) & (\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{n}) = 2^{n} \end{matrix}

对于 $\frac{1}{k + 1} (\binom{n}{k})$ ，通过式 (5.2) 进行变换，

\begin{aligned} \frac{1}{k + 1} (\binom{n}{k}) = & \frac{1}{k + 1} \frac{n}{k} (\binom{n - 1}{k - 1}) \\ = & \frac{1}{k + 1} \frac{n}{k} \frac{(n - 1)!}{(k - 1)! (n - k)!} \\ = & \frac{n!}{(k + 1)! (n - k)!} \\ = & \frac{1}{n + 1} \frac{(n + 1)!}{(k + 1)! (n - k)!} \\ = & \frac{1}{n + 1} (\binom{n + 1}{k + 1}) \end{aligned}

因此，提出公共部分，由式 (5.3) 可得，

\sum_{k = 0}^{n} \frac{1}{k + 1} (\binom{n}{k}) = \frac{1}{n + 1} \sum_{k = 0}^{n} (\binom{n + 1}{k + 1}) = \frac{2^{n + 1} - 1}{n + 1}

EX18

Evaluate the sum
$1 - \frac{1}{2} (\binom{n}{1}) + \frac{1}{3} (\binom{n}{2}) - \frac{1}{4} (\binom{n}{3}) + \dots + (- 1)^{n} \frac{1}{n + 1} (\binom{n}{n})$

由 EX16 结论，带入 x=-1，并将整个式子添加负号，有

- \sum_{k = 0}^{n} (\binom{n}{k}) \frac{(- 1)^{k + 1}}{k + 1} = - (\frac{(- 1 + 1)^{n + 1}}{n + 1} - \frac{1}{n + 1}) = \frac{1}{n + 1}

EX19

Sum the series $1^{2} + 2^{2} + 3^{2} + \dots + n^{2}$ by observing that
$m^{2} = 2 (\binom{m}{2}) + (\binom{m}{1})$
and using the identity (5.19).

2 (\binom{m}{2}) + (\binom{m}{1}) = 2 \times \frac{m (m - 1)}{2} + m = m^{2}

因此每个平方数都可以写成组合数和的形式，

\begin{aligned} \sum_{k = 1}^{n} k^{2} = & \sum_{k = 1}^{n} (2 (\binom{k}{2}) + (\binom{k}{1})) \\ = & 2 \sum_{k = 0}^{n} (\binom{k}{2}) + \sum_{k = 0}^{n} (\binom{k}{1}) \\ = & 2 (\binom{n + 1}{3}) + (\binom{n + 1}{2}) \\ = & \frac{n (n + 1) (2 n + 1)}{6} \end{aligned}

信息

使用到帕斯卡的迭代形式，具体参考正文 p85，公式 (5.19)。

EX20 🔑

Find integers a, b, and c such that
$m^{3} = a (\binom{m}{3}) + b (\binom{m}{2}) + c (\binom{m}{1})$
for all m. Then sum the series $1^{3} + 2^{3} + 3^{3} + \dots + n^{3}$ .

a (\binom{m}{3}) + b (\binom{m}{2}) + c (\binom{m}{1}) = a \frac{m (m - 1) (m - 2)}{6} + b \frac{m (m - 1)}{2} + c m = m^{3}

所以有方程组，

{\begin{cases} \frac{a}{6} = 1 \\ - \frac{a}{2} + \frac{b}{2} = 0 \\ \frac{a}{3} - \frac{b}{2} + c = 0 \end{cases}

所以， $a = 6, b = 6, c = 1$ ；参考 EX19 有

\begin{aligned} \sum_{j = 1}^{n} j^{3} = & \sum_{j = 0}^{n} (6 (\binom{j}{3}) + 6 (\binom{j}{2}) + (\binom{j}{1})) \\ = & 6 (\binom{n + 1}{4}) + 6 (\binom{n + 1}{3}) + (\binom{n + 1}{2}) \\ = & \frac{n^{2} (n + 1)^{2}}{4} \end{aligned}

EX21

Prove that, for all real numbers r and all integers k,
$(\binom{- r}{k}) = (- 1)^{k} (\binom{r + k - 1}{k})$

当 $k < 0$ 时，二项式为 0，当 $k \geq 0$ 时，

\begin{aligned} (\binom{- r}{k}) = & \frac{(- r) (- r - 1) \dots (- r - k + 1)}{k!} \\ = & (- 1)^{k} \frac{r (r + 1) \dots (r + k - 1)}{k!} \\ = & (- 1)^{k} (\binom{r + k - 1}{k}) \end{aligned}

EX22

Prove that, for all real numbers r and all integers k and m,
$(\binom{r}{m}) (\binom{m}{k}) = (\binom{r}{k}) (\binom{r - k}{m - k})$

当 $m < 0$ 或者 $k < 0$ 时，二项式为 0，当 $0 \leq k \leq m$ 时，

\begin{aligned} (\binom{r}{m}) (\binom{m}{k}) = & \frac{r (r - 1) \dots (r - m + 1)}{m!} \times \frac{m!}{k! (m - k)!} \\ = & \frac{r (r - 1) \dots (r - k + 1)}{k!} \frac{(r - k) (r - k - 1) \dots (r - m + 1)}{(m - k)!} \\ = & (\binom{r}{k}) (\binom{r - k}{m - k}) \end{aligned}

EX23

Every day a student walks from her home to school, which is located 10 blocks east and 14 blocks north from home. She always takes a shortest walk of 24 blocks.
(a) How many different walks are possible?
(b) Suppose that four blocks east and five blocks north of her home lives her best friend, whom she meets each day on her way to school. Now how many different walks are possible?
(c) Suppose, in addition, that three blocks east and six blocks north of her friend's house there is a park where the two girls stop each day to rest and play. Now how many different walks are there?
(d) Stopping at a park to rest and play, the two students often get to school late. To avoid the temptation of the park, our two students decide never to pass the intersection where the park is. Now how many different walks are there?

EX25 Q(a)

移动 24 次，一共往东 10 次， $(\binom{24}{10}) = 1961256$ 。

EX25 Q(b)

拆成两部分，先到朋友家，再到学校， $(\binom{9}{4}) (\binom{24 - 9}{10 - 4}) = 630630$ 。

EX25 Q(c)

拆成三部分， $(\binom{9}{4}) (\binom{9}{3}) (\binom{6}{3}) = 211680$ 。

EX25 Q(d)

总路径数，减去经过公园的路径数， $(\binom{9}{4}) (\binom{15}{6}) - (\binom{9}{4}) (\binom{9}{3}) (\binom{6}{3}) = 630630 - 211680 = 418950$ 。

顺便一提 💡

本题的街区和第二章 EX28 的街区有些不同，前者视作一个点，后者则看作一个块。

EX24

Consider a three-dimensional grid whose dimensions are 10 by 15 by 20. You are at the front lower left corner of the grid and wish to get to the back upper right corner 45 "blocks" away. How many different routes are there in which you walk exactly 45 blocks?

这本质上是一个分组问题，可以想想为把 45 个带号求，放入 x，y 和 z 三个盒子中。

因此一共有 $\frac{45!}{10! \cdot 15! \cdot 20!}$ 条路径。

EX25

Use a combinatorial argument to prove the Vandermonde convolution for the binomial coefficients: For all positive integers $m_{1}, m_{2}$ , and n,
$\sum_{k = 0}^{n} (\binom{m_{1}}{k}) (\binom{m_{2}}{n - k}) = (\binom{m_{1} + m_{2}}{n})$
Deduce the identity (5.16) as a special case.

考虑从 $m_{1}$ 名男同学， $m_{2}$ 位女同学中选出 n 位班委的问题，由两种解法。

先考虑从男同学中选出 k 名同学担任班委，则还需要从女同学中选出剩余 n-k 名班委，而对于每一个 k 的选法，符合加法法则；
不考虑性别，直接考虑从 $m_{1} + m_{2}$ 名同学选出 n 名同学担任班委。

显然，方法 1 和方法 2 是等价的，因此得证。

对于式 (5.16)，只需要取 $m_{1} = m_{2} = n \geq 0$ ，即有，

\sum_{k = 0}^{n} (\binom{m_{1}}{k}) (\binom{m_{2}}{n - k}) = \sum_{k = 0}^{n} (\binom{n}{k}) (\binom{n}{n - k}) = \sum_{k = 0}^{n} {(\binom{n}{k})}^{2} = (\binom{2 n}{n})

EX26

Let n and k be integers with $1 \leq k \leq n$ . Prove that
$\sum_{k = 1}^{n} (\binom{n}{k}) (\binom{n}{k - 1}) = \frac{1}{2} (\binom{2 n + 2}{n + 1}) - (\binom{2 n}{n})$

由 EX25 可知，

\begin{aligned} \sum_{k = 1}^{n} (\binom{n}{k}) (\binom{n}{k - 1}) \\ = & (\binom{n}{0}) (\binom{n}{- 1}) + \sum_{k = 1}^{n} (\binom{n}{k}) (\binom{n}{k - 1}) + (\binom{n}{n + 1}) (\binom{n}{n}) \\ = & \sum_{k = 0}^{n + 1} (\binom{n}{k}) (\binom{n}{n + 1 - k}) \\ = & (\binom{2 n}{n + 1}) \end{aligned}

即证，

(\binom{2 n}{n + 1}) = \frac{1}{2} (\binom{2 n + 2}{n + 1}) - (\binom{2 n}{n})

结合帕斯卡公式，这是很容易验证的。

小技巧

本题凑二项式系数的范德蒙德卷积公式时，补充的两项都是 $(\binom{r}{k})$ 的扩展定义，当 $k \leq - 1$ 或者 $k > n$ 时，由定义这两项都是 0。

再者，就是范德蒙德卷积公式的 k 并非只能从 0 取到 n，补充定义也是可以的。

EX27

Let n and k be positive integers. Give a combinatorial proof of the identity (5.15):
$n (n + 1) 2^{n - 2} = \sum_{k = 1}^{n} k^{2} (\binom{n}{k})$

还是使用学生的例子从 n 名同学中，先预选 k 名班委，再在 k 名班委中选出班长与学习委员（可以为同一人）。

由上面的例子，可以确定选出 k 名班委有 $(\binom{n}{k})$ 种方案；从班委中选出班长和学习委员各有 k 种方案；由乘法法则，一共有 $k^{2} (\binom{n}{k})$ 种方案。对于 k 可能的取值为 1，2，…，n，每一个 k 之间符合加法法则，因此共有 $\sum_{k = 1}^{n} k^{2} (\binom{n}{k})$ 种方案。

下面进行逆向思考，先委任班长与学习委员。如果班长与学习委员为同一人，其余人要么是班委，要么不是班委，一共有 $n 2^{n - 1}$ 种方案；如果班长与学习委员不是同一人，则有 $n (n - 1) 2^{n - 2}$ 种方案。合计共 $n (n + 1) 2^{n - 2}$ 种方案。

两种解法求解的是同一问题，因此结果等价，题目得证。

EX28

Let nand k be positive integers. Give a combinatorial proof that
$\sum_{k = 1}^{n} k {(\binom{n}{k})}^{2} = n (\binom{2 n - 1}{n - 1})$

从 n 名男同学和 n 名女同学中选出 n 名班委，其中必须有一位女同学担任班长。

从女同学中选出 k 名班委，再从男同学中选出 n-k 名班委，k 名女同学中选出一人为班长，有 $k (\binom{n}{k}) (\binom{n}{n - k})$ 种方法，对于每一个 k，符合加法法则，共有 $\sum_{k = 1}^{n} k {(\binom{n}{k})}^{2}$ 种方法。

或者，先从 n 名女同学中选出班长，再从剩余 2n-1 名同学中选择 n-1 名班委，即 $n (\binom{2 n - 1}{n - 1})$ 种选法，两种解法等价，题目得证。

EX29

Find and prove a formula for
$\sum_{\begin{matrix} r, s, t \geq 0 \\ r + s + t = n \end{matrix}} (\binom{m_{1}}{r}) (\binom{m_{2}}{s}) (\binom{m_{3}}{t})$
where the summation extends over all nonnegative integers r, s and t with sum r + s + t = n.

(x + 1)^{m_{1} + m_{2} + m_{3}} = (x + 1)^{m_{1}} (x + 1)^{m_{2}} (x + 1)^{m_{3}}

对比两端 $x^{n}$ 的系数，则有

\sum_{\begin{matrix} r, s, t \geq 0 \\ r + s + t = n \end{matrix}} (\binom{m_{1}}{r}) (\binom{m_{2}}{s}) (\binom{m_{3}}{t}) = (\binom{m_{1} + m_{2} + m_{3}}{n})

提示

有些类似 EX12 的思路。

EX30

Prove that the only antichain of S = {1, 2, 3, 4} of size 6 is the antichain of all 2-subsets of S.

由定理 5.3.3 知，n 元素集合的最大反链长为 $(\binom{n}{⌊ n / 2 ⌋})$ 。

设 $A$ 是 S 的最大反链，满足，

| A | = (\binom{n}{⌊ n / 2 ⌋})

设 $α_{k}$ 是反链 $A$ 中大小为 k 的子集个数，因此有，

| A | = \sum_{k = 0}^{n} α_{k} = (\binom{n}{⌊ n / 2 ⌋})

也即

\sum_{k = 0}^{n} \frac{α_{k}}{(\binom{n}{⌊ n / 2 ⌋})} = 1

由二项式系数的单峰性，可知， $(\binom{n}{⌊ n / 2 ⌋}) \geq (\binom{n}{k})$ ，结合定理 5.3.3 知，

\sum_{k = 0}^{n} \frac{α_{k}}{(\binom{n}{k})} \leq 1

做差整理可得，

\sum_{k = 0}^{n} α_{k} \frac{(\binom{n}{⌊ n / 2 ⌋}) - (\binom{n}{k})}{(\binom{n}{⌊ n / 2 ⌋}) (\binom{n}{k})} \leq 0

但是， $α_{k}$ 和 $(\binom{n}{⌊ n / 2 ⌋}) - (\binom{n}{k})$ 均为非负数，因此上式恒为 0。要么 $α_{k}$ 为 0，要么 $α_{k}$ 的系数为 0，显然，除 $k = ⌊ n / 2 ⌋$ 和 $k = ⌈ n / 2 ⌉$ 外，一定有 $α_{k} = 0$ 。

并且当 n=4 时， $k = ⌈ n / 2 ⌉ = ⌊ n / 2 ⌋ = 2$ ，所以最大反链唯一，最大反链长为 $(\binom{4}{2}) = 6$ 。并且只有 2 子集的反链数 $α_{2} > 0$ ，因此 S 大小为 6 的反链就是 S 的所有 2 子集的反链。

解题思路

先说明大小为 6 的反链就是最大反链，再论证最大反链唯一，最后说明为最大反链是 2 子集的反链。

EX31

Prove that there are only two antichains of S = {1, 2, 3, 4, 5} of size 10 (10 is maximum by Spemer's theorem), namely, the antichain of all 2-subsets of Sand the antichain of all 3-subsets.

由 EX30 知，n=5 的最大反链长为 $(\binom{5}{2}) = 10$ ，k 可以取 2 或 3，并且有 $α_{2} + α_{3} = 10$ 。所有的 2 子集和所有的 3 子集分别构成的反链均是最大反链。下证 $α_{2}, α_{3}$ 中必有一个为 0，即大小为 10 的反链只能是所有 2 子集的反链或所有 3 子集的反链。对于所有 2 子集构成的反链，每添加一个 3 子集需要从中删除 $(\binom{3}{2}) = 3$ 个 2 子集才能维持反链，而此时 $| A | < 10$ ，不是最大反链，因此最大反链不可能由 2 子集和 3 子集共同构成。因此只能是 $α_{2} = 10, α_{3} = 0$ 或 $α_{2} = 0, α_{3} = 10$ 。

EX32 ⭐

* Let S be a set of n elements. Prove that, if n is even, the only antichain of size $(\binom{n}{⌊ n / 2 ⌋})$ is the antichain of all $\frac{n}{2}$ -subsets; if n is odd, prove that the only antichains of this size are the antichain of all $\frac{n - 1}{2}$ -subsets and the antichain of all $\frac{n + 1}{2}$ -subsets.

略

EX33

Construct a partition of the subsets of {1, 2, 3, 4, 5} into symmetric chains.

需要采用递推的方式，由前一项构造后一项；满足如下两点，

把最后一个子集复制并插入 n，把该子集作为新的最后一个子集；
把 n 插入到除最后一个子集外所有的子集（并删除最后一个子集）。

我们给出 n=4 的结果（可以在草稿上求出），

\begin{aligned} \emptyset, 1, 12, 123, 1234 \\ 4, 14, 124 \\ 2, 23, 234 \\ 24 \\ 3, 13, 134 \\ 34 \end{aligned}

\begin{aligned} \emptyset, 1, 12, 123, 1234, 12345 \\ 5, 15, 125, 1235 \\ 4, 14, 124, 1245 \\ 45, 145 \\ 2, 23, 234, 2345 \\ 25, 235 \\ 24, 245 \\ 3, 13, 134, 1345 \\ 35, 135 \\ 34, 345 \end{aligned}

EX33PS

对于特殊的行 24，它没有除最后一个子集外的所有子集，所以不执行第二项操作。

EX34 🚧 💊

In a partition of the subsets of {1,2, ... ,n} into symmetric chains, how many chains have only one subset in them? two subsets? k subsets?

EX34 参考链接

一个没看懂的解法

待完善 🚧

大意就是求出 $\geq k$ 的子集个数的通项公式，然后用 $\geq k - 1$ 的部分减去 $\geq k$ 的部分，就是 $= k$ 的部分。

EX35

A talk show host has just bought 10 new jokes. Each night he tells some of the jokes. What is the largest number of nights on which you can tune in so that you never hear on one night at least all the jokes you heard on one of the other nights? (Thus, for instance, it is acceptable that you hear jokes 1, 2, and 3 on one night, jokes 3 and 4 on another, and jokes 1, 2, and 4 on a third. It is not acceptable that you hear jokes 1 and 2 on one night and joke 2 on another night.)

本题等价于求 10 个元素的集合最大反链长度，由公式 $(\binom{10}{10 / 2}) = 252$ 。

EX36

Prove the identity of Exercise 25 using the binomial theorem and the relation $(1 + x)^{m_{l}} (1 + x)^{m_{2}} = (1 + x)^{m_{1} + m_{2}}$ .

两端展开，对比 $x^{n}$ 的系数可得，

\sum_{k = 0}^{n} (\binom{m_{1}}{k}) (\binom{m_{2}}{n - k}) = (\binom{m_{1} + m_{2}}{n})

EX37

Use the multinomial theorem to show that, for positive integers nand t,
$t^{n} = \sum (\binom{n}{n_{1} n_{2} \dots n_{t}}),$
where the summation extends over all nonnegative integral solutions $n_{1}, n_{2}, . . ., n_{t}$ of $n_{1} + n_{2} + . . . + n_{t} = n$ .

由多项式定理，直接带入，

\begin{aligned} t^{n} = & (1 + 1 + \dots + 1)^{n} \\ = & \sum (\binom{n}{n_{1} n_{2} \dots n_{t}}) 1^{n_{1}} 1^{n_{2}} \dots 1^{n_{t}} \\ = & \sum (\binom{n}{n_{1} n_{2} \dots n_{t}}) \end{aligned}

EX38

Use the multinomial theorem to expand $(x_{1} + x_{2} + x_{3})^{4}$ .

\begin{aligned} (x_{1} + x_{2} + x_{3})^{4} = & \sum (\binom{4}{n_{1} n_{2} n_{3}}) x_{1}^{n_{1}} x_{2}^{n_{2}} x_{3}^{n_{3}} \\ = & (x_{1}^{4} + x_{2}^{4} + x_{3}^{4}) + 4 (x_{1}^{3} x_{2} + x_{2}^{3} x_{3} + x_{3}^{3} x_{1}) + \\ 6 (x_{1}^{2} x_{2}^{2} + x_{1}^{2} x_{3}^{2} + x_{2}^{2} x_{3}^{2}) + 12 (x_{1}^{2} x_{2} x_{3} + x_{1} x_{2}^{2} x_{3} + x_{1} x_{2} x_{3}^{2}) \end{aligned}

EX39

Determine the coefficient of $x_{1}^{3} x_{2} x_{3}^{4} x_{5}^{2}$ in the expansion of
$(x_{1} + x_{2} + x_{3} + x_{4} + x_{5})^{10}$

系数为 $(\binom{10}{3 1 4 0 2}) = \frac{10!}{3! \times 1! \times 4! \times 0! \times 2!} = 12600$ 。

EX40

What is the coefficient of $x_{1}^{3} x_{2}^{3} x_{3} x_{4}^{2}$ in the expansion of
$(x_{1} - x_{2} + 2 x_{3} - 2 x_{4})^{9}$

(\binom{9}{3 3 1 2}) (x_{1})^{3} (- x_{2})^{3} (2 x_{3}) (- 2 x_{4})^{2} = \frac{9!}{3! \times 3! \times 1! \times 2!} \times (- 1)^{3} \times 2 \times (- 2)^{2} x_{1}^{3} x_{2}^{3} x_{3} x_{4}^{2} = - 40320 x_{1}^{3} x_{2}^{3} x_{3} x_{4}^{2}

EX41

Expand $(x_{1} + x_{2} + x_{3})^{n}$ by boserving that
$(x_{1} + x_{2} + x_{3})^{n} = ((x_{1} + x_{2}) + x_{3})^{n}$
and then using the binomial theorem.

\begin{aligned} (x_{1} + x_{2} + x_{3})^{n} = & ((x_{1} + x_{2}) + x_{3})^{n} \\ = & \sum_{k = 0}^{n} (\binom{n}{k}) (x_{1} + x_{2})^{k} x_{3}^{n - k} \\ = & \sum_{k = 0}^{n} (\binom{n}{k}) (\sum_{j = 0}^{k} (\binom{k}{j}) x_{1}^{j} x_{2}^{k - j}) x_{3}^{n - k} \\ = & \sum_{K = 0}^{n} \sum_{j = 0}^{k} \frac{n!}{k! (n - k)!} \frac{k!}{j! (k - j)!} x_{1}^{j} x_{2}^{k - j} x_{3}^{n - k} \end{aligned}

记 $n_{1} = j, n_{2} = k - j, n_{3} = n - k$ ，所以上式可以化简为，

\begin{aligned} (x_{1} + x_{2} + x_{3})^{n} = & \sum_{n_{1} + n_{2}}^{n_{1} + n_{2} + n_{3}} \sum_{n_{1}}^{n_{1} + n_{2}} \frac{n!}{n_{1}! \times n_{2}! \times n_{3}!} x_{1}^{n_{1}} x_{2}^{n_{2}} x_{3}^{n_{3}} \\ = & \sum_{n_{1} + n_{2} + n_{3} = n} (\binom{n}{n_{1} n_{2} n_{3}}) x_{1}^{n_{1}} x_{2}^{n_{2}} x_{3}^{n_{3}} \end{aligned}

EX42

Prove the identity (5.21) by a combinatorial argument. (Hint: Consider the permutations of a multiset of objects of t different types with repetition numbers $n_{l}, n_{2}, . . ., n_{t}$ , respectively. Partition these permutations according to what type of object is in the first position.)

多重集合 ${n_{1} \cdot x_{1}, n_{2} \cdot x_{2}, \dots, n_{t} \cdot x_{t}}$ 的 n 排列，其中 $n_{1} + n_{2} + \dots + n_{t} = n$ ，多重集合 n 排列满足结论 $\frac{n!}{n_{1}! n_{2}! \dots n_{t}!}$ ，得到左式。

之后采用另一种算法，优先决定第一个位置放哪种元素，有 t 种情况，之后对剩余的 n-1 个元素进行 n-1 排列，假如第一个位置选择 $x_{2}$ ，那么对应的 n-1 排列则为 $\frac{(n - 1)!}{n_{1}! (n_{2} - 1)! \dots n_{t}!}$ ，即等于 $(\binom{n - 1}{n_{1} (n_{2} - 1) \dots n_{t}})$ ，对 t 种情况进行求和，得到右式。

综上，证毕。

EX43

Prove by induction on n that, for n a positive integer,
$\frac{1}{(1 - z)^{n}} = \sum_{k = 0}^{\infty} (\binom{n + k - 1}{k}) z^{k}, | z | < 1$
Assume the validity of
$\frac{1}{1 - z} = \sum_{k = 0}^{\infty} z^{k}, | z | < 1$

当 n=1 是显然成立；假设对正整数 n 上式仍然成立（ $n \geq 1$ ），对于正整数 n+1 有

\begin{aligned} \frac{1}{(1 - z)^{n + 1}} = & \frac{1}{n} (\frac{1}{(1 - z)^{n}})^{'} \\ = & \frac{1}{n} \sum_{k = 1}^{\infty} (\binom{n + k - 1}{k}) k z^{k - 1} \\ = & \sum_{k = 1}^{\infty} \frac{1}{n} \frac{(n + k - 1)!}{k! (n - 1)!} k z^{k - 1} \\ = & \sum_{k = 1}^{\infty} \frac{(n + k - 1)!}{(k - 1)! n!} z^{k - 1} \\ = & \sum_{k = 1}^{\infty} (\binom{n + k - 1}{k - 1}) z^{k - 1} \\ = & \sum_{k = 0}^{\infty} (\binom{(n + 1) + k - 1}{k}) z^{k} \end{aligned}

综上，证毕。

EX43PS

如果使用帕斯卡公式，中间化简合并的过程类似生成函数。

EX44

Prove that
$\sum_{n_{1} + n_{2} + n_{3} = n} (\binom{n}{n_{1} n_{2} n_{3}}) (- 1)^{n_{1} - n_{2} + n_{3}} = (- 3)^{n}$
where the summation extends over all nonnegative integral solutions of $n_{1} + n_{2} + n_{3} = n$ .

由 EX41 可以得到公式，

(x_{1} + x_{2} + x_{3})^{n} = \sum_{n_{1} + n_{2} + n_{3} = n} (\binom{n}{n_{1} n_{2} n_{3}}) x_{1}^{n_{1}} x_{2}^{n_{2}} x_{3}^{n_{3}}

化简题目中的式子，

\begin{aligned} \sum_{n_{1} + n_{2} + n_{3} = n} (\binom{n}{n_{1} n_{2} n_{3}}) (- 1)^{n_{1} - n_{2} + n_{3}} = & \sum_{n_{1} + n_{2} + n_{3} = n} (\binom{n}{n_{1} n_{2} n_{3}}) (- 1)^{n_{1}} (1 / (- 1))^{n_{2}} + (- 1)^{n_{3}} \\ = & (- 1 + 1 / (- 1) + - 1)^{n} \\ = & (- 3)^{n} \end{aligned}

IMPORTANT

本题英文原版书中要证明该式等于 1，应该是印刷错误。

EX45

Prove that
$\sum_{n_{1} + n_{2} + n_{3} + n_{4} = n} (\binom{n}{n_{1} n_{2} n_{3} n_{4}}) (- 1)^{n_{2} + n_{4}} = 0$

相比上一题，本题更为直接，没有倒数需要处理。

\begin{aligned} \sum_{n_{1} + n_{2} + n_{3} + n_{4} = n} (\binom{n}{n_{1} n_{2} n_{3} n_{4}}) (- 1)^{n_{2} + n_{4}} = & \sum_{n_{1} + n_{2} + n_{3} + n_{4} = n} (\binom{n}{n_{1} n_{2} n_{3} n_{4}}) (- 1)^{n_{2}} (- 1)^{n_{4}} 1^{n_{1}} 1^{n_{3}} \\ = & (1 + (- 1) + 1 + (- 1))^{n} \\ = & 0 \end{aligned}

IMPORTANT

本题英文原版书中幂指数印刷错误。

EX46

Use Newton's binomial theorem to approximate $\sqrt{30}$ .

参考正文 P91，

\begin{aligned} \sqrt{30} = & 5 (1 + z)^{\frac{1}{2}} z = \frac{1}{5} \\ = & 5 \sum_{k = 1}^{\infty} (\binom{1 / 2}{k}) z^{k} \end{aligned}

EX46PS

事实上，上面的系数就是泰勒展开的系数。

(1 + x)^{α} = 1 + α x + \frac{α (α - 1)}{2!} x^{2} + \frac{α (α - 1) (α - 2)}{3!} x^{3} + \dots o (x^{3})

EX47

Use Newton's binomial theorem to approximate $10^{1 / 3}$ .

参考答案给出的构造方法，

\begin{array}{r} 10^{1 / 3} = 2 (\frac{10}{8})^{\frac{1}{3}} = 2 (1 + z)^{\frac{1}{3}} z = \frac{1}{4} \end{array}

我自己想的构造，

\begin{array}{r} 10^{1 / 3} = 10 (1 - 0.99)^{\frac{1}{3}} = 10 (1 - z)^{\frac{1}{3}} z = - 0.99 \end{array}

结果应该是一致的。

EX48

Use Theorem 5.6.1 to show that, if m and n are positive integers, then a partially ordered set of mn + 1 elements has a chain of size m + 1 or an antichain of size n+1.

采用反证法，假设命题不成立，即 mn+1 个元素的偏序集，链长度最大为 m，反链长度最大为 n。

设 r 为最大链长，显然有 $r \leq m$ ，并且由定理 5.6.1 知，偏序集可以被划分为 r 条反链 ${A_{i}}_{i = 1}^{r}, | A_{i} | \leq n$ 。因此，

m n + 1 = \sum_{i = 1}^{r} | A_{i} | \leq r n \leq m n

产生了矛盾，假设不成立。

故 mn+1 个元素的偏序集有一个大小为 m+1 的链或大小为 n+1 的反链。

EX49

Use the result of the previous exercise to show that a sequence of mn + 1 real numbers either contains an increasing subsequence of m + 1 numbers or a decreasing subsequence of n + 1 numbers (see Application 9 of Section 2.2).

取 mn+1 个实数 ${a_{i}}_{i = 0}^{m n}$ ，用 X 表示有序对集合 ${(i, a_{i}) | 0 \leq i \leq m n}$ ，并定义 X 上的偏序关系：对于 X 上不同的元素 $x = (i, a_{i}), y = (j, a_{j})$ ，如果有 $i < j, a_{i} \leq a_{j}$ 则 $x < y$ 。

可以发现：链对应递增子序列 ${a_{i}}_{i = 0}^{m n}$ ，反链对应递减子序列 ${a_{i}}_{i = 0}^{m n}$ 。由上题可知，一定能找到长度为 m+1 的链或 n+1 的反链，相应地，也一定有长度为 m+1 的递增子序列或长度为 n+1 的递减子序列。

EX49PS

结论在 3.2 节，稍作调整即有结论：由 mn+1 个实数构成的序列，要么含有长度为 m+1 的递增（非递减）子序列，要么含有长度为 n+1 的递减子序列。

书中递增一般指非严格递增，递减则是严格递减。

EX50

Consider the partially ordered set (X, |) on the set X = {1, 2, ... ,12} of the first 12 positive integers, partially ordered by "is divisible by." (a) Determine a chain of largest size and a partition of X into the smallest number of antichains. (b) Determine an antichain of largest size and a partition of X into the smallest number of chains.

EX50Q(a)

最大大小的链为 1,2,4 8，最大链长为 4，反链划分如下，

\begin{aligned} 8, 12 \\ 4, 6, 9, 10 \\ 2, 3, 5, 7, 11 \\ 1 \end{aligned}

EX50Q(b)

最大大小的反链为 7, 8, 9, 10, 11, 12，（选出度为 0 的所有结点）反链长为 6，链的划分如下，

\begin{aligned} 1, 2, 4, 8 \\ 3, 6, 12 \\ 9 \\ 5, 10 \\ 7 \\ 11 \end{aligned}

EX51

Let Rand S be two partial orders on the same set X. Considering R and S as subsets of $X \times X$ , we assume that $R \subseteq S$ but $R \neq S$ . Show that there exists an ordered pair (p, q), where $(p, q) \in S$ and $(p, q) \notin R$ such hat $R^{'} = R \cup {(p, q)}$ is also a partial order on X. Show by example that not every such (p, q) has the property that R' is a partial order on X.

举反例的题目，取

X = {1, 2, 3}, R = {(1, 1), (2, 2), (3, 3), (1, 2)}, S = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3)}

取 p=2,q=3，这时 $R^{'} = {1, 1), (2, 2), (3, 3), (1, 2), (2, 3)}$ ，然而 $R^{'}$ 不满足传递关系（不包含 (1,3)），因此 $R^{'}$ 不是 X 上的偏序。

第 5 章 二项式系数 ​

EX1 ​

EX2 ​

EX3 ​

EX4 ​

EX5 ​

EX6 ​

EX7 ​

EX8 ​

EX9 ​

EX10 ​

EX11 ​

EX12 ​

EX13 ​

EX14 ​

EX15 ​

EX16 ​

EX17 ​

EX18 ​

EX19 ​

EX20 🔑 ​

EX21 ​

EX22 ​

EX23 ​

EX25 Q(a) ​

EX25 Q(b) ​

EX25 Q(c) ​

EX25 Q(d) ​

EX24 ​

EX25 ​

EX26 ​

EX27 ​

EX28 ​

EX29 ​

EX30 ​

EX31 ​

EX32 ⭐ ​

EX33 ​

EX33PS ​

EX34 🚧 💊 ​

EX34 参考链接 ​

EX35 ​

EX36 ​

EX37 ​

EX38 ​

EX39 ​

EX40 ​

EX41 ​

EX42 ​

EX43 ​

EX43PS ​

EX44 ​

EX45 ​

EX46 ​

EX46PS ​

EX47 ​

EX48 ​

EX49 ​

EX49PS ​

EX50 ​

EX50Q(a) ​

EX50Q(b) ​

EX51 ​

第 5 章二项式系数

EX1

EX2

EX3

EX4

EX5

EX6

EX7

EX8

EX9

EX10

EX11

EX12

EX13

EX14

EX15

EX16

EX17

EX18

EX19

EX20 🔑

EX21

EX22

EX23

EX25 Q(a)

EX25 Q(b)

EX25 Q(c)

EX25 Q(d)

EX24

EX25

EX26

EX27

EX28

EX29

EX30

EX31

EX32 ⭐

EX33

EX33PS

EX34 🚧 💊

EX34 参考链接

EX35

EX36

EX37

EX38

EX39

EX40

EX41

EX42

EX43

EX43PS

EX44

EX45

EX46

EX46PS

EX47

EX48

EX49

EX49PS

EX50

EX50Q(a)

EX50Q(b)

EX51