计数公式总结
本文总结了几个计数公式.
乘方
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}\)
可重组合数
\(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}\)