第38课 — 组合与牛顿二项式

组合与二项式

简单组合

$C_n^p = \binom{n}{p} = \frac{n!}{p!(n-p)!}$

读："$n$ 选 $p$"。$0 \leq p \leq n$ 时有效。

与有序选择的差别

$\binom{n}{p}$ 不排序。每个 $p$ 元子集只数一次。关系：$A_n^p = p! \binom{n}{p}$——有序选择是选完后排序。

性质

帕斯卡三角形

                    1
                  1   1
                1   2   1
              1   3   3   1
            1   4   6   4   1
          1   5  10  10   5   1
        1   6  15  20  15   6   1

第 $n$ 行（从 0 开始）含系数 $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$。

二项式定理（牛顿）

$(a + b)^n = \sum_{p=0}^n \binom{n}{p} a^{n-p} b^p$

例：

• $(a + b)^2 = a^2 + 2ab + b^2$
• $(a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$
• $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$

通项

$T_{p+1} = \binom{n}{p} a^{n-p} b^p$——$(a+b)^n$ 的第 $(p+1)$ 项。

多项（推广）

$(x_1 + x_2 + \cdots + x_k)^n = \sum \binom{n}{n_1, n_2, \ldots, n_k} x_1^{n_1} \cdots x_k^{n_k}$

$\binom{n}{n_1, \ldots, n_k} = \frac{n!}{n_1! \cdots n_k!}$，$\sum n_i = n$。