排列和组合

阶乘

$n!=n\times(n-1)\times(n-2)\times\ldots\times2\times1$

先让第一个人选一个位置，有 $n$ 种选法。再让第二个人选一个位置，有 $n-1$ 种选法.以此类推。

组合数

$C^m_n=n!\div m!\div(n-m)!$

把 $n$ 个球排成一排，选前 $m$ 个，排成一排的方案数是 $n!$。由于我们只关心前 $m$ 个球是什么，与顺序无关，所以就是 $n!\div m!\div(n-m)!$。

$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$

考虑最后一个球选不选，如果选，方案数是 $C_{n-1}^{m-1}$，否则是 $C_{n-1}^m$。

组合数问题（NOIP2016 TG D2T1 / P2822）

预处理出 $C_i^j$，求二维前缀和即可。

可重排列、可重集合和圆排列

可重排列

有 $n$ 种颜色的球，第 $i$ 种有 $a_i$ 个。把这些球排成一排，有几种方法？

令 $S$ 为 $a$ 的和。

答案为 $C_S^{a_1}\times C_{S-a_1}^{a_2}\times C_{S-a_1-a_2}^{a_3}\times\ldots$，化解后得 $\frac{S!}{a_1!\times a_2!\times a_3!\times\ldots\times a_n!}$

另外一种理解，先将 $S$ 个数随便排，有 $S!$ 种方案。但是有 $a_i$ 个球颜色相同，所以除以 $a_i!$。可以直接得出化简后的通项公式。

可重集合

有 $n$ 种颜色的球，每种球有无限个，求选出 $m$ 个球的方案数。

在 $m$ 个球中插入 $n-1$ 个隔板，两个隔板之间的球表示每一类选几个。

这样相当于有 $m+1-1$ 个空位，选 $m$ 个放球，$n-1$ 个放隔板。

方案数是 $C_{m+n-1}^{n-1}$。

圆排列

$n$ 个人站成一个圈有几种站法？

如果把旋转看成不同的，方案数是 $n!$，所以实际方案数是 $\frac{n!}{n}=(n-1)!$

错排问题

有 $n$ 个小朋友和 $n$ 个凳子，第 $i$ 个小朋友坐在 $i$ 号凳子上。现在让这些小朋友站起来，重新找凳子坐下，不能坐到原来的凳子上。有多少种方案？

二项式定理

$(x+y)^n=\sum_{i=0}^n\dbinom{n}{i}x^iy^{n-i}$

卢卡斯定理

$\dbinom{n}{m}\bmod p=\dbinom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{m}{p}\right\rfloor}\dbinom{n\bmod p}{m\bmod p}\bmod p$

容斥原理

$|A\cup B|=|A|+|B|-|A\cap B|$