​

线排列

• $P(n, r) = \frac{n!}{(n-r)!}$
• $P(n, r) = nP(n-1, r-1)$
• $P(n,r) = rP(n-1, r-1) + P(n-1, r)$

---

圆排列

• $\frac{P(n,r)}{r} = \frac{n!}{r(n-r)!}$

---

重排列

B=$\{\infty * b_1, \dots , \infty * b_n \}$ 的r-排列：$n^r$

---

无限重集的r-组合

• $F(n,r) = C(n + r - 1, r)$
• $x_1 + x_2 + … + x_n = r : F(n, r)$

---

二项式定理

• $(x+y)^n=\sum_{k=0}^nC(n,k)x^ky^{n-k}$
• $(x+y)^n=\sum_{k=0}^nC(n,n-k)x^ky^{n-k}$
• $(1 + x)^n=\sum_{k=0}^nC(n, n - k)x^k$
• $\frac{1}{1 - x} = \sum^{\infty}_{k=0}x^k$
• $\frac{1}{1+x} = \sum^{\infty}_{k=0}(-1)^kx^k$
• $(1+x)^{-n}=\sum_{k=0}^{\infty}(-1)^kC(n+k-1, k)x^k$

---

容斥原理

$\arrowvert \overline{A_1} \cap \overline{A_2} \cap \dots \cap \overline{A_n} \arrowvert = $

$ |S| - \sum|A_i| + \sum|A_i \cap A_j| - \sum|A_i \cap A_j \cap A_k| + … + (-1)^n|A_1 \cap A_2 \cap … A_n| $

---

一个整数能被Lcm(i, j)整除， 当且仅当它既能被i整除也能被j整除。

• 分类！

错排问题

• $$D_n=n!\sum_{k=0}^n(-1)^k\frac{1}{k!} \approx n!e^{-1}$$
• $$D_n = (n-1)(D_{n-1}+D_{n-2})$$

相对位置有限制排列问题

• $$Q_n=\sum_{k=0}^{n-1}(-1)^kC(n-1, k)(n-k)!$$
• $$Q_n = D_n + D_{n-1}$$

错排和相对位置有限制排列都可以用容斥原理直接做

一般有限制排列

• $R(c) = xR(c_i) + R(c_e)$

  $c_i:删去A_i所在行列剩下的棋盘$

  $c_e:删去A_i剩下的棋盘$

• 对于相互独立的棋盘$C_1C_2$有：

  $R(c) = R(c_1)R(c_2)$

• n元有禁位排列数：

  $n! - r_1(n-1)! + r_2(n-2)! + … + r_n(-1)^n$

---

母函数

普通母函数

$$f(x) = \sum_{i=0}^{\infty}a_ix^i$$ $$C(x) = A(x) + B(x)\Leftrightarrow c_i=a_i+b_i$$ $$C(x) = A(x)B(x) \Leftrightarrow c_i= \sum_{k=0}^ia_kb_{i-k}$$

指数母函数

$$f_e(x) = \sum_{i=0}^{\infty}a_i\frac{x^n}{i!}$$ $$C(x) = A(x) + B(x) \Leftrightarrow c_i = a_i + b_i$$ $$C(x) = A(x)B(x) \Leftrightarrow c_i = \sum_{k=0}^i\lgroup_k^i\rgroup a_kb_{i-k}$$

• $f(x) = \int_{0}^{\infty}e^{-s}f_e(sx)d_s$

• $e^x=\sum_{i=0}^\infty \frac{x^i}{i!}$

• $\frac{e^{-x}+e^x}{2} = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} …$

• $e^{ax} = \sum_{n=0}^{\infty}a^n\frac{x^n}{n!}$*

---

常系数线性齐次递归关系

• q是方程的m重根，则$q^n, nq^n, …, n^{m-1}q^n$都是a_n的解
• q是方程的1重根，则$q^n$是方程的解

非齐次递归关系

$a_n = \overline{a_n} + a_n^*$

$\overline{a_n}$：非齐次的特解

$a_n^*:$齐次的通解

---

f(n) 是n的k次多项式：

• 1不是齐次方程的特征根
  • $\overline{a_n} = A_0n^k + A_1n^{k-1} + … + A_k$
• 1是齐次方程的m重特征根
  • $\overline{a_n} = (A_0n^k + A_1n^{k-1} + … + A_k)n^m$

f(n)是$\beta^n$的形式时：

• $\beta$不是齐次方程的特征根
  • $\overline{a_n} = A \dot \beta^n$
• $\beta$是齐次方程的m重特征根
  • $\overline{a_n} = An^m\beta^n$