组合数学笔记

第一章组合数学基础

相异元素不允许重复的排列 $P(n, r)$
- 球盒模型：将$r$ 个有区别的球放入 $n$ 个不同的盒子里，每盒不超过一个。
- 计算公式：$$ P(n, r)=\frac{n!}{(n-r)!} $$
- 集合描述：$$ S=\{1 \cdot e_1, 1 \cdot e_2,…,1 \cdot e_n\} $$
相异元素允许重复的排列 $RP(\infty, r)$
- 球盒模型：将$r$ 个有区别的球放入 $n$ 个不同的盒子里，每个盒子的球数不加限制而且同盒的球不分次序。
- 计算公式：$$ RP(\infty, r) = n^r $$
- 集合描述：$$ S=\{\infty \cdot e_1, \infty \cdot e_2,…,\infty \cdot e_n\} $$
不尽相异元素的全排列
- 球盒模型：将$r$个有区别的球放入$t$个不同的盒子，每个盒子的容量是有限的，其中第$i$个盒子最多只能放入$n_i$个球，同盒的球不分次序。
- 集合描述：$$ S=\{ n_1 \cdot e_1, n_2 \cdot e_2,…,n_t \cdot e_t \}, n_1+n_2+…+n_t=n $$
- 特例
  - $r=1$ $$ RP(n, 1) = t $$
  - $r=n$ $$ RP(n, n) = \frac{n!}{n_1!n_2!…n_t!} $$
相异元素不允许重复的圆排列 $CP(n, r)$ $$ CP(n, r) = \frac{P(n, r)}{r} = \frac{n!}{r(n-r)!} $$
项链排列 $$ \frac{P(n, r)}{2r} = \frac{n!}{2r(n-r)!} $$

相异元素不允许重复的组合 $C(n, r)$
- 球盒模型：将$r$ 个无区别的球放入 $n$ 个不同的盒子里，每盒不超过一个。
- 计算公式：$$ P(n, r)=\frac{n!}{(n-r)!r!} $$
相异元素允许重复的组合 $RC(\infty, r)$
- 球盒模型：将$r$ 个无区别的球放入 $n$ 个不同的盒子里，每个盒子的球数不加限制。
- 计算公式：$$ RC(\infty, r)=C(n+r-1, r)=\frac{(n+r-1)!}{r!(n-1)!} $$
不尽相异元素任取$r$个组合问题 $RC(n, r)$
- 球盒模型：将$r$个无区别的球放入$t$个不同的盒子，每个盒子的容量是有限的，其中第$i$个盒子最多只能放入$n_i$个球，同盒的球不分次序。
- 集合描述：$$ S=\{ n_1 \cdot e_1, n_2 \cdot e_2,…,n_t \cdot e_t \}, n_1+n_2+…+n_t=n $$ 多项式$$ \prod_{i=1}^{t}{\sum_{j=0}^{n_i}{x^j}}=\prod_{i=1}^{t}{(1+x+x^2+…+x^{n_i})}=\sum_{r=0}^{n}{a_rx^r} $$ 则$RC(n, r)$就是多项式中$x^r$的系数，即$RC(n, r)=a_r$。

问题：将$n$个相异的球放入$t$个盒子，要求第$i$个盒子里放入$n_i$个，且盒中的球无次序。
计算公式：$$ RP(n, n)=\frac{n!}{n_1!n_2!…n_t!} $$仿照二项式系数$\begin{pmatrix}n \\ r \end{pmatrix}$，将其记为$\begin{pmatrix}n \\ n_1n_2…n_t \end{pmatrix}$
多项式展开的项数
- $(x_1+x_2+…+x_t)^n$展开的项数等于$C(n+t-1, n)$
- 系数之和为$t_n$

$$ a_n + c_1a_{n-1}+c_2a_{n-2}+…+c_ka_{n-k}=0, (c_k \ne 0) \ \ (3.2.1) $$

定义3.2.1 称多项式 $$ C(x)=x^k + c_1x^{k-1} + c_2x^{k-2}+…+c_{k-1}x + c_k $$ 为齐次递推关系（3.2.1）的特征多项式，相应的代数方程 $$ C(x)=x^k + c_1x^{k-1} + c_2x^{k-2}+…+c_{k-1}x + c_k = 0 $$称为（3.2.1）的特征方程，特征方程的解称为（3.2.1）的特征根。
定理3.2.1 数列 $a_n = q^n$ 是（3.2.1）的非零解的充分必要条件是是 $q$ 为（3.2.1）的特征根。
特征根法

	特征根	通解中对应的项
实根	$q$ 为单根	$Aq^n$
	$m$ 重根	$(A_1+A_2n+…+A_mn^{m-1})q^n$
复根	一对单复根 $q=\rho e^{i\theta}, \bar{q} = \rho e^{-i\theta}$	$\rho [A_1cos(n\theta)+A_2sin(n\theta)]$
	一对$m$重复根$q=\rho e^{i\theta}, \bar{q} = \rho e^{-i\theta}$	$ \rho[(A_1+A_2n+…+A_mn^{m-1})cos(n\theta)+(B_1+B_2n+…+B_mn^{m-1})sin(n\theta)] $

$$ a_n + c_1a_{n-1}+c_2a_{n-2}+…+c_ka_{n-k}=0, (c_k \ne 0) \ \ (3.2.2) $$

$$ a_n=a_n^{*}+\bar{a_n} $$

待定系数法求特解
- $f(n)=b$ $$ a_n^{*} = An^m $$ 其中$m$表示$1$是$m$重特征根($0 \le m \le k$)。当然，若 $1$ 不是特征根（即$m=0$），则$a_n^{ * }=A$
- $f(n)=b^n$ $$ a_n^{*} = An^mb^n $$ 其中$m$表示$b$是（3.3.1）的$m$重特征根($0 \le m \le k$)。若$b$不是特征根（即$m=0$），则$a_n^{ * }=Ab^n$
- $f(n)=b^nP_r(n)$ $$ a_n^{*} = n^mb^nQ_r(n) $$ 其中$Q_r(n)$是与$P_r(n)$同次的多项式，$m$表示$b$是（3.3.1）的$m$重特征根($0 \le m \le k$)。若$b$不是特征根（即$m=0$），则$a_n^{ * }=b^nQ_r(n)$