组合数学玄学操作 发表于 2020-01-02 更新于 2020-12-22 分类于 整理 阅读次数: 112 以下公式均不给出证明,目的是为了让结论一目了然。 组合数相关 CnmCmk=CnkCn−km−k 基本递推式 Cnm=Cn−1m−1+Cn−1m 二项式定理 (a+b)n=∑i=0nCniaibn−i ∑i=0n(Cni)2=C2nn Cn+mk=∑i=0kCniCmk−i 卢卡斯定理(要求 p 是质数) Cnm%p=Cn/pm/pCn%pm%p%p 上指标反转 (nm)=(−1)m(m−n−1m) 第一类斯特林数相关 snm=sn−1m−1+(n−1)sn−1m xn―=∑msnmxm 第二类斯特林数相关 Snm=Sn−1m−1+mSn−1m nm=∑k=0mSmkCnkk! 上式的二项式反演,组合数拆开后可转换为卷积形式 Snm=1m!∑k=0m(−1)m−kCmkkn
Gitalk 加载中 ...