小白整理，有误请大佬斧正
排列组合
排列
无其他限制下，从n个物体种选择r个出来的所有排列情况为A^r_n)=frac{n!}{n-r)!}) r>n时A^r_n)=0)
从n个物体种选择r个的圆排列为P^r_n)=frac{A^r_n)}{r})
多重集的排列
设n种元素每种互不相同,每种元素都有infty)种（无限多重集），在这n种中取r个的排列为n^r)
设n种元素每种互不相同,每种元素都有a_1,a_2,a_3…a_n)种（有限多重集）,在这n种中取r个,当min{a_1,a_2,…a_n})>=r)时，排列数依然为n^r)
设n种元素每种互不相同,每种元素都有a_1,a_2,a_3…a_n)种（有限多重集）,其全排列为frac{a_1+a_2+a_3+…+a_n)!}{{a_1}!{a_2}!…{a_n}!})
设n种元素每种互不相同,每种元素都有a_1,a_2,a_3…a_n)种（有限多重集）,在这n种中取r个,当min{a_1,a_2,…a_n})<r)时,排列为sum_{k_1+k_2+…+k_n=r}frac{r!}{{k_1}!{k_2}!…{k_n}!})
组合
无限制下，从n个物体选择r个物体的组合为Cn,r)=frac{n!}{r!n-r)!}), 亦写作^n_r)=frac{n!}{r!n-r)!}), r>n时，Cn,r)=0)
多重集的组合
设n种元素每种互不相同,每种元素都有infty)种（无限多重集），在这n种中取r个的组合为^{n+r-1}_{r})=^{n+r-1}_{n-1}))
设n种元素每种互不相同,每种元素都有a_1,a_2,a_3…a_n)种（有限多重集）,在这n种中取r个,当min{a_1,a_2,…a_n})>=r)时，组合数为^{n+r-1}_{r})=^{n+r-1}_{n-1}))
设n种元素每种互不相同,每种元素都有a_1,a_2,a_3…a_n)种（有限多重集）,在这n种中取r个,当min{a_1,a_2,…a_n})<r)时,组合为$$
组合数公式
C_n^k)=Cn-1,k)+Cn-1,k-1)),杨辉恒等式
C_n^k)=Cn,n-k)),对称性
sum_{i=0}^nCn,i)=2^n),单行和
sum_{i=0}^nCn,i)^2=C2n,n)),单行平方和
sum_{i=0}^nC_{k+i}^k)=C_{n+k+1}^{k+1})),斜60^circ)行和=反斜下一行对应值
fn)=egin{cases}
sum_{i=0}^{n/2-1}Cn/2+i,2i+1)& ext nequiv 0 mod 2\
sum_{i=0}^{n-1)/2}Ciggn-1)/2+i,2iigg)& ext nequiv 1 mod 2
end{cases}) , ig30^circ)斜行和等于Fibonacci数列ig))
Cn,i)=frac{n-i+1}{i}Cn,i-1)), 递推式
Cn,m))的奇偶性:n&m=m为奇，否则为偶（lucas定理推论）
二项式定理
a+b)^n=sum_0^nC_n^i)a^ib^{n-i})
鸽巢原理
n+1只鸽子飞向n个鸽巢，一定存在两只鸽子飞向了同一个鸽巢
容斥原理
容斥原理的题常考虑反面
错排问题
D_n=n!ig1-frac{1}{1!}+frac{1}{2!}-frac{1}{3!}+…+-1)^nfrac{1}{n!})
递推式推导
考虑在D_{n-1})中加入n来生成n个数的错排，数n可以与前面n-1个数任一交换即可，贡献为n-1)D_{n-1})
考虑在有1..n-1的一个序列，我们直接加入n来生成n的错排，可以在n-1个数任选一个数与n交换位置，然后剩下的n-2个数进行错排，这样就生成了n的错排，贡献为n-1)D_{n-2})
因此最终的递推式就是D_n=n-1)D_{n-1}+D_{n-2}))
D_1=0,D_2=1,D_3=2,D_4=9…)
D_n=nD_{n-1}+-1)^n)
特殊计数序列
Fibonacci序列
f_n=f_{n-1}+f_{n-2},ngeq3,f_1=f_2=1)
f_n=frac{1}{sqrt{5}}ig[frac{1+sqrt{5}}{2})^n-frac{1-sqrt{5}}{2})^nig])
f_nequiv 276601065691504013^n-308495997^n)mod 10^9+9)，注意仅限模1e9+9的情况下。
sum_{i=1}^nf_i=f_{n+2}-1),前缀和公式
f_1+f_3+…+f_{2n-1}=f_{2n}),奇数项前缀和公式
f_2+f_4+..+f_{2n}=f_{2n+1}),偶数项前缀和公式
sum_{i=1}^nf_i^2=f_nf_{n+1}),平方和公式
f_n^2=-1)^{n+1}+f_{n-1}f_{n+1})
f_{2n}=f_nf_{n+1}+f_{n-1}))
f_n equiv 0mod pRightarrow f_{nk} equiv 0 mod p,mbox{k为正整数})
gcdf_n, f_m) = f_{gcdn, m)})，
对于质数P, f[n] % P 有循环节， 如果5是模P的二次剩余，则循环节长度是P – 1的因子， 否则是2P + 1)的因子; 类Fibonacci也类似。
f_n=sum_{i=0}^mCn-1-i,i),m leq n-1-m)，杨辉三角斜30^circ)度求和
catalan数
C_n=sum_{k=0}^{n-1}C_nC_{n-k-1},n geq 2,C_0=C_1=1)
C_0=1,C_1=1,C_2=2,C_3=5,C_4=14,C_5=42,C_6=132,C_7=429,C_8=1430,C_9=4852)…
C_n=frac{C2n,n)}{n+1}=C2n,n)-C2n,n-1)),注意组合数区分卡特兰数
C_n=frac{4n-2}{n+1}C_{n-1})
用于栈进出序列，二叉树的种类枚举、多边形分成三角形的个数、圆括弧插入公式中的方法数。。。
Stirling数
Stirling估计式:n!simsqrt{2pi n}{frac{n}{e})}^n)
第一类Stirling数
正负,其绝对值的实际意义为n个元素的集合组成m个的圆排列的数目，ngeq m))
递推式：S_un,m)=S_un-1,m)+n-1)S_un-1,m-1))
边界以及结论
S_u0,0)=1\S_un,0)=0\S_un,1)=1\S_un,n)=1\S_un,n-1)=Cn,2)\S_un,n-2)=2Cn,3)+3Cn,4)\sum_{i=0}^nSn,i)=n!)
第二类Stirling数
n个元素组成拆成m个非空集合的方案数
递推式：S_2n,m)=S_2n-1,m-1)+mS_2n-1,m))
边界以及结论
S_2n,0)=0^n\S_2n,1)=1\S_2n,n)=1\S_2n,2)=2^{n-1}-1\S_2n,n-1)=Cn,2)\S_2n,n-2=Cn,3)+3Cn,4)))
拆分数
整数n拆成r个正整数之和为n的r拆分数，记作P_rn))
P_1n)=1,P_nn)=1,P_{n-1}n)=1,P_{n-2}n)=2,P_{n-3}n)=3)
P_2n)=iglceil{frac{n-1}{2}}igceil,n geq 2)
P_rn)=sum_{i=1}^r P_in-r))
装箱问题
n个球放入r个盒子成为装箱问题
相同球n和相同盒子r，n geq r)
无空盒子 P_rn))
可以有空盒子 sum_{i=1}^rP_in))
相同球不同盒子
无空盒子 Cn-1,r-1))
可以有空盒子 Cn+r-1,r-1))
不同球相同盒子
无空盒子 S_2n,r))
可以有空盒 sum_{i=1}^rS_2n,i))
不同球不同盒子
无空盒子 r!S_2n,r))
可以有空盒子 r^n)
生成函数
1-x)^{-m}=sum_0^infty{x^i^{m+i-1}_{m-1})})
burnside引理&polya定理
两者都是解决考虑旋转或是翻转等计数问题的理论
burnside引理
设G={a_1,a_2,…a_g})是目标集[1,n])上的置换群。每个置换都写成不相交循环的乘积。 是在置换a_k)的作用下不动点的个数，也就是长度为1的循环的个数。通过上述置换的变换操作后可以相等的元素属于同一个等价类。若G)将[1,n])划分成l)个等价类，则：
[l=frac{1}{overline{|G|}}sum_{i=1}^gc_1a_i)
]mbox{其中}c_1a_i)mbox{代表}a_imbox{中包含的一阶循环不动点)的个数})
polya定理
设G)是n个对象的一个置换群, 用m种颜色染图这n个对象，则不同的染色方案数为：
[frac{1}{overline{|G|}}sum_{i=1}^gm^{coverline{p_i})}$$,
其中$G={overline{p_1},overline{p_2},…overline{p_g}}, coverline{p_i})mbox{表示}overline{p_i}mbox{的循环节数阶)}$]