记录一些组合数学的公式。

公式

组合数 $C(n,m)$

  1. $C_n^0 = C_n^n = 1$
  2. $C_n^k = C_{n-1}^k + C_{n-1}^{k-1}$
  3. $C_n^k = \frac{n!}{k!(n-k)!}$

注:$0! = 1, (0!)^{-1} = 1$

证明公式2

$n$ 个中选 $k$ 个, 考虑 $n$ 个元素中的第一个元素:

  1. 如果它被选中,有 $C_{n-1}^{k-1}$ 种。
  2. 如果它没有被选中,有 $C_{n-1}^k$ 种。

二项式定理

$(a+b)^n = \sum\limits_{k=0}^n C_n^ka^kb^{n-k}$


卡特兰数 (Catalan)

通项公式:

  1. $H_n = 1 ~ (n=0,1)$

  2. $H_n = \frac{C_{2n}^n}{n+1}~(n \geq 2)$

  3. $H_n = C_{2n}^n - C_{2n}^{n-1}$

递推式:

  1. $H_n = \sum\limits_{i=0}^{n-1}H_{i}H_{n-i-1} = H_0H_{n-1} + H_1H_{n-2} + … + H_{n-1}H_0$

  2. $H_n = \frac{(4n-2)}{n+1} H_{n-1}$


第二类斯特林数

$S(n,m)$ 代表将 $n$ 个不同的小球,放进 $m$ 个相同,非空盒子的方案数

通项公式:

$S(n,m) = \sum\limits_{i=0}^m (-1)^{m-i}\frac{i^n}{i!(m-i)!}$

递推式:

$S(n,m) = m*S(n-1,m) + S(n-1,m-1)$

证明

考虑第一个小球,有两种情况:

  1. 独占一个盒子:相当于,其他 $n-1$ 个小球要放进 $m-1$ 个盒子中,且盒子不为空,所以为 $S(n-1,m-1)$
  2. 不独占一个盒子:相当于,先将其他 $n-1$ 个小球放进 $m$ 个盒子中,且盒子不为空,然后从 $m$ 个盒子中选一个,把当前小球放进去,所以为 $m*S(n-1,m)$

经典例题

例1 男女生排列问题

题意

三个女生和五个男生站成一排。

  1. 如果女生必须全排在一起,有多少种排法?

  2. 如果女生不能相邻,有多少种排法?

  3. 如果两端都不排女生,有多少种排法?

  4. 如果两端不都排女生,有多少种排法?

第一题答案

将3个女生看作1个,所以就有 $A_6^6$ 种。对于女生内部的排列有 $A_3^3$ 种。所以总共为 $A_6^6A_3^3$ 种。

第二题答案

先排男生,有 $A_5^5$ 种,然后将女生插入6个空位中,有 $A_6^3$ 种。所以总共为 $A_5^5A_6^3$ 种。

第三题答案

先排好两个男生在两边,有 $A_5^2$ 种,两个男生中间的人就可以随便排了,就有 $A_6^6$ 种。所以总共为 $A_5^2A_6^6$ 种。

也可以这么想,让女生在中间的6个位置先选好3个,有 $A_6^3$ 种,剩下的男生随便排,有 $A_5^5$ 种。所以总共为 $A_6^3A_5^5$ 种,答案和上面一样。

第四题答案

所有排列情况有 $A_8^8$ 种,如果两边都排女生,有 $A_3^2A_6^6$ 种。所以总共为 $A_8^8 - A_3^2A_6^6$ 种。


例2 小球放盒子问题

假设有 $n$ 个小球,$m$ 个盒子。

小球无区别-盒子无区别-不允许空盒

略(还没遇到)

小球无区别-盒子无区别-允许空盒

略(还没遇到)

小球无区别-盒子有区别-不允许空盒

使用隔板法,在 $n$ 个小球中间放置 $m-1$ 块挡板,将小球分为不为空的 $m$ 部分。小球之间的空位有 $n-1$ 个。所以答案为

$C_{n-1}^{m-1}$

小球无区别-盒子有区别-允许空盒

先多加 $m$ 个小球,转化为 不允许空盒 的问题后,再把多加的 $m$ 个小球拿出来即可。所以答案为

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

小球有区别-盒子无区别-不允许空盒

答案就是第二类斯特林数 $S(n,m)$,递推式如上:

$S(n,m) = m*S(n-1,m) + S(n-1,m-1)$

小球有区别-盒子无区别-允许空盒

不允许空盒 的基础上,枚举一下 空盒的个数。所以答案为

$\sum\limits_{i=1}^{\min(n,m)}S(n,i)$

小球有区别-盒子有区别-不允许空盒

盒子无区别 的基础上,乘上盒子的排列 $m!$ 即可,所以答案为:

$S(n,m) * m!$

小球有区别-盒子有区别-允许空盒

每个小球可以随便选,互不影响,所以答案为:

$n^m$


例3 错排问题

题意

有 $1,2,3,…,n$ 这些数字,重新排序使得不存在任何一个数字的位置和原来相同,有多少种方法?

答案

$D_n = (n-1)(D_{n-1} + D_{n-2})$,其中 $D_1 = 0, D_2 = 1$

证明:初始情况下如图:

img

在图中,上下两行对应的元素需要错开。我们设这种情况下,排序的方法有 $f(n)$ 种。

对于元素 $1$,我们可以选择除 $1$ 以外的任何一个元素,所以有 $n-1$ 种。

假设我们选了 $1 \rightarrow 2$,就会变成下图:

img

那么,再看元素 $2$:

  1. 如果 $2 \rightarrow 1$,那么就会变成下图,即 $f(n-2)$ 种。 img

  2. 如果 $2 \rightarrow 3 ~ or ~ 4 ~ or ~ … ~ n$,就相当于 $2$ 和 $1$ 必须错开,那就相当于下图,即 $f(n-1)$ 种。

    img

所以最终就可以得到 $f(n) = (n-1)(f(n-1) + f(n-2))$