组合数学

[TOC]

概述

研究三大问题:存在性、计数性、优化性。

幻方

3x3 的方格填 $0-9$ ,使每一行、每一列、对角线的和都为15。也可以扩展到 n x n 的方格内放 0-n*n 的数字。

定义:

  • 幻和 s:每一行、列、对角线的和。对 n*n 的幻方 $s=\frac{n(n^2+1)}{2}$ 。 证明如下: 看每一行 \(ns = \sum_{i=0}^{n^2} i = \frac{n^2(n^2+1)}{2}\) 所以 $s=\frac{n(n^2+1)}{2}$

  • 二阶幻方不存在。 $n>3$ 的幻方都存在。

  • 构造方法: 奇数阶: 1放在第一行中间,每次向右上角移动,把棋盘看作是循环的,如果目标位置已经存在数字,把当前位置放在移动前的位置的下方。 4n阶:……

    2(2n+1)阶:……

  • n 阶幻方的种类数:目前只知道 6 阶幻方种类数所在范围,并不知道具体值,更大的更无从谈起。每增加一阶方案数会暴增。

戈尼斯堡七桥问题

  • 奇数点:度数为奇数
  • 偶数点:度数为偶数
  • 能一次走完所有边的充要条件:奇数点的个数为0或2
  • 欧拉路的方案数。

圆排列和项链排列

圆排列:从 $n$ 个中取 $r$ 个的圆排列的排列数为 $ A_n^r/r \quad (2\le r\le n)$

把圆排列的翻转前后的两种情况看作一种,从 $n$ 个中取 $r$ 个的圆排列的排列数为 $ A_n^r/2r \quad (3\le r\le n)$

多重排列

有 n 种元素,每种 $r_i$ 个的排列方案数有 $C(n;r_1,r_2,…,r_t) = \frac{n!}{r_1!r_2!…r_t!} $

$(a_1+a_2+…+a_t)^n = \sum \frac{n!}{r_1!…r_t!}a_1^{r_1}…a_t^{r_t} \quad \sum r_i = n$

可重组合

从 n 种数可重复的取 r 的方案数。相当于取 r 个无标志的球,n 个有区别的盒子,每个盒子允许放多个球或空的方案数。

$C_{n+r-1}^{r}$

不相邻组合

从 $A={1,2,…,n}$ 中取 $r$ 个不相邻的数进行组合与从 $(n-r+1)$ 个元素中取 $r$ 个进行无重组合一一对应,其组合数为 $C_{n-r+1}^{r}$

全排列的生成

## 字典序法

从右向左第一个降序的数字与它后面的比它大的最小的数交换,并对它后面位置的值排序。 如 $839647521$ 的下一个排列的寻找过程如下: $8396\dot{4}7521 \rightarrow 8396 \dot{5}7\dot{4}21 \rightarrow 83965\dot{1}\dot{2}\dot{4}\dot{7} $

SJT算法

每个数字有一个初始方向,若数字的方向指向的数比它小,则称这个数是可移动数,每次移动最大的可移动数,每次移动时所有比当前数大的数的方向指向之前的相反方向。 例如:$123 \rightarrow 132 \rightarrow 312 \rightarrow 321 \rightarrow 231 \rightarrow 213$

长度为 n 的第 m 个全排列

让构造长为 n 的第 m 个全排列。

初始数列是 $1,2,3,…,n$ 。

  • 1开头的全排列有 (n-1)! 种

下面的删除和查找可以用权值线段树替代,都可以做到 $O(logn)$ 的时间复杂度。不过由于 n! 骤增,s 会很短,效率不会有明显的提高。

1
2
3
4
5
6
7
8
9
10
11
void solve(int n, int m){ // 长为n的第m个全排列
    int f[100]; f[0] = 1; string s = "";
    for(int i=1; i<=n; i++) f[i] = i*f[i-1], s += char(i+'0');
    m --;
    for(int i=n; i>=1; i--){
        int x = m / f[i-1];
        m %= f[i-1];
        cout << s[x] << " ";
        s.erase(x, 1);
    } cout << endl;
}

母函数

定义

用来计数

且:乘法法则;或:加法法则。

例子:掷两个骰子点数之和为6的所有方案数。

用 $x^a$ 表示筛子的点数是 $a$ ,则每一个筛子的所有情况可以表示为$(x+x^2+x^3+x^4+x^5+x^6)$ ,则两个骰子可以表示为$(x+x^2+x^3+x^4+x^5+x^6)(x+x^2+x^3+x^4+x^5+x^6)$ ,点数之和为 $6$ 可以表示为多项式展开后的 $x^6$ 的系数,两个骰子的情况 $x^6$ 的系数是 $5$ 。

这里的 $x$ 的可谓是真真切切的未知数,不单单是不知道它的数值,而是根本不用考虑它,完完全全是一个呼之即来挥之即去的工具人,我们通过它完成对问题映射,映射为更易研究的形式,以应对更复杂的情况。可以看到我们不再关注多项式的未知数,而是关注未知数的系数。

之所以采用幂次来表示一个骰子的点数,是因为幂次的运算有良好的性质,即一个数的不同幂次相乘可以变成幂次相加的形式,这一性质刚好可以满足现实情况中想用乘来表示的关系。

再多几个骰子也类似,直接计算这个系数就行了。每个骰子用一个多项式表示,对于 $m$ 个骰子可以定义一个生成函数 \(G(x) = (x+x^2+x^3+x^4+x^5+x^6)^m\) 想找相加为 $n$ 的情况,算出 $x^n$ 的系数即可。

应用

四个砝码分别重1g,2g,3g,4g,问总共可以组合出多少重量,每种的组合方式有多少种?

1g砝码可以表示:1(不要)或 x (要)

2g砝码可以表示:1(不要)或 x^2 (要)

所以有生成函数 \(\begin{align*} G(x) &= (1+x)(1+x^2)(1+x^3)(1+x^4) \\ &= x^{10}+x^9+x^8+2x^7+2x^6+2x^5+2x^4+2x^3+x^2+x+1 \end{align*}\) 问题答案呼之欲出,幂次表示可称出的重量,系数表示对应的方案数。

用什么样的砝码可以唯一的确定一个重量。

考虑 $1,2,4,8,16,32…$ \(\begin{align*} G(x) &= (1+x)(1+x^2)(1+x^4)(1+x^8)(1+x^{16})(1+x^{32}) \\ &= \frac{1-x^2}{1-x}\frac{1-x^4}{1-x^2}\frac{1-x^8}{1-x^4}\frac{1-x^{16}}{1-x^8}\frac{1-x^{32}}{1-x^{16}}\frac{1-x^{64}}{1-x^{32}} \\ &= \frac{1-x^{64}}{1-x} \\ &= 1+x+x^2+x^3+...+x^{63} \\ &= \sum_{i=0}^{63}x^i \end{align*}\) 所以用 2 的幂次的砝码重量可以唯一的称出每个重量。

整数拆分

有有序拆分和无序拆分两种形式。

有序拆分

相当于把 $n$ 个球放到 $r$ 个盒子中,用隔板法,把 $n$ 个球分成 $r$ 份(非空)相当于在 $n-1$ 个位置放 $r-1$ 个隔板,总方案数就是 $C_{n-1}^{r-1}$ 个。

无序拆分

相当于把 n 个无区别的球放入 r 个无区别的盒子中,且盒子可空的方案数,记作 $P(n)$。

母函数表示形式 \(\begin{align*} G(x) &= (1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)...(1+x^m+x^{2m}+...)... \\ &= \frac{1}{1-x}\frac{1}{1-x^2}...\frac{1}{1-x^m} \\ &= \frac{1}{(1-x)(1-x^2)...(1-x^m)} \end{align*}\)

FERRERS图像

TIM截图20191210204951

图像保证是非上升的。

性质:

  1. n 拆分成最大数为 k 的方案数 和 n 拆分成 k 个数的方案数相等。对应于Ferrers图像翻转前后表示的意义。

  2. n 拆分成最大不超过 k 的方案数 和 n 拆分成最多不超过 k 个数的方案数相等。

  3. n 拆分成若干奇数和的方案数 和 n 拆分成自共轭的Ferrers图像的方案数相等(反转之后图像不变)。

递推问题和母函数

汉诺塔(HANOI)问题

$h(n) = 2h(n-1) + 1$

对于汉诺塔问题,我们想要求的是 $h(n)$ 的值,可以先构造一个生成函数,让 $h(n)$ 作为 $x^n$ 的系数,有 \(\begin{align*} G(x) &= h(1)x+h(2)x^2+h(3)x^3+... &(1)\\ -2xG(x) &= -2h(1)x^2-2h(2)x^3-2h(3)x^3+... &(2) \\ (1-2x)G(x) &= h(1)x+(h(2)-2h(1))x^2+(h(3)-h(2))x^3+...&(1)+(2)\\ &= x+x^2+x^3+... \\ &= \frac{x}{1-x} \\ G(x) &= \frac{x}{(1-x)(1-2x)} = \sum_{k=1}^{\infty}h(k)x^k &(3) \\ &= \frac{1}{1-2x}-\frac{1}{1-x} \\ &= (1+2x+2^2x^2+2^3x^3+...)-(1+x+x^2+x^3+...)\\ &= (2-1)x+(2^2-1)x^2+(2^3-1)x^3+...\\ &= \sum_{k=1}^{\infty}(2^k-1)x^k \end{align*}\) 现在通过生成函数的方式我们得到了 $h(k) = 2^k-1$

偶数个5

求 $n$ 位十进制正整数中出现偶数个 $5$ 的数的个数,不能有前导零。

设 $a_n$ 表示 $n$ 位数有偶数个 $5$ 的方案数。$n$ 位数共有 $910^{n-1}$ 个 ,按照尾数进行分类,如果尾数不是 $5$ ,前 $n-1$ 位必须有偶数个 $5$,当前方案数 $a_n = 9a_{n-1} $,若尾数是 $5$ ,前 $n-1$ 位必须有奇数个 $5$ ,当前方案数 $a_n = 910^{n-2}-a_{n-1}$,所以 $a_n = 9*10^{n-2}+8a_{n-1} \quad (a_1 = 8)$ ,构造生成函数 \(\begin{align*} G(x) &= a_1x+a_2x^2+a_3x^3+... \\ -8xG(x)&= -8a_1x^2-8a_2x^3-8a_3x^4-... \\ (1-8x)G(x) &= a_1x+(a_2-8a_1)x^2+(a_3-8a_2)x^3+... \\ &= a_1x+9*10^{2-2}x^2+9*10^{3-2}x^3+... \\ &= a_1x+9x^2(10^0+10^1x+10^2x^2+...) \\ &= 8x+\frac{9x^2}{1-10x} \\ G(x) &= \frac{x(8-71x)}{(1-8x)(1-10x)} \\ &= \frac{1}{2} (\frac{7x}{1-8x}+\frac{9x}{1-10x}) \\ &= \frac{1}{2} \sum_{k=1}^{\infty} (7\cdot 8^{k-1}+9\cdot 10^{k-1})x^k \end{align*}\) 至此我们算出了 \(a_n = \frac{7}{2}\cdot 8^{n-1} + \frac{9}{2}\cdot 10^{n-1}\)

Fibonacci数列

见链接

线性常系数齐次递推关系

线性累加和为0,同时有一些常系数的递推关系式称为线性常系数齐次递推关系

表示形式为 $a_n+c_1a_{n-1}+…+c_ka_{n-k}=0$ ,

初始值 $a_0 = d_0,a_1=d_1,…,a_{k-1}=d_{k-1}$

$c_i,d_i$ 是常数且 $c_k \neq 0$ ,则称上式为 ${a_n}$ 的 $k$ 阶线性常系数齐次递推关系

特征多项式

我们通过下面的推导来寻找一种求解上述形式的递推式的通项公式的简单方法。

首先有递推式 \(a_n+C_1a_{n-1}+...+C_ka_{n-k}=0 \quad (1)\) 设序列 ${ a_n}$ 的母函数 \(G(x) = a_0+a_1x+...+a_nx^n+... \quad (2)\) 根据递推式 $(1)$ 有如下等式成立 \(\begin{array}{l}{x^{k}\left(a_{k}+C_{1} a_{k-1}+C_{2} a_{k-2}+\cdots+C_{k} a_{0}\right)=0} \\ {x^{k+1}\left(a_{k+1}+C_{1} a_{k}+C_{2} a_{k-1}+\cdots+C_{k} a_{1}\right)=0} \\ {\cdots \cdots} \\ {x^{n}\left(a_{n}+C_{1} a_{n-1}+C_{2} a_{n-2}+\cdots+C_{k} a_{n-k}\right)=0} \\ {\ldots \ldots}\end{array}\) 将这些式子两边分别相加(竖着看将每一列相加)得到 \(\begin{aligned} \left(G(x)-\sum_{i=0}^{k-1} a_{i} x^{i}\right) + C_{1} x\left(G(x)-\sum_{i=0}^{k-2} a_{i} x^{i}\right) +\cdots+C_{k} x^{k} G(x)=0 \end{aligned}\) 可以把 $G(x)$ 提取出来 \(\left(1+C_{1} x+C_{2} x^{2}+\cdots+C_{k} x^{k}\right) G(x)=\sum_{j=0}^{k-1} C_{j} x^{j} \sum_{i=0}^{k-1-j} a_{i} x^{i} = P(x)\) 则 $$ \begin{align*} G(x) &= \frac{P(x)}{\left(1+C_{1} x+C_{2} x^{2}+\cdots+C_{k} x^{k}\right)}
&= \frac{P(x)}{x^k(m^k+C_1m^{k-1}+C_2m^{k-2}+…+C_k)} \quad(m = x^{-1})
&= \frac{P(x)}{x^k(m-a_1)^{k_1}(m-a_2)^{k_2}…(m-a_i)^{k_i}} \quad (k_1+k_2+…+k_i=k)
&= \frac{P(x)}{x^kC(m)}
&= \frac{P(x)}{(1-a_1x)^{k_1}(1-a_2x)^{k_2}…(1-a_i)^{k_i}} \

\end{align} \(可以看到最初的递推关系式和推出的 $C(m)$ 的系数一一对应\) \begin{align} 0 &= a_n+C_1a_{n-1}+…+C_ka_{n-k}
C(m) &= m^k+C_1m^{k-1}+C_2m^{k-2}+…+C_k
\end{align*} \(这样在计算式就可以通过起初的表达式的系数快速得到生成函数。即如果知道递推关系\) a_{n}+C_{1} a_{n-1}+C_{2} a_{n-2}+\ldots C_{k} a_{n-k}=0 \(可以快速的得到 $C(x)$ ,这里把它称作**特征多项式**\) C(x)=x^{k}+C_{1} x^{k-1}+\ldots+C_{k-1} x+C_{k} $$ 例如

  • Fibonacci递推式 $F_n-F_{n-1}-F_{n-2}=0$ ,它的特征多项式就是 $x^2 - x - 1 = 0$
  • Hanoi递推式 $h(n)-3h(n-1)+2h(n-2)=0$ ,它的特征多项式就是 $x^2-3x+2=0$

母函数与特征多项式

无重根的特征多项式

有了特征多项式,可以比较容易的把多项式化成 $\frac{P(x)}{(1-a_1)^{k_1}…(1-a_ix)^{k_i}}$ 的形式。

若特征多项式 $C(x)$ 无重根 ($k_i = 1$),可以分解为 \(C(x)=\left(x-\alpha_{1}\right)\left(x-\alpha_{2}\right) \ldots\left(x-\alpha_{k}\right)\) 特征多项式可以表示为 \(\begin{align*} G(x)&=\frac{P(x)}{x^kC(m)}=\frac{P(x)}{C(x)} \\ &=\frac{P(x)}{\left(1-\alpha_{1} x\right)\left(1-\alpha_{2} x\right) \ldots\left(1-\alpha_{k} x\right)} \\ &=\frac{A_{1}}{1-\alpha_{1} x}+\frac{A_{2}}{1-\alpha_{2} x}+\ldots+ \frac{A_{k}}{1-\alpha_{k} x} \\ &=\sum_{i=1}^{k}A_i(1+\alpha_ix+\alpha_i^2x^2+...) \end{align*}\)

我们只关注 $x^n$ 的系数 $a_n$ ,则 \(a_n = \sum_{i=1}^{k}A_ia_i^n\) 现在我们只需要求的待定系数 $A_i$ 即可,将 $n=0,1,2,…$ 带入上式可得线性方程组 \(\left\{\begin{array}{c}{A_{1}+A_{2}+\cdots+A_{k}=d_{0}} \\ {A_{1} \alpha_{1}+A_{2} \alpha_{2}+\cdots+A_{k} \alpha_{k}=d_{1}} \\ {\ldots \ldots} \\ {A_{1} \alpha_{1}^{k-1}+A_{2} \alpha_{2}^{k-1}+\cdots+A_{k} \alpha_{k}^{k-1}=d_{k-1}}\end{array}\right.\) 其中 $d_i$ 是 $a_n$ 的初始值。

有重根的特征多项式

Hint: 上述推导是基于特征多项式无重根的情况,有重根的情况见下方推导。

设特征多项式 $C(x)$ 有重根,设 $\beta$ 是 $C(x)$ 的 $k$ 重根,则 $G(x) = \sum_{j=1}^{k} \frac{A_{j}}{(1-\beta x)^{j}} $

现在依然要求待定系数 $A_j$ ,根据二项式定理 $(1+x)^{\alpha}=\sum_{n=0}^{\infty} \frac{\alpha(\alpha-1) \ldots(\alpha-n+1)}{n !} x^{n} \quad \alpha \in R$

可以发现 $G(x)$ 中 $x^n$ 的系数 \(a_{n}=\sum_{j=1}^{k} A_{j}C_{j+n-1}^{n} \beta^{n} = \sum_{j=1}^{k} A_{j}C_{j+n-1}^{j-1} \beta^{n}\) 是 $n$ 的 $j-1$ 次多项式。因此,$a_n$ 是 $\beta$ 与 $n$ 的 $k-1$ 次多项式的乘积。则递推关系的解对应于的项为 \(\left(A_{0}+A_{1} n+\cdots+A_{k-1} n^{k-1}\right) \beta^{n}\) 其中 $A_i$ 为待定系数

所以就可以直接写出通项公式 \(a_n = \left(A_{0}+A_{1} n+\cdots+A_{k-1} n^{k-1}\right) \beta^{n}\) 然后依然带入 $n=0,1,…$ 求出待定系数。

复数根的特征多项式

设两个复数根为 \(\begin{array}{l}{\alpha_{1}=\rho(\cos \theta+i \sin \theta)} \\ {\alpha_{2}=\bar{\alpha}_{1}=\rho(\cos \theta-i \sin \theta)}\end{array}\) 依然可以把它看作是无重根的形式,依然让 $a_n = A_1\alpha_1^n+A_2\alpha_2^n$
\(\begin{aligned} & A_{1} \alpha_{1}^{\mathrm{n}}+A_{2} \alpha_{2}^{\mathrm{n}} \\=&\left(A_{1}+A_{2}\right) \rho^{\mathrm{n}} \cos n \theta+ i\left(A_{1}-A_{2}\right) \rho^{\mathrm{n}} \sin n \theta \\=& A \rho^{\mathrm{n}} \cos n \theta+B \rho^{\mathrm{n}} \sin n \theta \end{aligned}\) 这样表示更方便求解。

特征多项式求斐波那契通项式

首先有 $F_n -F_{n-1}-F_{n-2} = 0$

有特征多项式 $x^2 - x - 1 = 0$ ,有特征根 $\alpha = \frac{1+\sqrt{5}}{2},\beta = \frac{1-\sqrt{5}}{2}$

可以直接写出 $F_n = A_1\alpha^n+A_2\beta^n$ ,现在需要求待定系数 $A_1,A_2 $

直接把 $n=0,1$ 带入得到 $A=\frac{1}{\sqrt{5}},B=-\frac{1}{\sqrt{5}}$

就有了通项公式 \(F(n) = \frac{1}{\sqrt{5}}\left( (\frac{1+\sqrt{5}}{2})^n+(\frac{1-\sqrt{5}}{2})^n\right)\) 可以对比链接中的求法,现在的步骤简洁了许多。

总结

再总结一下,利用特征多项式求线性常系数齐次递推通向公式主要有以下步骤:

  1. 得到线性递推关系,化成线性常系数齐次递推形式
  2. 找到对应的特征方程并求出特征解,其中特征解有三种不同形式,形式不同得到的通向公式也略有不同
  3. 带入前几项算出待定系数

卡特兰数(Catalan number)

链接中有将卡特兰数转化为格路问题的方案数,采用组合数的方法可以直接得到一个化简结果。这里采用母函数方法求一下,设第 $n$ 个卡特兰数为 $C_n$ ,有母函数 \(\begin{align*} c(x) &=\sum_{n=0}^{\infty} C_{n} x^{n} \\ c(x)^{2}&=C_{0} C_{0+}\left(C_{1} C_{0}+C_{0} C_{1}\right) x+\left(C_{2} C_{0}+C_{1} C_{1}+C_{0} C_{2}\right) x^{2}+\ldots \ldots \end{align*}\) 卡特兰数的前几项 \(\begin{aligned} C_{1} &=C_{0} C_{0} \\ C_{2} &=C_{1} C_{0}+C_{0} C_{1} \\ C_{3} &=C_{2} C_{0}+C_{1} C_{1}+C_{0} C_{2} \\ C_{4} &=C_{3} C_{0}+C_{2} C_{1}+C_{1} C_{2}+C_{0} C_{3} \\ \cdots & \cdots \end{aligned}\) 所以 \(\begin{align*} c(x)^{2}&=C_{1}+C_{2} x+C_{3} x^{2}+\ldots \ldots \\ c(x)&=C_{0}+C_{1} x+C_{2} x^{2}+\ldots \ldots \quad \quad (C_0=1)\\ c(x)&=1+x c(x)^{2} \end{align*}\) 上述表达式可以求出两个解,还要满足 \(\lim _{x \rightarrow 0^{+}} c(x)=C_{0}=1\) 所以从两根中取一个 \(c(x)=\frac{1-\sqrt{1-4 x}}{2 x} = \frac{1-(1-4x)^{\frac{1}{2}}}{2x}\) 通过二项式定理 $(1+x)^{\alpha}=\sum_{n=0}^{\infty} \frac{\alpha(\alpha-1) \ldots(\alpha-n+1)}{n !} x^{n} \quad \alpha \in R$ 展开得到 \(\begin{array}{c}{c(x)=\sum_{n=0}^{\infty}\left(\begin{array}{c}{2 n} \\ {n}\end{array}\right) \frac{x^{n}}{n+1}} \\ {C_{n}=\frac{1}{n+1}\left(\begin{array}{c}{2 n} \\ {n}\end{array}\right)}\end{array}\)

指数型母函数

\[G(x) = a_{0}+a_{1} x+a_{2} x^{2}+\cdots\]

是 $a_0,a_1,…$ 序列的母函数. \(\begin{aligned} (1+x)^\alpha &= (1+x)(1+x)...(1+x) \\ &= 1+n x+\frac{n(n-1)}{2} x^{2}+\cdots +\frac{n(n-1) \cdots(n-k+1)}{k !} x^{k}+\cdots \end{aligned}\) 而母函数的系数也就刚好对应于组合数,所以母函数是来解决组合问题的。若想将其转换成能够表示排列问题的形式,相当于把 $\alpha $ 个盒子标上序号 \(\begin{aligned}(1+x)^{n} &=\sum_{k=0}^{\infty} C(n, k) x^{k} \\ &=\sum_{k=0}^{\infty} \frac{C(n, k) k !}{k !} x^{k} \\ &=\sum_{k=0}^{\infty} P(n, k) \frac{x^{k}}{k !} \end{aligned}\) 所以若要计算排列问题,只需把组合问题对应的系数乘以 $k!$ 即可,这时把这种类型的母函数叫做指数型母函数 \(\begin{aligned} G_{e}(x)=& a_{0}+\frac{a_{1}}{1 !} x+\frac{a_{2}}{2 !} x^{2}+\frac{a_{3}}{3 !} x^{3} +\cdots+\frac{a_{k}}{k !} x^{k}+\cdots \end{aligned}\) 而且有 \(\begin{aligned} e^{x} &=\sum_{n=0}^{\infty} \frac{x^{n}}{n !} \\ &=1+x+\frac{x^{2}}{2 !}+\cdots+\frac{x^{n}}{n !} \cdots \end{aligned}\) 所以用指数型母函数求解问题的时候就可以借助 $e^x$

例题

一个五位数由 1,2,3,4四个数字构成,问满足下列条件的情况由多少种

1出现次数不超过2次,但不能不出现;

2出现次数不超过1次;

3出现次数可达3次,也可以不出现;

4出现次数为偶数。

有母函数 $$ \begin{aligned} G_{e}(x) &=\left(\frac{x}{1 !}+\frac{x^{2}}{2 !}\right)\left(1+\frac{x}{1 !}+\frac{x^{2}}{2 !}+\frac{x^{3}}{3 !}\right)\left(1+\frac{x^{2}}{2 !}+\frac{x^{4}}{4 !}\right) \

&=\left(x+\frac{3}{2} x^{2}+\frac{1}{2} x^{3}\right)\left(1+x+x^{2}+\frac{2}{3} x^{3}+\frac{7}{24} x^{4}+\frac{1}{8} x^{5}+\frac{x^{6}}{48}+\frac{x^{7}}{144}\right)\

&= x+\frac{5}{2} x^{2}+3 x^{3}+\frac{8}{3} x^{4}+\frac{43}{24} x^{5}+\frac{43}{48^{6}} x^{6}+\frac{17}{48} x^{7}+\frac{1}{288}x^8+\frac{1}{48}x^9+\frac{1}{288} x^{10} \

&=\frac{x}{1 !}+5 \frac{x^{2}}{2 !}+18 \frac{x^{3}}{3 !}+64 \frac{x^{4}}{4 !}+215 \frac{x^{5}}{5 !}+645 \frac{x^{6}}{6 !}+1785 \frac{x^{7}}{7 !} +140 \frac{x^{8}}{8 !}+7650 \frac{x^{9}}{9 !}+12600 \frac{x^{10}}{10 !} \end{aligned} $$ 所以最后的答案应该就是 215

错排问题

第一类斯特林数

n 个人跳舞,分成m个圈的方案数。记作 $s(n,m)$

易知 $s(n,0) = 0, s(n,1) = 1$

对于第 n+1 个人,存在以下两种情况

  1. 第n+1个人可以单独自己跳舞,其他n个人构成m-1个圈。
  2. 第n+1个人加入到别的队伍中,可以选择第i个的左边,所以有n个不同的位置,而其他n个人有s(n,m)种不同的组圈方法

所以第一类斯特林数的递推式为 \(s(n+1,n) = s(n,m-1)+ns(n,m)\)

第二类斯特林数

n 个球分成 m 组,组内无顺序区别,求总方案数。

相当于 n 个有区别的球放入 m 个无区别的盒子中且盒子不为空的总方案数。 有 $s(n,0) = 0, s(n,1)=s(n,n)=1,s(n,2)=2^{n-1}-1$

当前放的球a,面临以下两种情况

  1. a独占一个盒子,方案数 $s(n-1,m-1)$
  2. a放入有球的 m 个盒子中,方案数 $ms(n-1,m)$

因此 \(s(n,m) = ms(n-1,m)+s(n-1,m-1)\)

利用母函数求解通项表达式

  • $n$ 个有区别的球放到 $m$ 个相同的盒子中,要求无一空盒,其不同的方案数:$s(n,m)$
  • $n$ 个有标志的球放进 $m$ 个有区别的盒子,无空盒,其方案数是 $m!s(n,m)$ ,相当于 $m$ 个有标志的元素取 $n$ 个做允许重复的排列

第二种情况,有以下母函数 \(\begin{aligned} G_{e}(x)&=\left(x+\frac{x^{2}}{2 !}+\frac{x^{3}}{3 !}+\ldots\right)^m\\ &=\left(e^{x}-1\right)^{m} \\ &=\sum_{h=1}^{m} C(m, h)(-1)^{h} e^{(m-h) x} \\ \because e^{(m-h) x}&=1+\frac{m-h}{1 !} x+\frac{(m-h)^{2}}{2 !} x^{2}+\frac{(m-h)^{3}}{3 !} x^{3}+\ldots=\sum_{n=0}^{\infty} \frac{(m-h)^{n}}{n !} x^{n} {n !} \\ \therefore \quad G_{e}(x)&=\sum_{k=1}^{m} C(m, h)(-1)^{n} \sum_{n=0}^{\infty} \frac{(m-h)^{n}}{n !} x^{n}=\sum_{n=0}^{\infty} \frac{x^{n}}{n !} \sum_{n=1}^{m} C(m, h)(-1)^{n}(m-h)^{n} \\ m ! S(n, m)&=\sum_{n=1}^{m} C(m, h)(-1)^{n}(m-h)^{n}\\ \end{aligned}\) 因此可以得到通项式: \(S(n, m)=\frac{1}{m!}\sum_{n=1}^{m} C(m, h)(-1)^{n}(m-h)^{n}\)

容斥原理

  • 概念:交、并、补集
  • 两个式子:交集的补集 和 补集的并集,并集的补集 和 补集的交集 的互相转换。
  1. 500 以内能被 3 或 5 整除的数的个数
  2. a,b,c,d,e,f 排列形成的长度为 6 字符串中不含 ace 或 ef 的排列个数
  3. a,b,c,d 组成的长为 n 的字符串中a,b,c 都至少出现一次的字符串个数
  4. 120以内的素数个数。不超过120的合数一定是2、3、5、7的倍数。
  5. 欧拉函数 $\varphi(n)$
  6. 有约束的多元方程的非负整数解的个数问题
  7. 有障碍的格路问题
  8. 第二类斯特林数转化为放球模型后可以用容斥原理解决
  9. 错排问题

鸽巢原理

  1. 30人的班级,至少 3 人的生日在同一个月
  2. 10双蓝袜子,12双白袜子,随机取几次就能凑成一双
  3. n+1 个不大于 2n 的正整数一定有两个数是互质的
  4. [1,2n] 取 n+1 个数,必会有一个数是另一个数的个数
  5. 中国剩余定理
  6. Ramsey数

群论

把数学运算归类,一个集合和一种运算是否能被称为群要看是否满足以下条件

  1. 封闭性:集合中的元素经过运算得到的结果依然在集合中
  2. 结合律:(ab)c = a(bc)
  3. 单位元:基本单位
  4. 逆元:数和它的逆元的运算结果是单位元

有以下概念:

  1. 有限群:有限个元素的群。元素个数被称为阶
  2. 无限群:无限个元素的群。
  3. 子群:从一个群中取出若干元素构成的群。
  4. 交换群(阿贝尔群):运算满足交换律。
  5. 置换群:任意群都可以用置换群表示。

有以下性质:

  1. 单位元是唯一的。
  2. 消去律成立。

置换群

  • 置换乘法:不满足交换律。在置换乘法下满足群的定义(封闭性、结合律、单位元、逆元),构成一个群。
  • 任意置换都可以表示成若干不相交循环的乘积。
  • 任意循环都可以写成任意对换的乘积

Burnside引理

Polya定理

母函数型Polya定理

图的计数:n个顶点的简单图有多少种不同的图形,相当于 n 个无标志顶点的二着色

# 使用单$作为行内数学公式分界符