组合数

组合数

定义式

$$\binom{a}{b}=\dfrac{a!}{b!(a-b)!}$$

递推式

$$\binom{a}{b}=\binom{a-1}{b}+\binom{a-1}{b-1}$$

lucas定理

$$\binom{a}{b}=\binom{a \bmod p}{b \bmod p}\times \binom{\frac{a}{p}}{\frac b p}\pmod p$$

1 2 3 4 5 6 7 8 9 10 11 12

inline long long C(int a,int b,int p){ int res=1; for(int i=1,j=a;i<=b;i++,j--) res=res*j%p, res=res*qpow(i,p-2)%p; return res; } inline int lucas(int a,int b,int p){ if(a<p && b<p) return C(a,b,p); return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p; }

卡特兰数

长度为 $2n$ 的合法括号序列数量：

$$\text{Catalan}_n=\binom{2n}{n}-\binom{2n}{n-1}=\dfrac{\binom {2n}{n}}{(n+1)}$$