组合数学玄学操作

以下公式均不给出证明,目的是为了让结论一目了然。

组合数相关

CnmCmk=CnkCnkmk

基本递推式 Cnm=Cn1m1+Cn1m

二项式定理 (a+b)n=i=0nCniaibni

i=0n(Cni)2=C2nn

Cn+mk=i=0kCniCmki

卢卡斯定理(要求 p 是质数) Cnm%p=Cn/pm/pCn%pm%p%p

上指标反转 (nm)=(1)m(mn1m)

第一类斯特林数相关

snm=sn1m1+(n1)sn1m

xn=msnmxm

第二类斯特林数相关

Snm=Sn1m1+mSn1m

nm=k=0mSmkCnkk!

上式的二项式反演,组合数拆开后可转换为卷积形式 Snm=1m!k=0m(1)mkCmkkn