数学笔记——组合计数

啊~我讨厌数学 ——沃若老师

本笔记讲述了与组合计数有关的内容！

组合数

$$C(n,m)=C(n,n-m)=\frac{n!}{(n-m)!m!}$$

其中 $n!=n\times(n-1)\times(n-1)\times\dotsc\times 1$，为了使 $n!=n\times(n-1)!$ 成立我们令 $0!=1$

组合数的递推公式（可用作预处理）时间复杂度 $O(nm)$：

$$C(n,m)=C(n-1,m)+C(n-1,m-1)$$

当然在给定模数的情况下你也可以预处理阶乘和阶乘的逆元，时间复杂度下降到 $O(n)$

可重排列

考虑有 $n$ 个球，第 $i$ 种球有 $a_i$ 个。问有几种排列？

令 $Q=\sum a$。我们分步考虑：

1. 考虑第$1$个球，方案有 $S(Q,a_1)$
2. 考虑第$2$个球，方案有 $S(Q-a_1,a_2)$
   以此类推可得

$$ans=C(Q,a_1)\times C(Q-a_1,a_2)\times\dotsc\\=\frac{Q!}{a_1!(Q-a_1)!}\times\frac{(Q-a_1)!}{a_2!(Q-a_1-a_2)!}\times\frac{(Q-a_1-a_2)!}{a_3!(Q-a_1-a_2-a_3)!}\times\dotsc\\=\frac{Q!}{a_1!a_2!a_3!\dotsc a_n!}$$

或者理解为先把它们当成全部不同，有 $Q!$ 种方案，但因为第 $i$ 种有 $a_i$ 个球颜色相同，所以除以 $a_i$。

圆排列

$n$ 个人站成圈有多少种站法（旋转后相同记为相同）？

我们采用大眼观察法：

不难发现：

$$f(n)=(n-1)!$$

其实这是因为我们可以固定 $1$ 为起点，剩下 $n-1$ 个随机排列，得 $(n-1)!$

错排问题

有 $n$ 个小朋友，为他们排列使得他们不坐在自己的原本位置上，记方案数为 $f(n)$，求方案数。

第 $n$ 个小朋友可以坐在 $1$ 到 $n-1$ 上的任意位置。我们假设坐在 $i$ 号凳子上：

• $i$ 号小盆友坐在 $n$ 号凳子上，相当于 $n-2$ 的子问题
• $i$ 号小盆友不坐 $n$ 号凳子上，我们把 $n$ 号凳子和 $i$ 号互换，相当于 $n-1$ 的子问题

$$f(n)=(n-1)\times[f(n-1)+f(n-2)]$$

二项式定理

$$(x+y)^n=\sum^n_{i=0} S(n,i) x^i y^{n-1}$$

为啥呢？我们不形式化的证明（我也不太会）。考虑 $(x+y)^3$，我们将它们写出：$(x+y)(x+y)(x+y)$它的结果为 $x^3 + 3x^2y + 3xy^2 + y^3$。考虑结果中的 $3x^2y$，它应该是三个 $x^2y$，即 $(\textcolor{red}{x}+y)(\textcolor{red}{x}+y)(x+\textcolor{red}{y})$ 和 $(\textcolor{red}{x}+y)(x+\textcolor{red}{y})(\textcolor{red}{x}+y)$ 还有 $(x+\textcolor{red}{y})(\textcolor{red}{x}+y)(\textcolor{red}{x}+y)$，所以系数 $3$ 就是可以选择到 $x^2y$ 的个数，只看左边就等于只选择 $1$ 个 $x$ 的个数，即 $C(3,1)$

卢卡斯定理

当 $p$ 是质数，当 $n$ 大 $m$ 大 $p$ 不大时：

$$C(n,m)\equiv C(\lfloor \frac{n}{p} \rfloor,\lfloor \frac{m}{p} \rfloor) \times C(m\bmod p,n\bmod p) \pmod p$$