组合数学（待完成）

• 计数原理：加法计数原理（分类），乘法计数原理（分步），减法计数原理，除法计数原理

• 排列组合：

与顺序有关的摆放或选择称 排列(Permutation)。

P(n,r)=\dfrac{P(n,n)}{P(n-r,n-r)}=\dfrac{n!}{(n-r)!}

规定P(n,r)=0\ \text{when}\ n<r

与顺序无关的摆放或选择称 组合(Combination)。

\begin{pmatrix}n\\r\end{pmatrix}=\dfrac{P(n,r)}{P(r,r)}=\dfrac{n!}{r!(n-r)!}

规定`$$\begin{pmatrix}n\r\end{pmatrix}=0\ \text{when}\ n）最大个数，应用容斥原理，将上界限制转化为下界限制，换元求解，即得到各元素都有无穷个时，元素分配个数均不超过各自最大个数的方法数，而这等于题意所求的方法数（无穷相对于最大个数多出的部分不会影响方法数）

• 生成函数：

  //TODO

  对偶问题：将r个相同的球放入k个不同盒子，其中第i个盒子容量为n_i，允许盒子为空的方法数

对应不定方程：

x_1+x_2+...+x_k=r\\其中0\le x_1\le n_1,0\le x_2\le n_2,...,0\le x_k\le n_k

求方程解的个数

PS：关于球的相同与不同，由于盒子放球可以一个一个放，因此对不同的球，将球序固定后放入盒子的顺序不同时，即便每个盒子分配到的球数相同，得到的方法也不同；而相同的球只要结果是每个盒子分配到相同的球数，放入盒子的顺序不同也是一样的方法。由于前者可以映射到元素放置的顺序，而后者可以映射到放置的顺序整体消序（即组合），故分别对应上了多重排列和多重组合。

矩阵填数：先选择填哪些空C_n^k，再对各数排序A_k^k

非攻击性车：先选行C_n^k，再选列A_n^k，最后做其他限制（如颜色）//TODO

• 不定方程的解个数（注意解(1,1,2)与(1,2,1)不同）

对于不定方程

x_1+x_2+...+x_k=r

1.约束为0\le x_1,0\le x_2,...,0\le x_k，即非负整数解，直接使用多重组合

2.约束为a_1\le x_1,a_2\le x_2,...,a_k\le x_k，即下界约束，换元为情况1。特别的，对于正整数解，有a_1=a_2=...=a_k=1（对应将r个相同的球放入k个不限大小的不同盒子中的方法数，不允许空盒）

这里可以看出，先取走特殊的元素，剩下的一般元素用一般的排列组合即可解决，例如这里可以先每个盒子都分配一个元素，剩下的就变成了多重组合

3.约束为0\le x_1\le n_1,0\le x_2\le n_2,...,0\le x_k\le n_k，即上界约束，使用容斥原理或生成函数

4.同时拥有上界约束和下界约束，先换元转为情况3，再解决

5.约束为x_1=mt_1,x_2=mt_2,...,x_k=mt_k;m,t_1,t_2,...t_k\in N，使用生成函数解决

对于不定方程

t_1x_1+t_2x_2+...+t_kx_k=r\\t_1,t_2,...t_k\in N

换元，换为上种情况5，使用生成函数。

• 排列生成

递归生成算法
邻位对换算法
从逆序生成排列算法（最大数开始，最小数开始）

逆序，逆序数，逆序列，逆序个数

• 组合生成

字典序生成算法
反射Gray码序生成算法（递归法，逐次法）

Gray码序与字典码序的转换

基于字典序的r-组合生成算法


• 二项式定理：

(a+b)^n=\sum_{i=0}^{n}\begin{pmatrix}n\\i\end{pmatrix}a^ib^{n-i}

杨辉三角组合意义：

1.某数为左上正上之和

2.某数为从(0,0)到该数位置的路径数，允许的移动方向规定为向下和向右下

（最好参考ppt理解）

延伸公式：

1.

\sum_{i=0}^{n}\begin{pmatrix}n\\i\end{pmatrix}p^i=(p+1)^n

2.

\sum_{i=0}^{n}(-1)^{n-i}\begin{pmatrix}n\\i\end{pmatrix}p^i=(p-1)^n

二项式系数性质：1.单峰，最大值可能有一个（n为奇数）或两个（n为偶数），单峰点为n/2或其两侧的整数

链，反链，最大链：定义参照ppt。

对于n元素集合，最大链有n!个，其元素个数为n+1，构造方法为逐一填入（详见ppt）；反链最多元素个数为\begin{pmatrix}n\\n/2\end{pmatrix}（整数除法），最大反链为包含所有该集合的n/2元素子集的集类（因此最大反链有一个或两个，与n奇偶有关）

多项式定理：

(a_1+a_2+...a_k)^n=\sum_{n_1+n_2+...+n_k=n}\begin{pmatrix}n\\n_1n_2...n_k\end{pmatrix}a_1^{n_1}a_2^{n_2}...a_k^{n_k}

多项式系数\begin{pmatrix}n\\n_1n_2...n_k\end{pmatrix}=\dfrac{n!}{n_1!n_2!...n_k!}，即有限多重全排列数

帕斯卡公式：

\begin{pmatrix}n\\n_1n_2...n_k\end{pmatrix}=\begin{pmatrix}n\\n_1-1\ n_2...n_k\end{pmatrix}+\begin{pmatrix}n\\n_1n_2-1\ ...n_k\end{pmatrix}+...+\begin{pmatrix}n\\n_1n_2...n_k-1\end{pmatrix}

牛顿二项式定理：

(a+b)^\alpha=\sum_{i=0}^{\infin}\begin{pmatrix}\alpha\\i\end{pmatrix}a^ib^{\alpha-i},0\le |a|<|b|

此时二项式系数被扩展，允许出现实数，有

\begin{pmatrix}\alpha\\r\end{pmatrix}=\begin{cases}\dfrac{\alpha(\alpha-1)...(\alpha-r+1)}{r!},r\ge1\\1,r=0\\0,r\le-1\end{cases},\alpha\in \R,r\in \Z

等价形式：

1.

(1+z)^\alpha=\sum_{i=0}^{\infin}\begin{pmatrix}\alpha\\i\end{pmatrix}z^i,|z|<1

2.

(1+z)^{-n}=\sum_{i=0}^{\infin}(-1)^i\begin{pmatrix}n+i-1\\i\end{pmatrix}z^i,|z|<1
\\(1-z)^{-n}=\sum_{i=0}^{\infin}\begin{pmatrix}n+i-1\\i\end{pmatrix}z^i,|z|<1

（生成函数有用）

• 矩形寻路问题：对两个方向的运动进行多重排列计数
• 容斥原理：对于集合B和集合B的一个覆盖\{A_i\}，有

|\bigcap_{i\in C} \bar A_i|=|B|-|\bigcup_{i\in C} A_i|=|B|-\sum_{i\in C}|A_i|+\sum_{i,j\in C}|A_i\cap A_j|-...+(-1)^{|C|}|\bigcap_{i\in C} A_i|

注意这里就是为了摆脱你对重复计数数不清的烦恼，在计数等号右边时，只需考虑并集的情况，无需考虑其他的影响；也注意一定要记完整，不能因为有几项相等而擅自等价为一项而遗漏。

顺便一提，等号右边的sum个数依次为|C|,\begin{pmatrix}|C|\\2\end{pmatrix},...,\begin{pmatrix}|C|\\|C|\end{pmatrix}，可以提示计数与简化计数

错位排列：对1,2,...,n，其排列i_1,i_2,...,i_n满足i_1\neq1,i_2\neq2,...,i_n\neq n时，为一个错位排列，其个数为D_n。用容斥原理求解，即反过来求解有若干个元素在其自然位置上，其他元素任意排（没有限制）的方法数。

D_n=n!(1-\dfrac{1}{1!}+\dfrac{1}{2!}-...+(-1)^n\dfrac{1}{n!}),n\ge1

递推公式：D_n=(n-1)(D_{n-1}+D_{n-2}),D_n=nD_{n-1}+(-1)^n,D_2=1,D_1=0

绝对禁止位置排列：对错位排列的推广，原理相同，注意一般描述为位置禁止哪些元素，可以反过来理解为元素禁止在哪些位置，具体看需要是转换成就让禁止元素进入这些位置来求解还是就让这些位置进入这些禁止元素求解。

带禁止位置的非攻击性车：//TODO

相对禁止位置排列：带捆绑法的绝对禁止位置排列。相对原来的位置有何限制意味着原来是自然位置

• 若干泰勒展开：

1+x+x^2+x^3+...=\dfrac{1}{1-x},|x|<1

1-x+x^2-x^3+...=\dfrac{1}{1+x},|x|<1

1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+...=\text e^x

1+2x+4\dfrac{x^2}{2!}+8\dfrac{x^3}{3!}+...=\text e^{2x}

1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+...=\dfrac{1}{2}(\text e^{x}-\text e^{-x})

1+x^2+\dfrac{x^4}{2!}+\dfrac{x^6}{3!}+...=\text e^{x^2}

注意\dfrac{1}{1-x^n}与\dfrac{1}{(1-x)^n}的区别

• 生成函数：对数列\{h_n\}，其生成函数为g(x)=\sum_{n=0}^{\infin}h_nx^n。有穷数列可以通过补0得到无穷数列

多重组合数（h_n为方程x_1+x_2+...+x_k=n解的个数）的生成函数

g(x)=\sum_{n=0}^{\infin}\begin{pmatrix}n+k-1\\k\end{pmatrix}x^n=\dfrac{1}{(1-x)^k}\\=(1+x+x^2+...)^k=(\sum_{e_1=0}^{\infin}x^{e_1})(\sum_{e_2=0}^{\infin}x^{e_2})...(\sum_{e_k=0}^{\infin}x^{e_k})\\=\sum_{e_1+e_2+...+e_k=n=0}^{\infin}x^{e_1}x^{e_2}...x^{e_k}

注意

\sum_{e_1+e_2+...+e_k=n=0}^{\infin}x^{e_1}x^{e_2}...x^{e_k}\neq \sum_{n=0}^{\infin}x^n

根据约束对各个(1+x+x^2+...)内的单项式进行去除，然后再合并展开，得到目标公式

例如(x+x^2+x^3)代表该变量约束为1\le x_i \le 3，(x+x^3+x^5+...)表述约束为该变量只能取偶数，等等

• 指数生成函数：对数列\{h_n\}，其生成函数为g^{(e)}(x)=\sum_{n=0}^{\infin}\dfrac{h_n}{n!}x^n

多重排列数（h_n为k阶（定义参开头）无限多重n排列）的指数生成函数

g^{(e)}(x)=\sum_{n=0}^{\infin}\dfrac{k^n}{n!}x^n=\text e^{kx}\\=(1+\dfrac{x}{1!}+\dfrac{x^2}{2!}+...)^k=(\sum_{e_1=0}^{\infin}\dfrac{x^{e_1}}{e_1!})(\sum_{e_1=0}^{\infin}\dfrac{x^{e_2}}{e_2!})...(\sum_{e_1=0}^{\infin}\dfrac{x^{e_k}}{e_k!})\\=\sum_{e_1+e_2+...+e_k=n=0}^{\infin}\dfrac{1}{e_1!e_2!...e_k!}x^{e_1}x^{e_2}...x^{e_k}

多重排列数（h_n为k阶（定义参开头）有限多重全排列，第i种元素有n_i个）的指数生成函数（注意各个n_i固定！）

g^{(e)}(x)=f_{n_1}(x)f_{n_2}(x)...f_{n_k}(x)=\sum_{0\le m_1\le n_1,0\le m_2\le n_2,...,0\le m_k\le n_k,m_1+m_2+...+m_k=n=0}^{\infin}\dfrac{1}{m_1!m_2!...m_k!}x^{m_1}x^{m_2}...x^{m_k}

其中

f_{n_i}(x)=(1+\dfrac{x}{1!}+\dfrac{x^2}{2!}+...+\dfrac{x^{n_i}}{n_i!})\\

带约束时，同样对各子式进行限制，合并展开即可，注意最终要凑出n!分母，使分子直接为所求

注意：

\sum_{e_1+e_2+...+e_k=n=0}^{\infin}\dfrac{1}{e_1!e_2!...e_k!}x^{e_1}x^{e_2}...x^{e_k}\neq\sum_{0\le m_1\le n_1,0\le m_2\le n_2,...,0\le m_k\le n_k,m_1+m_2+...+m_k=n=0}^{\infin}\dfrac{1}{m_1!m_2!...m_k!}x^{m_1}x^{m_2}...x^{m_k}

• 递推：1.确定其中一个，降阶；2.由阶小的补充，升阶

等差，等比，差比（前n项和可用错位相减，裂项相消，通项公式待定系数求解）

斐波那契数列：1.递推公式：f_n=f_{n-1}+f_{n-2},f_0=0,f_1=1

2.前n项和S_n=f_{n+2}-1

3.斐波那契数是偶数当且仅当n被3整除
斐波那契数能被3整除当且仅当n可被4整除
斐波那契数能被4整除当且仅当n可被6整除

4.

f_n=\begin{pmatrix}n-1\\0\end{pmatrix}+\begin{pmatrix}n-2\\1\end{pmatrix}+...+\begin{pmatrix}n-k\\k-1\end{pmatrix},k=[(n+1)/2](\text{down})

• k阶常系数线性齐次递推关系

h_n=a_1h_{n-1}+a_2h_{n-2}+...+a_kh_{n-k},a_k\neq0

求解方法：

1.特征方程法

特征方程为

x^n-a_1x^{n-1}-a_2x^{n-2}-...-a_kx^{n-k}=0

设有k个不同的根q_1,q_2,...,q_k，则h_n解为

h_n=c_1q_1^n+c_2q_2^n+...+c_kq_k^n

给定初值h_0,h_1,h_2,...,h_{k-1}来确定c_1,c_2,..,c_k

若有t组重根，其中第i组重数为s_i，则设

H_n^{(i)}=c_1q_i^n+c_2nq_i^n+...+c_nn^{s_i-1}q_i^n

则解为

h_n=H_n^{(1)}+H_n^{(2)}+...+H_n^{(t)}

2.生成函数法

利用递推公式配凑：

g(x)=h_0+h_1x+h_2x^2+...

则有

-a_1xg(x)=-(a_1h_0x+a_1h_1x^2+a_1h_2x^3+...)\\
-a_2x^2g(x)=-(a_2h_0x^2+a_2h_1x^3+a_2h_2x^4+...)\\
...\\
-a_kx^kg(x)=-(a_kh_0x^k+a_kh_1x^{(k+1)}+a_kh_2x^{(k+2)}+...)

得

(1-a_1x-a_2x^2-...-a_kx^k)g(x)=h_0+(h_1-a_1h_0)x+(h_2-a_1h_1-a_2h_0)x^2+...+(h_n-a_1h_{n-1}-a_2h_{n-2}-...-a_kh_{n-k})x^n+...

可以利用h_n-a_1h_{n-1}-a_2h_{n-2}-...-a_kh_{n-k}=0消去n及之后的项。

得到g(x)=\dfrac{p(x)}{q(x)}的形式后，用部分分式法，分解为多个\dfrac{c}{(1-rx)^n}的乘积，再将其用牛顿二项式定理展开

• k阶常系数线性非齐次递推关系

h_n=a_1h_{n-1}+a_2h_{n-2}+...+a_kh_{n-k}+b_n,a_k\neq0

类似于微分方程，通解f_n的得到通过求解对应的齐次递推关系，而若能得到一个特解c_n，则解为h_n=kf_n+c_n,k\in Z


特解：1.b_n是n的k次多项式，则h_n也是

2.b_n是指数函数r^n，若r不是特征根（0重根），则h_n=cr^n；若r是k重特征根，则h_n=r^n\sum_{i=0}^kc_in^i

3.b_n=p_nr^n，r是k重特征根，p_n是n的p次多项式，则h_n=r^n\sum_{i=0}^pc_in^{m+i}

• Catalan数

递推公式：

C_n=C_0C_{n-1}+C_1C_{n-2}+...+C_{n-1}C_0;C_0=1

C_n=\dfrac{4n-2}{n+1}C_{n-1}

通项公式：

C_n=\dfrac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}

推导：

g(x)=C_0+C_1x+C_2x^2+...\\
(g(x))^2=C_0^2+(C_0C_1+C_1C_0)x+(C_0C_2+C_1C_1+C_2C_0)x^2+...=C_1+C_2x+C_3x^2+...

故

g(x)-C_0=x(g(x))^2

解得

g(x)=\dfrac{1\pm\sqrt{1-4C_0x}}{2x}=\dfrac{1\pm\sqrt{1-4x}}{2x}

由g(0)=C_0=1，故只能取g(x)=\dfrac{1-\sqrt{1-4x}}{2x}

展开

g(x)=\sum_{n=1}^{\infin}\dfrac{1}{n}\begin{pmatrix}2n-2\\n-1\end{pmatrix}x^{n-1}=\sum_{n=0}^{\infin}\dfrac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}x^n

因为

(1+x)^{\frac{1}{2}}=\sum_{n=0}^{\infin}\begin{pmatrix}1/2\\n\end{pmatrix}x^n=\begin{pmatrix}1/2\\0\end{pmatrix}+\begin{pmatrix}1/2\\1\end{pmatrix}x+\begin{pmatrix}1/2\\2\end{pmatrix}x^2+...\\
=1+\dfrac{\frac{1}{2}}{1!}x-\dfrac{\frac{1}{2}\frac{1}{2}}{2!}x^2+\dfrac{\frac{1}{2}\frac{1}{2}\frac{3}{2}}{3!}x^3+...\\
=1+\dfrac{1}{2}x+\sum_{n=2}^{\infin}(-1)^{n-1}\dfrac{(2n-1)!!}{n!2^n}x^n\\
=1+\dfrac{1}{2}x+\sum_{n=2}^{\infin}(-1)^{n-1}\dfrac{(2n-2)!}{n!(n-1)!2^{2n-1}}x^n\\
=1+\dfrac{1}{2}x+\sum_{n=2}^{\infin}\dfrac{(-1)^{n-1}}{n2^{2n-1}}\begin{pmatrix}2n-2\\n-1\end{pmatrix}x^n\\
=1+\sum_{n=1}^{\infin}\dfrac{(-1)^{n-1}}{n2^{2n-1}}\begin{pmatrix}2n-2\\n-1\end{pmatrix}x^n

其中，

\dfrac{(2n-1)!!}{n!2^n}=\dfrac{(2n-1)!!(2n-2)!!}{n!(n-1)!2^{n-1}2^n}=\dfrac{(2n-2)!}{n!(n-1)!2^{2n-1}}

所以

\sqrt{1-4x}=(1-4x)^{1/2}=1-\sum_{n=1}^{\infin}\dfrac{2}{n}\begin{pmatrix}2n-2\\n-1\end{pmatrix}x^n

Catalan数的递归关键在于如何分治，且先拿一般的h_n得到递推式，再根据递推式和初值确定与Catalan数的对应关系

定理：考虑由n个+1和n个-1构成的2n项序列a_1, a_2,…, a_{2n}，其部分和满足：a_1 + a_2 + ? + a_k \ge 0(k=1,2,…,2n) 的序列的个数等于第n个Catalan数

证明：减法原理，可接受与不可接受，一一映射（详见ppt），每一个不可接受的n个1，n个-1的序列都对应一个普通的n+1个1，n-1个-1的序列（这个证明思路可以推广使用）

拟Catalan数：

C_n^*=n!C_{n-1}

C_n^*=(4n-6)C_{n-1}^*;C_1^*=1

C_n^*=(n-1)!\begin{pmatrix}2n-2\\n-1\end{pmatrix}

• 两类Stirling数

第二类Stirling数：将n个不同的球放入k个相同的无限容量的盒子，每个盒子不允许为空的方法数(由鸽笼原理知n>=k，可令`$$S(n,k)=0,nk） |
| 不同 | 相同 | 不允许 | 有限制 | 先求盒子不同，再消序 |
| 相同 | 不同 | 允许 | 每盒最多1个 | \begin{pmatrix}n\\k\end{pmatrix} |
| 相同 | 不同 | 允许 | 无限制 | \begin{pmatrix}n+k-1\\n\end{pmatrix} |
| 相同 | 不同 | 允许 | 第i盒最多n_i个；其他限制 | 生成函数，容斥原理；生成函数，换元+容斥原理 |
| 相同 | 不同 | 不允许 | 每盒最多1个 | \begin{pmatrix}n\\k\end{pmatrix}（n>k） |
| 相同 | 不同 | 不允许 | 无限制 | 先每个盒子填一个，再将剩下的填入。\begin{pmatrix}n-k+k-1\\n-k\end{pmatrix}=\begin{pmatrix}n-1\\n-k\end{pmatrix}=\begin{pmatrix}n-1\\k-1\end{pmatrix} |
| 相同 | 不同 | 不允许 | 第i盒最多n_i个 | 生成函数，先分配+容斥原理 |
| 相同 | 相同 | 允许 | 无限制 | 分拆数\sum_{i=0}^{k}p_n^i |
| 相同 | 相同 | 不允许 | 无限制 | 分拆数p^k_n |

（不允许也算一种限制，下界限制，但是下界限制不仅限于不允许为空）

（对多重r-排列先分组再分配其实是先多重r-组合，然后就转化为了多重全排列，便于计算）

（待补充）

鸽笼原理：

鸽笼原理强化形式：

Ramsey定理：

群：

Polya计数