第四章: 组合和概率基础

第一部分:组合基础和生成函数

组合基础

  • 略。

组合恒等式

  • 缺。

  • 对于有限集 $A_1, \ldots, A_n$，有容斥原理： \(\left|\bigcup_{i=1}^{n} A_i \right| = \sum_{\emptyset\ne I\subseteq [n]}(-1)^{|I| - 1} \left| \bigcap_{i\in I} A_i \right|\)

  • 例子：至少有一个对子的，5张扑克的一手牌，共有多少种可能？

    • 答：补集计数（注：即为 $n=1$ 的容斥原理）。先计数没有任何对子的手牌数：

      • 只考虑数字，相当于从1~13中选取没有任何相同数字的5个数字，共有${13\choose 5}$种可能。

      • 因为每张牌的花色可以是4种花色中的任何一个，故而没有任何对子的手牌共有 ${13\choose 5}\cdot 4^5$ 种。

      • 从所有 ${52 \choose 5}$ 种的手牌中减去，得到答案为 ${52 \choose 5} - {13\choose 5}\cdot 4^5$。

  • 例子：在平面直角坐标系中，从 $(0, 0)$ 点开始走，每次只能向上或向右走一步，欲到达 $(m, n)$，共有多少种路径？

    • 答：相当于计数在一个长度为 $m+n$ 的行动序列中，令 $m$ 个行动是“向右走”，剩下 $n$ 个行动是“向上走”的序列数。因为顺序任意，所以共有 ${m+n \choose m}$ 种。

  • 思考题：设 $m = n$，求此时除两端点外不接触直线 $y = x$ 的路径总数.

    • 提示：卡特兰数。

生成函数

  • 斐波那契数列： ${f_n}$ 满足 $f_0 = 0, f_1 = 1, f_n = f_{n-2} + f_{n-1}$，求 $f_n$ 的通项公式。

  • 答：定义: $F(x) = \sum_{i=1}^{\infty}f_i x^i$，将递推式同乘 $x^n$，得到： \(f_{n} x^{n} = x^{2} f_{n-2} x^{n-2} + x f_{n-1} x^{n-1}\)

    • 将上式对 $n = 2,3,···$ 累加，整理得到 \(F(x) - f_{0} - f_{1}x = x^{2}F(x) + x F(x) - x f_{0}.\)

    • 故而，$F(x) = x + x F(x) + x^{2}F(x)$，解得$F(x) = \frac{x}{1-x-x^2}$。

    • 最后解得

    \[f_n = \frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2} \right)^n - \frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2} \right)^n\]

  • 生成函数:一种强大的计数工具

    就像解析几何是替代传统几何的一种强大的、标准的工具一样，生成函数也是一种有很强普遍性的计数方法。

  • 使用生成函数来计数的方法（一）

    给定常数 $a_1, \ldots, a_d$ 、初始值 $f_1,\ldots, f_d$ 及线性递推关系

    \[f_n = a_1\cdot f_{n-1} + a_2\cdot f_{n-2} + \cdots + a_d \cdot f_{n-d}\]

    求解：$F(x) = \sum_{i=1}^\infty f_i x^i$。

    记 $h(x) = \sum_{i=1}^d h_i x^i$

    • $h_1 = a_1, h_2 = a_2 - a_1 f_1$,
    • $h_i = a_i - a_1 f_{i-1} - a_2 f_{i-2} - \cdots - a_{i-1} f_1, 2\le i < d$.
    • $h_d = a_d - a_1 f_{d-1} - a_2 f_{d-2} - \cdots - a_{d-1} f_1$.

    答案：$F(x) = \frac{h(x)}{1-(a_1x + a_2x^2 + \cdots + a_dx^d)}$.

  • 使用生成函数来计数的方法(二)

    • 从有 $n$ 个不同元素的集合中选择 $k$ 个元素. 方案数的生成函数是每个元素的生成函数之乘积. 即组合数 $f_k = C(n, k)$ 的生成函数: $(1 + x)^n$.
    • 选 $k$ 种可重复选取的元素的方案数的生成函数: $(1 − x)^{−k}$.
    • 混合选取 $n$ 个元素（单个 $k$ 种不同元素和 $m$ 种可重复选取的元素）方案数的生成函数: $(1 + x)^k(1 − x)^{−m}$.
    • 练习:个人的密码可以从数字和字母中选取. 每个字母只能用一次，数字可以任取多次. 问 8 位数的密码有多少个?

  • 使用生成函数来计数的方法(三)

    • 购买家具的要求: 至少三种红色，奇数种蓝色，黄色种数是 4 的倍数，最多一种黑色.
    • 生成函数: $\frac{x^3}{1-x}\frac{x}{1-x^2}\frac{1}{1-x^4} (1+x)$
    • 练习: 有多少种方法来买 9 套家具呢?

  • 使用生成函数来计数的方法(四)

    计算和式: $\sum_{n=0}^N n^2$.

    考虑生成函数 $f(x) = \sum_{n=0}^N x^n$，我们有 $f(x) = \frac{x^{N+1} - 1}{x - 1}$，利用导数法则

    \[\sum_{n=0}^{N}n^{2}=\left(x\frac{\mathrm d}{\mathrm d x}\right)^2 \frac{x^{N+1} - 1}{x - 1} \bigg |_{x=1} = \frac{N(N+1)(2N+1)}{6}.\]

    由于这里是有限和，没有收敛性问题，所以代入 x = 1 是合法的.

    老师找人上去算，我去试了下，结果计算量太大直接爆炸……求一层导数还行，两层就太离谱了。

    因为是纯机械的，所以可以丢给计算机算……