• 小白整理，有误请大佬斧正

排列组合

排列

1. 无其他限制下，从n个物体种选择r个出来的所有排列情况为\(A(^r_n)=\frac{n!}{(n-r)!}\) r>n时\(A(^r_n)=0\)

2. 从n个物体种选择r个的圆排列为\(P(^r_n)=\frac{A(^r_n)}{r}\)

多重集的排列

1. 设n种元素每种互不相同,每种元素都有\(\infty\)种（无限多重集），在这n种中取r个的排列为\(n^r\)

2. 设n种元素每种互不相同,每种元素都有\(a_1,a_2,a_3…a_n\)种（有限多重集）,在这n种中取r个,当\(min({a_1,a_2,…a_n})>=r\)时，排列数依然为\(n^r\)

3. 设n种元素每种互不相同,每种元素都有\(a_1,a_2,a_3…a_n\)种（有限多重集）,其全排列为\(\frac{(a_1+a_2+a_3+…+a_n)!}{{a_1}!{a_2}!…{a_n}!}\)

4. 设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}!}\)

组合

1. 无限制下，从n个物体选择r个物体的组合为\(C(n,r)=\frac{n!}{r!(n-r)!}\), 亦写作\((^n_r)=\frac{n!}{r!(n-r)!}\), r>n时，\(C(n,r)=0\)

多重集的组合

1. 设n种元素每种互不相同,每种元素都有\(\infty\)种（无限多重集），在这n种中取r个的组合为\((^{n+r-1}_{r})=(^{n+r-1}_{n-1})\)

2. 设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})\)

3. 设n种元素每种互不相同,每种元素都有\(a_1,a_2,a_3…a_n\)种（有限多重集）,在这n种中取r个,当\(min({a_1,a_2,…a_n})<r\)时,组合为$$

组合数公式

1. \(C(_n^k)=C(n-1,k)+C(n-1,k-1)\),杨辉恒等式
2. \(C(_n^k)=C(n,n-k)\),对称性
3. \(\sum_{i=0}^nC(n,i)=2^n\),单行和
4. \(\sum_{i=0}^nC(n,i)^2=C(2n,n)\),单行平方和
5. \(\sum_{i=0}^nC(_{k+i}^k)=C(_{n+k+1}^{k+1})\),斜\(60^\circ\)行和=反斜下一行对应值
6. \(f(n)=\begin{cases}
   \sum_{i=0}^{n/2-1}C(n/2+i,2i+1)& \text n\equiv 0 \bmod 2\\
   \sum_{i=0}^{(n-1)/2}C\bigg((n-1)/2+i,2i\bigg)& \text n\equiv 1 \bmod 2
   \end{cases}\) , \(\big(30^\circ\)斜行和等于Fibonacci数列\(\big)\)
7. \(C(n,i)=\frac{n-i+1}{i}C(n,i-1)\), 递推式
8. \(C(n,m)\)的奇偶性:n&m=m为奇，否则为偶（lucas定理推论）

二项式定理

• \((a+b)^n=\sum_0^nC(_n^i)a^ib^{n-i}\)

鸽巢原理

• n+1只鸽子飞向n个鸽巢，一定存在两只鸽子飞向了同一个鸽巢

容斥原理

• 
  容斥原理的题常考虑反面

错排问题

1. \(D_n=n!\big(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+…+(-1)^n\frac{1}{n!}\)
2. 递推式推导

考虑在\(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…\)

3. \(D_n=nD_{n-1}+(-1)^n\)

特殊计数序列

Fibonacci序列

1. \(f_n=f_{n-1}+f_{n-2},n\geq3,f_1=f_2=1\)
2. \(f_n=\frac{1}{\sqrt{5}}\big[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\big]\)
3. \(f_n\equiv 276601065(691504013^n-308495997^n)\bmod 10^9+9\)，注意仅限模1e9+9的情况下。
4. \(\sum_{i=1}^nf_i=f_{n+2}-1\),前缀和公式
5. \(f_1+f_3+…+f_{2n-1}=f_{2n}\),奇数项前缀和公式
6. \(f_2+f_4+..+f_{2n}=f_{2n+1}\),偶数项前缀和公式
7. \(\sum_{i=1}^nf_i^2=f_nf_{n+1}\),平方和公式
8. \(f_n^2=(-1)^{n+1}+f_{n-1}f_{n+1}\)
9. \(f_{2n}=f_n(f_{n+1}+f_{n-1})\)
10. \(f_n \equiv 0\bmod p\Rightarrow f_{nk} \equiv 0 \bmod p,\mbox{k为正整数}\)
11. \(gcd(f_n, f_m) = f_{gcd(n, m)}\)，
12. 对于质数P, f[n] % P 有循环节， 如果5是模P的二次剩余，则循环节长度是P – 1的因子， 否则是2(P + 1)的因子; 类Fibonacci也类似。
13. \(f_n=\sum_{i=0}^mC(n-1-i,i),m \leq n-1-m\)，杨辉三角斜\(30^\circ\)度求和

catalan数

1. \(C_n=\sum_{k=0}^{n-1}C_nC_{n-k-1},n \geq 2,C_0=C_1=1\)
2. \(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\)…
3. \(C_n=\frac{C(2n,n)}{n+1}=C(2n,n)-C(2n,n-1)\),注意组合数区分卡特兰数
4. \(C_n=\frac{4n-2}{n+1}C_{n-1}\)

用于栈进出序列，二叉树的种类枚举、多边形分成三角形的个数、圆括弧插入公式中的方法数。。。

Stirling数

\(Stirling估计式:n!\sim\sqrt{2\pi n}{(\frac{n}{e})}^n\)

第一类Stirling数

1. 正负,其绝对值的实际意义为n个元素的集合组成m个的圆排列的数目，\((n\geq m)\)
2. 递推式：\(S_u(n,m)=S_u(n-1,m)+(n-1)S_u(n-1,m-1)\)
3. 边界以及结论

\(S_u(0,0)=1\\S_u(n,0)=0\\S_u(n,1)=1\\S_u(n,n)=1\\S_u(n,n-1)=C(n,2)\\S_u(n,n-2)=2C(n,3)+3C(n,4)\\\sum_{i=0}^nS(n,i)=n!\)

第二类Stirling数

1. n个元素组成拆成m个非空集合的方案数
2. 递推式：\(S_2(n,m)=S_2(n-1,m-1)+mS_2(n-1,m)\)
3. 边界以及结论

\(S_2(n,0)=0^n\\S_2(n,1)=1\\S_2(n,n)=1\\S_2(n,2)=2^{n-1}-1\\S_2(n,n-1)=C(n,2)\\S_2(n,n-2=C(n,3)+3C(n,4))\)

拆分数

1. 整数n拆成r个正整数之和为n的r拆分数，记作\(P_r(n)\)
2. \(P_1(n)=1,P_n(n)=1,P_{n-1}(n)=1,P_{n-2}(n)=2,P_{n-3}(n)=3\)
3. \(P_2(n)=\big\lceil{\frac{n-1}{2}}\big\rceil,n \geq 2\)
4. \(P_r(n)=\sum_{i=1}^r P_i(n-r)\)

装箱问题

• n个球放入r个盒子成为装箱问题

1. 相同球n和相同盒子r，\(n \geq r\)

无空盒子 \(P_r(n)\)
可以有空盒子 \(\sum_{i=1}^rP_i(n)\)

2. 相同球不同盒子

无空盒子 \(C(n-1,r-1)\)
可以有空盒子 \(C(n+r-1,r-1)\)

3. 不同球相同盒子

无空盒子 \(S_2(n,r)\)
可以有空盒 \(\sum_{i=1}^rS_2(n,i)\)

4. 不同球不同盒子

无空盒子 \(r!S_2(n,r)\)
可以有空盒子 \(r^n\)

生成函数

• \((1-x)^{-m}=\sum_0^\infty{x^i(^{m+i-1}_{m-1})}\)

burnside引理&polya定理

• 两者都是解决考虑旋转或是翻转等计数问题的理论

1. 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_1(a_i)
\]

\(\mbox{其中}c_1(a_i)\mbox{代表}a_i\mbox{中包含的一阶循环(不动点)的个数}\)

2. polya定理

设\(G\)是n个对象的一个置换群, 用m种颜色染图这n个对象，则不同的染色方案数为：

\[\frac{1}{\overline{|G|}}\sum_{i=1}^gm^{c(\overline{p_i})}$$,
其中$G=\{\overline{p_1},\overline{p_2},…\overline{p_g}\}, c(\overline{p_i})\mbox{表示}\overline{p_i}\mbox{的循环节数(阶)}$\]