Binomial Theorem

Let $n$ be a nonnegative integer. Then

\[\sum_{k=0}^n 2^k\left(\begin{array}{l} n \\ k \end{array}\right)=3^n \]

Proof: We recognize that the left-hand side of this formula is the expansion of $(1+2)^n$ provided by the binomial theorem. Therefore, by the binomial theorem, we see that

\[(1+2)^n=\sum_{k=0}^n\left(\begin{array}{l} n \\ k \end{array}\right) 1^{n-k} 2^k=\sum_{k=0}^n\left(\begin{array}{l} n \\ k \end{array}\right) 2^k . \]

Hence

\[\sum_{k=0}^n 2^k\left(\begin{array}{l} n \\ k \end{array}\right)=3^n \]

实际上就是直接展开.

Pascal's Identity and Triangle

The binomial coefficients satisfy many different identities. We introduce one of the most important of these now.
PASCAL'S IDENTITY Let $n$ and $k$ be positive integers with $n \geq k$. Then

\[\left(\begin{array}{c} n+1 \\ k \end{array}\right)=\left(\begin{array}{c} n \\ k-1 \end{array}\right)+\left(\begin{array}{l} n \\ k \end{array}\right) \]

通过解释证明.

$n + 1$ 个选择 $k$ 个:

选最后一个;
不选最后一个.

VANDERMONDE'S IDENTITY

Let $m, n$, and $r$ be nonnegative integers with $r$ not exceeding either $m$ or $n$. Then

\[\left(\begin{array}{c} m+n \\ r \end{array}\right)=\sum_{k=0}^r\left(\begin{array}{c} m \\ r-k \end{array}\right)\left(\begin{array}{l} n \\ k \end{array}\right) \]

Remark: This identity was discovered by mathematician Alexandre-Théophile Vandermonde in the eighteenth century.

Proof: Suppose that there are $m$ items in one set and $n$ items in a second set. Then the total number of ways to pick $r$ elements from the union of these sets is $\left(\begin{array}{c}m+n \\ r\end{array}\right)$.

Another way to pick $r$ elements from the union is to pick $k$ elements from the second set and then $r-k$ elements from the first set, where $k$ is an integer with $0 \leq k \leq r$. Because there are $\left(\begin{array}{l}n \\ k\end{array}\right)$ ways to choose $k$ elements from the second set and $\left(\begin{array}{c}m \\ r-k\end{array}\right)$ ways to choose $r-k$ elements from the first set, the product rule tells us that this can be done in $\left(\begin{array}{c}m \\ r-k\end{array}\right)\left(\begin{array}{l}n \\ k\end{array}\right)$ ways. Hence, the total number of ways to pick $r$ elements from the union also equals $\sum_{k=0}^r\left(\begin{array}{c}m \\ r-k\end{array}\right)\left(\begin{array}{l}n \\ k\end{array}\right)$.

通过解释证明:

$m+n$ 选出 $r$ 个:

左边选 $r - k$ 个, 右边选择 $k$ 个;
遍历所有可能的 $k$.

We have found two expressions for the number of ways to pick $r$ elements from the union of a set with $m$ items and a set with $n$ items. Equating them gives us Vandermonde's identity.
Corollary 4 follows from Vandermonde's identity.
If $n$ is a nonnegative integer, then

\[\left(\begin{array}{c} 2 n \\ n \end{array}\right)=\sum_{k=0}^n\left(\begin{array}{l} n \\ k \end{array}\right)^2 \]

Proof: We use Vandermonde's identity with $m=r=n$ to obtain

\[\left(\begin{array}{c} 2 n \\ n \end{array}\right)=\sum_{k=0}^n\left(\begin{array}{c} n \\ n-k \end{array}\right)\left(\begin{array}{l} n \\ k \end{array}\right)=\sum_{k=0}^n\left(\begin{array}{l} n \\ k \end{array}\right)^2 . \]

The last equality was obtained using the identity $\left(\begin{array}{l}n \\ k\end{array}\right)=\left(\begin{array}{c}n \\ n-k\end{array}\right)$.

实际上就是 Vandermonde's identity 的特殊情况.

Theorem 4

Let $n$ and $r$ be nonnegative integers with $r \leq n$. Then

\[\left(\begin{array}{l} n+1 \\ r+1 \end{array}\right)=\sum_{j=r}^n\left(\begin{array}{l} j \\ r \end{array}\right) . \]

通过解释证明:

一个比特字符串, 一共 $n +1$ 位, 有 $r+1$ 个 1, 其他是 0. 在这个字符串里面最后出现的 1肯定在 $r + 1$ 到 $n + 1$ 的某个位置.

$n +1$ 位, 有 $r+1$ 个 1, 的字符串数量是

最后一个 1 出现在第 $r+1$ 位.
最后一个 1 出现在第 $r+2$ 位.
...
最后一个 1 出现在第 $n+1$ 位.

Generating Functions

定义:

The generating function for the sequence $a_0 , a_1 , \dots , a_k $, . . . of real numbers is the infinite series

\[G(x) = a_0 + a_1x + a_2x^2 + \cdots + a_kx^k + \cdots = \sum_{i = 0}^\infty a_k x^k . \]

常用

二项式定理:

\[\begin{aligned} & (1+x)^n=\sum_{k=0}^n C(n, k) x^k \\ & =1+C(n, 1) x+C(n, 2) x^2+\cdots+x^n \\ & (1+a x)^n=\sum_{k=0}^n C(n, k) a^k x^k \\ & =1+C(n, 1) a x+C(n, 2) a^2 x^2+\cdots+a^n x^n \\ & \left(1+x^r\right)^n=\sum_{k=0}^n C(n, k) x^{r k} \\ & =1+C(n, 1) x^r+C(n, 2) x^{2 r}+\cdots+x^{r n} \end{aligned} \]

等比数列:

\[\begin{aligned} & \frac{1-x^{n+1}}{1-x}=\sum_{k=0}^n x^k=1+x+x^2+\cdots+x^n \\ & \frac{1}{1-x}=\sum_{k=0}^{\infty} x^k=1+x+x^2+\cdots \\ & \frac{1}{1-a x}=\sum_{k=0}^{\infty} a^k x^k=1+a x+a^2 x^2+\cdots \\ & \frac{1}{1-x^r}=\sum_{k=0}^{\infty} x^{r k}=1+x^r+x^{2 r}+\cdots \\ \end{aligned} \]

求导/展开:

\[\begin{aligned} & \frac{1}{(1-x)^2}=\sum_{k=0}^{\infty}(k+1) x^k=1+2 x+3 x^2+\cdots \\ & \frac{1}{(1-x)^n}=\sum_{k=0}^{\infty} C(n+k-1, k) x^k \\ & =1+C(n, 1) x+C(n+1,2) x^2+\cdots \\ & \frac{1}{(1+x)^n}=\sum_{k=0}^{\infty} C(n+k-1, k)(-1)^k x^k \\ & =1-C(n, 1) x+C(n+1,2) x^2-\cdots \\ & \frac{1}{(1-a x)^n}=\sum_{k=0}^{\infty} C(n+k-1, k) a^k x^k \\ & =1+C(n, 1) a x+C(n+1,2) a^2 x^2+\cdots \\ & e^x=\sum_{k=0}^{\infty} \frac{x^k}{k !}=1+x+\frac{x^2}{2 !}+\frac{x^3}{3 !}+\cdots \\ & \ln (1+x)=\sum_{k=1}^{\infty} \frac{(-1)^{k+1}}{k} x^k=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+\cdots \\ & \end{aligned} \]

定理

Let $f(x)=\sum_{k=0}^{\infty} a_k x^k$ and $g(x)=\sum_{k=0}^{\infty} b_k x^k$. Then

\[f(x)+g(x)=\sum_{k=0}^{\infty}\left(a_k+b_k\right) x^k \quad \text { and } \quad f(x) g(x)=\sum_{k=0}^{\infty}\left(\sum_{j=0}^k a_j b_{k-j}\right) x^k \]

扩张定义: 二项式系数

Let $u$ be a real number and $k$ a nonnegative integer. Then the extended binomial coefficient $\left(\begin{array}{l}u \\ k\end{array}\right)$ is defined by

\[\left(\begin{array}{l} u \\ k \end{array}\right)= \begin{cases}u(u-1) \cdots(u-k+1) / k ! & \text { if } k>0 \\ 1 & \text { if } k=0\end{cases} \]

允许 $u$ 是负数, 非整数.

Counting Problems

比如: 整数解的个数问题 ($e_i \geq 0$):

\[\sum e_i = C \]

Find the number of solutions of

\[e_1+e_2+e_3=17 \]

where $e_1, e_2$, and $e_3$ are nonnegative integers with $2 \leq e_1 \leq 5,3 \leq e_2 \leq 6$, and $4 \leq e_3 \leq 7$.
Solution: The number of solutions with the indicated constraints is the coefficient of $x^{17}$ in the expansion of

\[\left(x^2+x^3+x^4+x^5\right)\left(x^3+x^4+x^5+x^6\right)\left(x^4+x^5+x^6+x^7\right) \]

十七块钱分给三个小朋友, 每个人分到的钱需要在一个区间里; 钱都是一样的钱, 不会出现抢相同面额的钱的情况; 假设钱都是 1 块钱, 不会出现 5 块钱面值不能拆分的情况;

总方法数是上面多项式展开后 $x^{17}$ 的系数. 指数表示每个小朋友被分到了多少钱, 在指数位置的数字在相乘的时候会相加, 对应了和固定这一前提.

注意这里分钱是有顺序的, 也就是先分给第一个小朋友, 然后给第二个, 然后是第三个.

除了项数有限的情况, 项数无无限的情况也适用.

还是分钱的问题, 这次是自动贩卖机.有三种面额的货币, 分别是 1 元, 2 元和 5 元. 一个商品需要 r 元, 如果钱是

一次性放入的
或者说, 不考虑钱投入自动贩卖机的先后顺序

那么组成 r 元的种类数是:

\[\left(1+x+x^2+x^3+\cdots\right)\left(1+x^2+x^4+x^6+\cdots\right)\left(1+x^5+x^{10}+x^{15}+\cdots\right) \]

如果钱是

一个个放入
或者说, 钱有投入的先后顺序之分
- 2, 1, 2 和 1, 2, 2 是两种投入的方式

那么组成 r 元的种类数就是:

\[(x + x^2 + x^5)^n \]

其中 $n$ 是说投入了 n 次.

是否区分投入顺序这一点对母函数构造的理解是不一样的.

不区分顺序:
- 括号里面代表了这一种钱币 1 张的情况, 2 张的情况, 3 张的情况...
- 感觉上:
  - 括号之间相乘直觉上像是为三个集合做 (笛卡尔) 积, 最后得到的总集合我们能比较方便地取出我们想要的答案部分.
  - 或者直接用正经的思路解释, 因为每个括号里的元素实际上在我们在锁定一个答案的某种构造方法的时候 (比如 $x^{17}$ 的一种构造方法可以是 $x^5x^5x^2x^2x^2 x$ ) 就只选了一次. 某数量的 1 块钱选了一次, 某数量的 2 块钱选了一次, 某数量的 5 块钱选了一次, 所有可能的情况求和, 就是答案 (或者说答案组分的那个系数).
区分顺序
- 括号里面是三种钱币, 三种面额;
- 投币 n 次, 所以是 n 个步骤一步步相乘.
- 最终可以组合出目标的答案, 也就是 $x^{17}$ .