组合数学笔记

等填坑。

二项式定理

定理：

$$(a+b)^{n} = \sum_{i=0}^{n} C_{n}^{i} a^{i} b^{n-i}$$

当 $b=1$ 时：

$$(a+1)^n = \sum_{i=0}^{n} C_{n}^{i} a^{i}$$

二项式反演

定理：

$$f(i)=\sum_{j=i}^{n}(-1)^{j-i}C_{j}^{i} g(j)$$ $$g(i)=\sum^{n}_{j=i}C^{i}_{j} f(j)$$

证明：

$$\sum_{j=i}^{n} (-1)^{j-i} C_{j}^{i} g(j) = \sum_{j=i}^{n} (-1)^{j-i} C_{j}^{i} \sum^{n}_{k=j} C^{j}_{k} f(k) = \sum_{k=i}^{n} f(k) \sum_{j=i}^{k} C^j_k \times C^i_j \times (-1)^{(j-i)}$$

上述等式中求和保证 $i \leq j \leq k \leq n$ 。

令 $\sum_{k=i}^{n}f(k)$ 右侧的系数为 $a$ ，即 $a=\sum_{j=i}^{k} C^j_k \times C^i_j \times (-1)^{(j-i)}$ 。

• 当 $k=i$ 时，$a=1$ 。

• 当 $k \neq i$ 时，$a=0$ 。

此时，$原式 = f(i)$ ，证毕。

费马小定理

定理：

$$1 \equiv a^{p-1} \mod p$$

等价于（逆元）：

$$\frac{1}{a} \equiv a^{p-2} \mod p$$

证明：

令 $S=\{1,2,\cdots,p-1 \}$ ，$T=\{a,2a,\cdots,(p-1)a\}$ 。

反证法可证 $S$ 和 $T$ 为同一排列。

$$\prod_{i=1}^{p-1} i \equiv \prod_{i=1}^{p-1}i \times a \mod p$$ $$1 \equiv a^{p-1} \mod p$$

证毕。

卡特兰数

拓展欧几里得

组合数模板

namespace comb{
	//const int P=mod;
	int qpow(int a,int x){
		if(x==0) return 1;
		int res=qpow(a,x>>1)%P;
		if(x%2) return res*res%P*a%P;
		else return res*res%P;
	}
	const int maxn=1e3+10; // 模数以下
	int inv[maxn],fac[maxn]; 
	void init(){
		//阶乘
		fac[0]=1;
		for(int i=1;i<maxn;i++) fac[i]=fac[i-1]*i%P;
		//逆元（线性
		inv[maxn-1]=qpow(fac[maxn-1],P-2);
		//cout<<fac[1000000]<<" "<<P<<endl;
		for(int i=maxn-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%P;
	}
	int C(int n,int m){ //$C _{n} ^{m}$
		if(m>n||m<0) return 0;
		return fac[n]*inv[m]%P*inv[n-m]%P;
	}
}