计数公式总结

计数公式总结

本文总结了几个计数公式.

乘方

fc[1]=1;
for(ll x=2;x<=n;x++)
	fc[x]=fc[x-1]*x%mod;
ifc[n]=yt::kpow(fc[n],mod-2)%mod;
for(ll x=n-1;x;x--)
	ifc[x]=ifc[x+1]*(x+1)%mod;

排列数

\(n\) 取 \(k\), 顺序有关.

\(A_{n}^{k}=\cfrac{n!}{(n-k)!}\)

\(A_{n}^{k}=(n-k+1)*A_{n}^{k-1}\)

组合数

\(n\) 取 \(k\), 顺序无关.

\(C_{n}^{k}=C_{n}^{n-k}=\cfrac{n!}{k!(n-k)!}\)

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

吸收公式: \(C_{n}^{k}=\cfrac{n}{k}*C_{n-1}^{k-1}\)

上指标求和: \(\sum\limits_{x\in[0,n]}C_{x}^{k}=C_{n+1}^{k+1}\)

上指标反转: \(C_{n}^{k}=(-1)^{k}*C_{k-n-1}^{k}\)

\(C_{n}^{k}*C_{k}^{x}=C_{n}^{x}*C_{n-k}^{x-k}\)

平行求和: \(\sum\limits_{k\le n}C_{x+k}^{k}=C_{x+n+1}^{n}\)

二项式

\((a+b)^{k}=\sum\limits_{x\in[0,n]}C_{k}^{x}a^{x}b^{k-x}\)

\((a+1)^{k}=\sum\limits_{x\in[0,n]}C_{k}^{x}a^{x}\)

\(\sum\limits_{k\in A}(C_{n}^{x+k}*C_{m}^{y-k})=C_{n+m}^{x+y}\)

\(\sum\limits_{k\in A}(C_{n}^{x+k}*C_{m}^{y+k})=C_{n+m}^{n-x+y}=C_{n+m}^{x+m-y}\)

\(\sum\limits_{k\in A}(C_{n}^{x+k}*C_{m+k}^{y}*(-1)^{k})=(-1)^{n+x}*C_{m-x}^{y-n}\)

\(\sum\limits_{k\le n}(C_{n-k}^{x}*C_{m}^{k-y}*(-1)^{k})=(-1)^{n+x}*C_{m-x-1}^{n-x-y}\)

\(\sum\limits_{k\in[-m,n]}(C_{n-k}^{x}*C_{m+k}^{y})=C_{n+m+1}^{x+y+1}\)

vandermonde 卷积: \(\sum\limits_{k\in A}(C_{n}^{k}*C_{m}^{x-k})=C_{n+m}^{x}\)

可重组合数

\(n\) 取 \(k\), 顺序无关, 可以重复.

\(C_{n+k-1}^{k}\)

可重排列数

\(n\) 取 \(k\), 其中有重复的.

\(\cfrac{n!}{\prod\limits_{x\in[v_{min},v_{max}]}(tot_{x}!)}\)

圆排列

\(n\) 个不同元素排列成环形.

\((n-1)!\)

第一类 stirling 数

\(n\) 个不同元素排成 \(k\) 个循环排列的方式数.

divide to cycles then perm.

\(dcp_{n}^{k}=dcp_{n-1}^{k-1}+(n-1)*dcp_{n-1}^{k}\)

第二类 stirling 数

\(n\) 个不同元素划分进 \(k\) 个非空集合的方案数.

dsivide to sets.

\(ds_{n}^{k}=ds_{n-1}^{k-1}+k*ds_{n-1}^{k}\)

bell 数

\(n\) 个元素所有划分总数.

\(bell_{n}=\sum\limits_{x\in[1,n]}ds_{n}^{k}\)

catalan 数

\(cat_{n}=\cfrac{c_{2n}^{n}}{n+1}\)

\(12\) 种计数法

\(x\) 个球	\(n\) 个容器	无限制	每个容器至多 \(1\) 球	每个容器至少 \(1\) 球
不同	不同	\(n^{x}\)	\(x!*C_{n}^{x}\)	\(x!*ds_{n}^{x}\)
不同	相同	\(\sum\limits_{k\in[1,n]}ds_{x}^{k}\)	\(x\le n\)	\(ds_{x}^{n}\)
相同	不同	\(C_{x+n-1}^{n-1}\)	\(C_{n}^{x}\)	\(C_{x-1}^{n-1}\)
相同	相同	\(f_{x,n}\)	\(x\le n\)	\(f_{x-n,n}\)

\(f\) 有 dp 方程 \(f_{x,y}=f_{x-y,y}+f_{x,y-1}\), 含义是 前面所有容器的球数 +1, 或者获得一个新的盒子.

错排列

\(n\) 个元素的排列, 只有 \(k\) 个元素能排在自己应该排的位置, 剩余 \(n-k\) 个元素必须排在自己不该排的位置.

\(d_{n}^{k}=(n-k)!*\sum\limits_{x\in[2,n-k]}((-1)^{x}*\cfrac{1}{x!})\)