组合数学总结

一、组合数学基础

1.1 排列与组合

排列

1. 相异元素不允许重复的排列
   $$P_n^r=P(n,r)=\frac{n!}{(n-r)!}$$

2. 相异元素允许重复的排列

   从n个不同元素中允许重复的选r个元素的排列，对应的分配模型时将r个有区别的球放入n个不同的盒子，同盒的球不加以区分，每个盒子的球数不加限制且同盒的球不分次序
   $$RP(oo,r)=n^r$$

3. 不尽相异元素的排列

   设S={n1·e1, n2·e2, …nt·et}，即元素ei有ni个，且n1+n2+…+nt=n，从S中任取r个元素，求其排列数

   将r个有区别的球放入t个不同的盒子，每个盒子的容量有限，其中第i个盒子最多放ni个球，求分配方案数
   $$\begin{gathered} r==1时，RP(n,1)=P_t^1=t \\ r==n时，RP(n,n)=\frac{n!}{n_1!n_2!...n_t!} \end{gathered}$$

4. 相异元素不允许重复的圆排列

   $$CP(n,n)=\frac{P(n,n)}{n}=(n-1)!$$
   $$CP(n,n)=(n-1)!$$

例题：

项链排列

隔板思想

组合

1. 相异元素不允许重复的组合
   $$C_n^r==C(n,r)=\frac{P_n^r}{r!}=\frac{n!}{(n-r)!r!}$$

2. 相异元素允许重复的组合

   设S={oo · e1, oo · e2, …oo · en}，从S中允许重复的取r个元素构成组合，称r可重组合RC(oo, r)

对应于，将r个无区别的球放入n个不同的盒子，每个盒子的球数不受限制
$$RC(oo,r)=C(n+r-1,r)=\frac{(n+r-1)!}{r!(n-1)!}$$

1.2 组合等式及其组合意义

1. 对称关系式
   $$C(n,r)=C(n,n-r)$$

2. 加法公式
   $$C(n,r)=C(n-1,r)+C(n-1,r-1)$$

3. 乘法公式
   $$C(n,k)C(k,r)=C(n,r)C(n-r,k-r)$$

1.3 多项式系数

当n是正整数时，Newton二项式定理
( a + b ) n = ∑ r = 0 n ( n r ) a r b n − r 组 合 数 ( n r ) 叫 做 二 项 式 系 数 (a+b)^n=\sum_{r=0}^n\left (nr

\right)a^rb^{n-r} \\\\ \quad \quad \newline 组合数\left (nr\right)叫做二项式系数 (a+b)n=r=0∑n​(nr​)arbn−r组合数(nr​)叫做二项式系数

定理：
$$\begin{gathered} (x_1+x_2+...+x_t{)}^n展开式的项数等于C(n+t-1,n)， \\ 而这些项的系数之和为t^n \end{gathered}$$

例题

二、母函数

2.1 普母函数

定义：
$$\begin{gathered} 对于数列a_n，称无穷级数G(x)=\sum _{n=0}^{oo}{a}_n{x}^n为该数列的普通型母函数， \\ 简称普母函数或母函数，同时称a_n为G(x)的生成数列 \end{gathered}$$

定理：组合数的母函数
设 S = { n 1 ⋅ e 1 ， n 2 ⋅ e 2 ， . . . ， n m ⋅ e m } ， 且 n 1 + n 2 + . . . n m = n ， 则 S 的 r 可 重 组 合 的 母 函 数 为 G ( x ) = ∏ i = 1 m ( ∑ j = 0 n i x j ) = ∑ r = 0 n a r x r 其 中 ， r 可 重 组 合 数 为 x r 的 系 数 a r ， r = 0 ， 1 , 2... n 设S={n1·e1，n2·e2，...，nm·em}

，且n_1+n_2+...n_m=n，\\\\ \quad \quad \newline 则S的r可重组合的母函数为 \quad G(x)=\prod_{i=1}^m(\sum_{j=0}^{n_i}x^j)=\sum_{r=0}^na_rx^r \\\\ \quad \quad \newline 其中，r可重组合数为x^r的系数a_r，r=0，1,2...n \quad \quad \quad \quad 设S={n1​⋅e1​，n2​⋅e2​，...，nm​⋅em​​}，且n1​+n2​+...nm​=n，则S的r可重组合的母函数为G(x)=i=1∏m​(j=0∑ni​​xj)=r=0∑n​ar​xr其中，r可重组合数为xr的系数ar​，r=0，1,2...n

推论
1.
S = { e 1 ， e 2 ， . . . ， e n } ， 则 r 无 重 组 合 的 母 函 数 为 G ( x ) = ( 1 + x ) n 组 合 数 为 x r 的 系 数 C ( n , r ) S={e1，e2，...，en}

，则r无重组合的母函数为 \\ \quad \quad \newline G(x)=(1+x)^n \\ \quad \quad \newline 组合数为x^r的系数C(n,r) S={e1​，e2​，...，en​​}，则r无重组合的母函数为G(x)=(1+x)n组合数为xr的系数C(n,r)
2.
$$\begin{gathered} S=\left\{\begin{array}{c}oo\cdot e_1，oo\cdot e_2，...，oo\cdot e_n\end{array}\right\}，则r无限可重组合的母函数为 \\ G(x)=(\sum _{j=0}^{oo}{x}^j{)}^n=\frac{1}{(1-x{)}^n} \\ 组合数为x^r的系数C(n+r-1,r) \end{gathered}$$

S = { o o ⋅ e 1 ， o o ⋅ e 2 ， . . . ， o o ⋅ e n } ， 每 个 元 素 至 少 取 一 个 ， 则 r 可 重 组 合 ( r ≥ n ) 的 母 函 数 为 G ( x ) = ( ∑ j = 1 o o x j ) n = ( x 1 − x ) n 组 合 数 为 x r 的 系 数 C ( r − 1 , n − 1 ) S={oo·e1，oo·e2，...，oo·en}

，每个元素至少取一个， \\ \quad \quad \newline则r可重组合(r≥n)的母函数为 \quad \quad G(x)=(\sum_{j=1}^{oo}x^j)^n=(\frac{x}{1-x})^n \\ \quad \quad \newline 组合数为x^r的系数C(r-1,n-1) S={oo⋅e1​，oo⋅e2​，...，oo⋅en​​}，每个元素至少取一个，则r可重组合(r≥n)的母函数为G(x)=(j=1∑oo​xj)n=(1−xx​)n组合数为xr的系数C(r−1,n−1)
4.
$$\begin{gathered} S=\left\{\begin{array}{c}oo\cdot e_1，oo\cdot e_2，...，oo\cdot e_n\end{array}\right\}，每个元素出现非负偶次数， \\ 则r可重组合的母函数为G(x)=(1+x^2+x^4+...+x^{2r}+...)=\frac{1}{(1-x^2{)}^n} \\ 组合数为x^r的系数a_r=\{\begin{array}{r}0，当r为奇数\\ C(n+\frac{r}{2}-1，\frac{r}{2})，当r为偶数\end{array} \end{gathered}$$

例题

二次分配问题

2.2 指母函数

定义
对 于 数 列 { a k } = { a 0 , a 1 , a 2 . . . } G e ( x ) = ∑ n = 0 o o a n x n n ! = a 0 + a 1 x 1 ! + a 2 x 2 2 ! + . . . + a n x n n ! + . . . 称 为 数 列 { a k } 的 指 数 型 母 函 数 ， 简 称 指 母 函 数 ， 而 数 列 { a k } 称 为 指 母 函 数 G e ( x ) 的 生 成 序 列 对于数列{ak}

={a0,a1,a2...} \\ \quad\newline G_e(x)=\sum_{n=0}^{oo}a_n\frac{x^n}{n!}=a_0+a_1\frac{x}{1!}+a_2\frac{x^2}{2!}+...+a_n\frac{x^n}{n!}+... \\ \quad\newline 称为数列{ak}的指数型母函数，简称指母函数， \\ \quad\newline 而数列{ak}称为指母函数G_e(x)的生成序列 对于数列{ak​​}={a0​,a1​,a2​...​}Ge​(x)=n=0∑oo​an​n!xn​=a0​+a1​1!x​+a2​2!x2​+...+an​n!xn​+...称为数列{ak​​}的指数型母函数，简称指母函数，而数列{ak​​}称为指母函数Ge​(x)的生成序列

定理
设 重 集 S = { n 1 ⋅ e 1 ， n 2 ⋅ e 2 ， . . . ， n m ⋅ e m } ， 且 n 1 + n 2 + . . . + n m = n ， 则 S 的 可 重 排 列 的 指 母 函 数 为 G e ( x ) = ∏ i = 1 m ( ∑ j = 0 n i x j j ! ) = ∑ r = 0 n a r x r r ! 其 中 ， r 可 重 排 列 数 为 x r r ! 的 系 数 a r ， r = 0 , 1 , 2 , . . . n 设重集S={n1·e1，n2·e2，...，nm·em}

，\\ \quad\newline 且 n_1+n_2+...+n_m=n，则S的可重排列的指母函数为 \\ \quad\newline G_e(x)=\prod_{i=1}^m(\sum_{j=0}^{n_i}\frac{x^j}{j!})=\sum_{r=0}^na_r\frac{x^r}{r!} \\ \quad\newline 其中，r可重排列数为\frac{x^r}{r!}的系数a_r，r=0,1,2,...n 设重集S={n1​⋅e1​，n2​⋅e2​，...，nm​⋅em​​}，且n1​+n2​+...+nm​=n，则S的可重排列的指母函数为Ge​(x)=i=1∏m​(j=0∑ni​​j!xj​)=r=0∑n​ar​r!xr​其中，r可重排列数为r!xr​的系数ar​，r=0,1,2,...n

例题

二次分配问题

2.3 正整数分拆

定义：将一个正整数n分解成k个正整数之和
{ n = n 1 + n 2 + . . . + n k ， k ≥ 1 n i ≥ 1 ， i = 1 ， 2 ， . . . ， k \left\{ n=n1+n2+...+nk，k≥1ni≥1，i=1，2，...，k

\right. {n=n1​+n2​+...+nk​，k≥1ni​≥1，i=1，2，...，k​
称该分解是n的一个k分拆，并称n_i为分量。

按照对ni是否要考虑顺序，将分拆分为有序分拆和无序分拆

2.3.1 有序拆分

求n的k有序分拆的个数，相当于求一次不定方程全体正整数解的组数，可对每个分量n_i加以条件限制，例如1 ≤ ni ≤ ri (i = 1, 2, …, k).

定理：对于n的k有序分拆
{ n = n 1 + n 2 + . . . + n k ， k ≥ 1 1 ≤ n i ≤ r i ， i = 1 ， 2 ， . . . ， k \left\{ n=n1+n2+...+nk，k≥11≤ni≤ri，i=1，2，...，k

\right. {n=n1​+n2​+...+nk​，k≥11≤ni​≤ri​，i=1，2，...，k​

其k有序分拆数列{ qk(n) }的母函数是

$$\begin{gathered} \prod _{i=1}^k(\sum _{j=1}^{r_i}{x}^j)=(x+x^2+...+x^{r_1})(x+x^2+...+x^{r_2}...)(x+x^2+...+x^{r_k}) \\ (x^1表示1个1，x^2表示2个1） \end{gathered}$$
这个定理等价于，把n个相同的球放入k个不同的盒子里，第i个盒子容量为ri，且使每盒非空

推论：若对n的k有序分拆的各分量ni没有限制，则
其 k 有 序 分 拆 数 数 列 { q k ( n ) } 的 母 函 数 为 ( x 1 − x ) k ， 且 q k ( n ) = C ( n − 1 , k − 1 ) 证 明 ： n = n 1 + n 2 + . . . + n k n − k = ( n 1 − 1 ) + ( n 2 − 1 ) + . . . + ( n k − 1 ) n − k 个 连 续 的 1 中 间 插 入 k − 1 个 0 ， 即 分 为 k 堆 ， C ( n − k + k − 1 , k − 1 ) = C ( n − 1 , k − 1 ) 其k有序分拆数数列{qk(n)}

的母函数为(\frac{x}{1-x})^k，且 \\\\ \quad \newline q_k(n)=C(n-1,k-1) \\ \quad \newline 证明： n=n_1+n_2+...+n_k \\ \quad \newline n-k=(n_1-1)+(n_2-1)+...+(n_k-1) \\ \quad \newline n-k个连续的1中间插入k-1个0，即分为k堆，C(n-k+k-1,k-1)=C(n-1,k-1) 其k有序分拆数数列{qk​(n)​}的母函数为(1−xx​)k，且qk​(n)=C(n−1,k−1)证明：n=n1​+n2​+...+nk​n−k=(n1​−1)+(n2​−1)+...+(nk​−1)n−k个连续的1中间插入k−1个0，即分为k堆，C(n−k+k−1,k−1)=C(n−1,k−1)

2.3.2 无序拆分

在n的分拆中，不考虑各分量的顺序，就是有序分拆

可以将分拆后的各项数值从大到小加以排序，即有
{ n = n 1 + n 2 + . . . + n k ， k ≥ 1 n 1 ≥ n 2 ≥ n 3 ≥ . . . ≥ n k ≥ 1 满 足 以 上 条 件 的 每 一 组 正 整 数 解 就 代 表 一 个 n 的 k 无 序 分 拆 其 分 拆 数 记 为 p k ( n ) ， n 1 称 为 最 大 分 项 \left\{ n=n1+n2+...+nk，k≥1n1≥n2≥n3≥...≥nk≥1

\right. \\ \quad \newline 满足以上条件的每一组正整数解就代表一个n的k无序分拆 \\\\ \quad \newline 其分拆数记为p_k(n)，n_1称为最大分项 \quad \quad \quad {n=n1​+n2​+...+nk​，k≥1n1​≥n2​≥n3​≥...≥nk​≥1​满足以上条件的每一组正整数解就代表一个n的k无序分拆其分拆数记为pk​(n)，n1​称为最大分项

将n分拆为k项(每一项的大小不受限制)的分拆数等于将n分拆为最大分项为k(分项个数不限)的分拆数。

把n分拆为最大分项等于k，其分拆数相当于求不定方程
{ 1 x 1 + 2 x 2 + 3 x 3 + . . . + k x k = n x i ≥ 0 , i = 1 , 2 ， . . . k − 1 , x k ≥ 1 \left\{ 1x1+2x2+3x3+...+kxk=nxi≥0,i=1,2，...k−1,xk≥1

\right. {1x1​+2x2​+3x3​+...+kxk​=nxi​≥0,i=1,2，...k−1,xk​≥1​
的整数解的组数。即整数n由1,2，…,k允许重复且k至少出现一次的所有组合数，其母函数为
$$\begin{gathered} (1+x+x^2+...)(1+x^2+(x^2{)}^2...)(1+x^3+(x^3{)}^2+...)...(x^k+(x^k{)}^2+(x^k{)}^3+...) \\ \frac{x^k}{(1-x)(1-x^2)...(1-x^k)}=\sum _{n=k}^{oo}{p}_k(n)x^n \end{gathered}$$
其中展开式中x^n的系数即为n的最大分项等于k的分拆个数

若最大分项小于或等于k，其分拆数相当于求不定方程
{ 1 x 1 + 2 x 2 + 3 x 3 + . . . + k x k = n x i ≥ 0 ， i = 1 ， 2 ， 3 ， 4... k \left\{ 1x1+2x2+3x3+...+kxk=nxi≥0，i=1，2，3，4...k

\right. {1x1​+2x2​+3x3​+...+kxk​=nxi​≥0，i=1，2，3，4...k​
其分拆数列母函数为
$$\begin{gathered} (1+x+x^2+...)(1+x^2+(x^2{)}^2...)(1+x^3+(x^3{)}^2+...)...(1+x^k+(x^k{)}^2+...) \\ \frac{1}{(1-x)(1-x^2)...(1-x^k)}=\sum _{n=0}^{oo}{r}_k(n)x^n \end{gathered}$$
其中展开式中x^n的系数即为n的最大分项不超过k的分拆个数

三、递推关系

3.1 常系数线性递推关系

$$\begin{gathered} k阶齐次递推关系：a_n+c_1{a}_{n-1}+c_2{a}_{n-2}+...+c_k{a}_{n-k}=0，c_k\ne 0(3.1.1) \\ k阶非齐次递推关系：a_n+c_1{a}_{n-1}+c_2{a}_{n-2}+...+c_k{a}_{n-k}=f(n)，c_k\ne 0(3.1.2) \end{gathered}$$

特征根法

1.齐次递推关系

1.1. 特征根为单根
设q1，q2，…，qn是式(3.1.1)的互不相同的特征根，则式(3.1.1)的通解为
$$a_n=A_1{q}_1^n+A_2{q}_2^n+...+A_k{q}_k^n$$

例题

1.2. 重根情况
一般情况下，设q是式(3.2.1)的k重解，则，式(3.1.1)的通解为
$$a_n=(A_1+A_{2}n+...+A_k{n}^{k-1})q^n$$

1.3. 复根情况
一般情况，设q是m重复根，自然q’也是m重复根，则通解为
$${\rho }^n[(A_1+A_{2}n+...+A_m{n}^{m-1})cos(n\theta )+(B_1+B_{2}n+...+B_m{n}^{m-1})sin(n\theta )]$$

例题

2.非齐次方程

设a*是式(3.1.2)的一个特解，a’n是式(3.1.1)的通解，则式(3.1.2)的通解为
$$a_n=a_n^{\ast }+{\hat{a}}_n$$

2.1. f(n) = b (b为常数)
$$a_n^{\ast }=A{n}^m$$
其中，m表示1是式(3.1.1)的m重特征根(0≤m≤k），若1不是特征根（即m=0）
$$a_n^{\ast }=A$$

例题

2.2. f(n) = b^n (b为常数)
$$a_n^{\ast }=A{n}^m{n}^n$$
其中m表示b是式(3.1.1)的m重特征根(0≤m≤k）, 若b不是特征根(即m=0)
$$a_n^{\ast }=A{b}^n$$

例题

2.3. f(n) = b^n Pr(n) (其中Pr(n)为关于n的r次多项式，b为常数)
$$a_n^{\ast }=n^m{b}^n{Q}_r(n)$$
其中Qr(n) 是与Pr(n)同次的多项式，b是式(3.1.1)的m重特征根(0≤m≤k）, 若b不是特征根(即m=0)
$$a_n^{\ast }=b^n{Q}_r(n)$$

例题

母函数方法

对于一些复杂的递推关系，利用母函数方法求解很有效，当用它求解数列{an}的递推关系时，首先作出{an}的母函数
$$G(x)=\sum _{n=0}^{oo}$$
并以他为媒介，将给定的递推关系转化为关于G(x)的方程，然后解出G(x)，再将G(x)展开成x的幂级数，x^n的系数便是an

例题

Stirling数列

下阶乘函数
$$\begin{gathered} [x{]}_n=x(x-1)(x-2)...(x-(n-1)),[x{]}_0=1 \\ [x{]}_n=[x{]}_{n-1}\ast (x-(n-1))) \end{gathered}$$

$$\begin{gathered} [x{]}_n=\sum _{k=0}^n{S}_1(n,k)x^k,其中S_1(n,k)为第一类Stirling数 \\ [x{]}^n=\sum _{k=0}^n{S}_2(n,k)x_k,其中S_2(n,k)为第二类Stirling数 \end{gathered}$$

Striling数的组合意义

• 分配问题：将n个有区别的球放入m个相同的盒子，要求各盒不空，则不同的放法为S2(n,m)
• 集合的划分：将含有n个元素的集合恰好分成m个无序非空子集的所有不同划分的数目即S2(n,m)。这种划分也称为集合的m划分

第一类Stirling数的性质

1. S1(n,0)=0
2. S1(n,1)=(n-1)!(-1)^(n-1)
3. S1(n,n)=1
4. S1(n,n-1)=-C(n,2)
5. sgn(S1(n,k))=(-1)^(n+k)
6. S1(n,k)满足递推关系
   $$S_1(n,k)=S_1(n-1,k-1)-(n-1)S_1(n-1,k)$$

第二类Stirling数的性质

1. S2(n,0)=0, n>0
2. S2(n,1)=1, n≥1
3. S2(n,n)=1
4. S2(n,n-1)=C(n,2)
5. S2(n,2))=2^(n-1)-1
6. S2(n,k)满足递推关系
   $$S_2(n,k)=S_2(n-1,k-1)+k{S}_2(n-1,k)$$