数学学院 2021 年转专业数学能力测试
阅读材料
组合计数, 是指对一个无穷的有限集合序列 $S_{1}, S_{2}, \cdots$, 给出其元素个数$f(1),f(2),\cdots$, 求出通项$f(n)$.为了方便,我们经常考虑下标从0开始,即集合序列为 $S_{0}, S_{1}, \cdots$, 元素个数分别为 $f(0), f(1), \cdots$, 并且记无穷序列 $$ \left(a_{0}, a_{1}, a_{2}, \cdots, a_{n}, \cdots\right) $$ 为 $\left(a_{n}\right)_{n \geq 0} .$ 例如 $$ (n)_{n \geq 0}=(0,1,2,3, \cdots), \quad\left(n^{2}\right)_{n \geq 0}=(0,1,4,9, \ldots). $$
计数结果的表示方式有以下几种:
1.具体的表达式
我们常用的表达式包括有理函数 $r(n)$ 、阶乘: $n !$ 升阶乘:
$$
(\alpha)_{n}=\alpha(\alpha+1) \cdots(\alpha + n - 1).
$$
组合数:
$$
\left(\begin{array}{l}
\alpha \\
k
\end{array}\right)=\frac{\alpha(\alpha-1) \cdots(\alpha-k+1)}{k !}.
$$
有理函数、升阶乘函数的乘积构成了一类称为超几何项的函数.
定义 1.1. 称 $f(n)$ 为超几何项, 如果 $f(n+1) / f(n)$ 是关于 $n$ 的有理函数.
2.逆推公式
有很多计数结果是一个递推公式.同时寻找递推关系也是计数的一个重要方法.
例如 Fibonacci 数列 $F_{n}$ 满足下面的递推关系:
$$
F_{n}=F_{n-1}+F_{n-2}.
$$
初值为 $F_{0}=F_{1}=1 .$ 它的具体表达式(记为*式)为
$$
F_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right].
$$
表达式不仅形式复杂, 更重要的是计算不方便.特别是在编程实现的时候, 递推关系可以给我们很大的方便.
3.渐近公式
有一些计数结果, 既没有表达式, 也没有递推公式, 例如不超过 $n$ 的素数的个数 $\pi(n)$ .即使有表达式或递推公式, 由于其复杂性, 也无法获得更多的信息.并且有时候我们更关心 $n$ 充分大的时候, 用常用函数表示的渐近性质.所以, 渐近公式也是一个非常重要的计数表示方式.
例如: $$ n ! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^{n}, \quad \pi(n) \sim n / \ln n, $$ 其中 $f(n) \sim g(n)$ 表示 $\displaystyle \lim _{n \rightarrow \infty} f(n) / g(n)=1$ .
4.生成函数
生成函数是利用形式幂级数表示计数结果的方式.假设序列 $\left(a_{n}\right)_{n \geq 0}$ 为计数函数, 则它的生成函数为 $$ f(x)=\sum_{n=0}^{\infty} a_{n} x^{n} . $$
设 $\displaystyle f(x)=\sum_{n=0}^{\infty} a_{n} x^{n}, g(x)=\sum_{n=0}^{\infty} b_{n} x^{n}$, 则它们的加法和乘法对应 的系数 $c_{n}$ 分别为: $$ f(x)+g(x)=\sum_{n=0}^{\infty}\left(a_{n}+b_{n}\right) x^{n}, \quad f(x) \cdot g(x)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n} a_{k} b_{n-k}\right) x^{n}. $$
全零序列的生成函数为 0, 序列 $(1,0,0, \cdots)$ 的生成函数为 1, 与我们通常的数 0,1 一致.
生成函数之所以成为很好的计数工具是因为它具有两个优点:
(a) 生成函数的和、积、求导、复合均有相应的组合意义, 可以很方便的进行计数.
(b) 另一方面, 形式幂级数运算的定义与幂级数的运算是一致的.我们可以将形式幕级数视为幂级数,从而成为一个关于 $x$ 的函 数.这样, 我们可以利用对函数的演算合性质得到形式幂级数的性质.
测试题
一. (a) 组合数 $\left(\begin{array}{l}2 n \\ n\end{array}\right)$ 是否是关于 $n$ 的超几何项? 请证明你的结论.
(b) 利用 Stirling 公式 $$ n ! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^{n} , $$ 给出 $\left(\begin{array}{c}2 n \\ n\end{array}\right)$ 的渐近公式.
二. 考虑由所有无穷序列 $\left(a_{n}\right)_{n \geq 0}$ 构成的集合 $X$, 其中每个 $a_{n}$ 均为实数. 在 $X$ 中定义加法和数乘 $$ \left(a_{n}\right)_{n \geq 0}+\left(b_{n}\right)_{n \geq 0}=\left(a_{n}+b_{n}\right)_{n \geq 0}, \quad \lambda \cdot\left(a_{n}\right)_{n \geq 0}=\left(\lambda a_{n}\right)_{n \geq 0}. $$ 则 $X$ 构成线性空间, 零元素为全零序列 $(0)_{n \geq 0}$.
令 $$ S=\left\{\left(a_{n}\right)_{n \geq 0} \mid a_{n+2}=a_{n}+a_{n+1}, \quad \forall n \geq 0\right\}. $$
(a) 证明: $\left(\alpha^{n}\right)_{n \geq 0}$ 和 $\left(\beta^{n}\right)_{n \geq 0}$ 线性无关, 其中 $$ \alpha=\frac{1+\sqrt{5}}{2}, \quad \beta=\frac{1-\sqrt{5}}{2}. $$
(b) 证明： $S$ 构成 $X$ 的子空间.
(c) 计算 $S$ 的维数.
(d) 证明 Fabonacci 序列的显示公式 $\left(^{*}\right)$.
三. 假设序列 $\left(a_{n}\right)_{n \geq 0}$ 满足 $a_{0}=1$, 递推关系为 $$ a_{n+1}=\sum_{k=0}^{n} a_{k} a_{n-k}, \quad \forall n \geq 0. $$
令其生成函数为 $$ C(x)=\sum_{n=0}^{\infty} a_{n} x^{n}. $$
(a) 证明: $$ C(x)=1+x C(x) C(x). $$
(b) 给出 $C(x)$ 的一个表达式.
(c) 给出 $a_{n}$ 的一个表达式.