组合数学学习笔记

今天（2019.5.23）有幸能听到组合十段的陈通学长讲解组合数学知识。

$$\Huge\texttt{组}_{\texttt{合}^{\texttt{数}_\texttt{学}}}$$

part1:组合数

约定:

$$x^{\underline{k}}=[x]_{k}=\prod_{i=n-k+1}^{n}i$$ $$x^{\overline{k}}=[x]^{k}=\prod_{i=n}^{n+k-1}i$$ $$\binom{n}{k}=\frac{[n]_{k}}{k!}$$

则有：

$$\binom{-1}{k}=(-1)^k$$ $$\binom{-n}{k}=(-1)^k\binom{n+k-1}{k}$$

二项式定理：

$$(a+b)^n=\sum_{k\geq 0}\binom{n}{k}a^kb^{n-k}$$

则有：

$$(1+x)^k=\sum_{k\geq 0}\binom{n}{k}x^k$$ $$\frac{1}{1+x}=\sum_{k\geq 0}(-x)^k$$ $$\sum_{k\geq 0}\binom{n}{k}=2^n$$ $$\sum_{k\geq 0}(-1)^k\binom{n}{k}=0$$ $$\sum_{k\geq 0}\binom{n}{2k}=2^{n-1}$$ $$\sum_{k\geq 0}\binom{n}{3k}=?$$

将$x=w_3^0,w_3^1,w_3^2$带入$(1+x)^k$可以计算

（课后练习1:解决一类$\sum\binom{n}{ak}$的问题）

fandemengde行列式：

$$(1+x)^{n_1}*(1+x)^{n_2}=\sum_{k\geq 0}\sum_{i\geq 0}\binom{n_1}{i}\binom{n_2}{k-i}x^k$$ $$=(1+x)^{n_1+n_2}=\sum_{k\geq 0}\binom{n_1+n_2}{k}x^k$$

Lucas定理：

$$\binom{n}{m}\equiv \binom{n \mod{p}}{m\mod{p}}\cdot\binom{n/p}{m/p}\mod{p}$$

证明：

$$n=s*p+r$$ $$(1+x)^n=[(1+x)^p]^s*(1+x)^r$$ $$=(1+\binom{p}{1}x+\binom{p}{2}x^2+...+\binom{p}{p}x^p)^s*(1+x)^r$$ $$\equiv(1+x^p)^s\cdot(1+x)^r\mod{p}$$

之后再二项式转回去就ok了。

杨辉三角性质：

$$\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$$ $$\sum_{i=m}^{n}\binom{i}{k}=\binom{n+1}{m+1}-\binom{m}{k+1}$$ $$\sum_{k=0}^{n}k\binom{n}{k}=\sum_{k=1}^{n}n\binom{n-1}{k-1}=n\sum_{k=0}^{n-1}\binom{n-1}{k}=n2^n$$ $$\sum_{k=0}^{n}k^2\binom{n}{k}= \sum_{k=0}^{n}k^{\underline{2}}\binom{n}{k}+\sum_{k=0}^{n}k\binom{n}{k}=n(n-1)2^{n-1}+n2^n$$

e.g.

若$f(x)$为次数小于n的多项式，则有:$\sum_{k=0}^{n}(-1)^kf(k)\binom{n}{k}=0$

考虑将普通多项式转化成下降幂多项式来证明(课后练习2)。

$Stirling$公式：

$$n! \approx \sqrt{2\pi n}(\frac{n}{e})^n$$

性质：$\binom{n}{n/2}\approx\frac{2^n}{\sqrt{n}}$

part2:生成函数

生成函数是数列的另一种表达方式（形式幂级数）

{$a_n$}的普通生成函数为$\sum_{n\geq 0}a_nx_n$

e.g.

组合数对应的生成函数：$(1+x)^n=\sum_{k \geq 0}\binom{n}{k}x^k$

阶乘的倒数对应的生成函数：$e^x=\sum_{k\geq 0}\frac{x^k}{k!}$

生成函数求解递推：

e.g.0

求$Fibonacci$的通项公式：

令$F(x)=\sum_{k\geq 0}f_kx^k$

则有$F(x)=1+x+x^2F(x)+x(F(x)-1)$

$F(x)=\frac{1}{1-x-x^2}=\frac{A}{1-\alpha x}+\frac{B}{1-\beta x}=…$

后两项又是等比数列的生成函数，就可以得到通项公式了。

e.g.1

考虑每个元素为1,2的n元组，求和为3的倍数的n元组个数。

设$F(X),g(x),h(x)$为模3余数为0,1,2的生成函数:

$F(x)=1+xG(x)+xH(x)$

$G(x)=1+xF(x)+xH(x)$

$H(x)=1+xF(x)+xG(x)$

得：$F(x)=\frac{1-x}{1-x-x^2}=\sum_{k\geq 0}(-1)^k\frac{2}{3}+\sum_{k\geq 0}\frac{1}{3}2^k$

用生成函数求解通项公式的方法：用生成函数描述数列的递推公式，得到生成函数方程并求，然后将生成函数转回通项公式。

e.g.2

考虑每个元素为0,1,2的n元组，求有奇数个1，偶数个2的n元组个数。

$$f_n=\sum_{i+j+k=n}[2\nmid j][2\mid k]\binom{n}{j}\binom{n-i}{k}$$ $$\frac{f_n}{n!}=\sum_{i+j+k=n}[2\nmid j][2\mid k]\frac{n!}{i!j!k!}$$

所以$f_n$的指数生成函数可以用三个函数的卷积来表示。

$$F(x)=e^x\cdot \frac{e^x-e^{-x}}{2}\cdot \frac{e^x+e^{-x}}{2}=\frac{e^{3x}-e^{-x}}{4}$$

(后面两项就是阶乘奇数项与偶数项的生成函数)

$$F(x)=\sum_{k\geq 0}\frac{3^n-(-1)^n}{4n!}x^n$$

所以$f_n=\frac{3^n-(-1)^n}{4}$。

part3:catlan数

定义：括号序列方案数。

递推公式：

$$c_0=1,c_n=\sum_{i=0}^{n-1}c_ic_n-i-1$$

生成函数：

$$C(x)=\frac{1-\sqrt{1-4x}}{2x}$$

通项公式：

$$C(x)=\frac{(2n)!}{n!(n+1)!}$$

part4:Stirling数

这部分参见这一篇

part5:拆分数

将n个相同的小球放入k个相同的盒子(非空)的方案数称作拆分数，记作$p(n,k)$。

如果不限定盒子的个数，则定义拆分数为$p(n)$。

性质：

$p(n)<p(n+1)$

$p(n)-p(n-1)<p(n+1)-p(n)$

$p(2n,n)=p(n)$

Ferrers图

把n拆成若干个正整数之和，其中最大值恰为k的方案数为$p(n,k)$。

可以利用这一结论dp求$p(n,k)$

法1:

$$dp[n][k]\rightarrow dp[n+k][k],dp[n][k]\rightarrow dp[n][k+1]$$

法2:

$$dp[n][k]\rightarrow dp[n+1][k+1],dp[n][k]\rightarrow dp[n+k][k]$$

法3:

$A=${$1,2,…,s$}

$B=${$s+1,s+2,…n$}

$$p(n)=\sum_{i=0}^{n}P_a(i)\cdot P_b(n-i)$$

法4:

生成函数：$p(x)=\prod_{k\geq 1}\frac{1}{1-x^k}$

法5:

$p(x)=p(n-1)+p(n-2)-p(n-5)-p(n-7)$，其中项上减去的常数为广义的五边形数。

广义五边形数即为$(1-x)(1-x^2)(1-x^3)…$的系数。

即：$\sum_{k=0} (-1)^kx^{3k\pm{}1}$

拆分数大小估计

$$2^{\sqrt{n}-2}\leq p(n)\leq 2^{n-1}$$

估计复杂度用，在十二省联考 希望 中间有所应用（暴力部分的复杂度分析）