Skip to content

组合数学基础

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

计数原理

加法原理

完成某件事有 nn 种途径,每种途径有 pip_i 个不同的方案,则完成这件事的方案总数为

i=1npi\sum_{i = 1}^{n} p_i

乘法原理

完成某件事需要进行 nn 个步骤,每个步骤有 pip_i 个不同的方案,则完成这件事的方案总数为

i=1npi\prod_{i = 1}^{n} p_i

排列组合

排列数

定义

nn 个不同的元素中取出 mm 个不同的元素作为一个排列,产生的不同排列数量记为 Anm\mathrm A_{n}^{m}。排列数的计算公式为:

Anm=n(n1)(n2)(nm+1)=n!(nm)!\mathrm A_{n}^{m} = n(n - 1)(n - 2) \cdots (n - m + 1) = \frac{n!}{(n - m)!}

特化

  1. m=0m = 0 时,只有一种方案即什么都不选;
  2. m=nm = n 时,排列为全排列 Anm=Ann=n!\mathrm A_{n}^{m} = \mathrm A_{n}^{n} = n!
  3. m>nm > n 时,排列数为 00

组合数

定义

nn 个不同元素种取出 mm 个元素作为一个集合,产生的不同集合数量记为 Cnm\mathrm C_{n}^{m},也常用 (nm)\displaystyle \binom{n}{m} 表示。组合数的计算公式为:

Cnm=AnmAmm=n!m!(nm)!\mathrm C_{n}^{m} = \frac{\mathrm A_{n}^{m}}{\mathrm A_{m}^{m}} = \frac{n!}{m!(n - m)!}

特化

  1. m=0m = 0 时,只有一种方案即什么都不选;
  2. m=nm = n 时,只有一种方案即全选;
  3. m>nm > n 时,组合数为 00

性质

  1. (nm)=(nnm)\displaystyle \binom{n}{m} = \binom{n}{n - m},选择 mm 个相当于选择 nmn - m 个留下来;
  2. Pascal 公式:(nm)=(n1m)+(n1m1)\displaystyle \binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1},常用于递推求组合数;
  3. m=0n(nm)=2n\displaystyle \sum_{m = 0}^{n} \binom{n}{m} = 2^n
  4. k=0n(1)k(ni)=[n=0]\displaystyle \sum_{k = 0}^{n} (-1)^k \binom{n}{i} = [n = 0]
  5. k=0n(nk)2=(2nn)\displaystyle \sum_{k = 0}^{n} \binom{n}{k}^2 = \binom{2n}{n}
  6. 斐波那契数列:Fn+1=k=0n(nkk)\displaystyle F_{n + 1} = \sum_{k = 0}^{n} \binom{n - k}{k}

多重集的排列数

多重集是指包含重复元素的广义集合。设 S={n1a1,n2a2, ,nkak}S = \{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\} 表示由 n1n_1a1a_1n2n_2a2a_2,…,nkn_kaka_k 组成的多重集,SS 的全排列个数为:

n!i=1kni!=n!n1!n2!nk!\frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!}

多重集的组合数

S={n1a1,n2a2, ,nkak}S = \{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\} 表示由 n1n_1a1a_1n2n_2a2a_2,…,nkn_kaka_k 组成的多重集。那么对于整数 rrr<ni,i[1,k]r < n_i, \forall i \in [1, k]),从 SS 中选择 rr 个元素组成一个多重集的方案数就是 多重集的组合数。这个问题等价于 x1+x2++xk=rx_1 + x_2 + \cdots + x_k = r 的非负整数解的数目,可以用插板法解决,答案为:

(r+k1k1)\binom{r + k - 1}{k - 1}

二项式定理

(a+b)n=k=0n(nk)akbnk(a + b) ^ n = \sum_{k = 0}^{n} \binom{n}{k} a^{k} b^{n - k}

证明

可以应用数学归纳法来证明二项式定理。

n=1n = 1 时,有:

(a+b)1=(n0)a0b1+(n1)a1b0=a+b\begin{aligned} & (a + b)^1 \\ =& \binom{n}{0} a^0 b^1 + \binom{n}{1} a^1 b^0 \\ =& a + b \end{aligned}

此情况下命题成立。

假设 n=mn = m 时命题成立,令 n=m+1n = m + 1,有:

(a+b)n=(a+b)(a+b)m=(a+b)k=0m(mk)akbmk=ak=0m(mk)akbmk+bk=0m(mk)akbmk=k=0m(mk)ak+1bmk+bk=0m(mk)akbmk+1=k=1m+1(mk1)akbmk+1+bk=0m(mk)akbmk+1=k=0m+1((mk1)+(mk))ak+bmk+1=k=0m+1(m+1k)ak+bmk+1=k=0n(nk)ak+bnk\begin{aligned} (a + b)^{n} &= (a + b) (a + b)^m \\ &= (a + b) \sum_{k = 0}^{m} \binom{m}{k} a^{k} b^{m - k} \\ &= a \sum_{k = 0}^{m} \binom{m}{k} a^{k} b^{m - k} + b \sum_{k = 0}^{m} \binom{m}{k} a^{k} b^{m - k} \\ &= \sum_{k = 0}^{m} \binom{m}{k} a^{k + 1} b^{m - k} + b \sum_{k = 0}^{m} \binom{m}{k} a^{k} b^{m - k + 1} \\ &= \sum_{k = 1}^{m + 1} \binom{m}{k - 1} a^k b^{m - k + 1} + b \sum_{k = 0}^{m} \binom{m}{k} a^k b^{m - k + 1} \\ &= \sum_{k = 0}^{m + 1} (\binom{m}{k - 1} + \binom{m}{k}) a^k + b^{m - k + 1} \\ &= \sum_{k = 0}^{m + 1} \binom{m + 1}{k} a^k + b^{m - k + 1} \\ &= \sum_{k = 0}^{n} \binom{n}{k} a^k + b^{n - k} \\ \end{aligned}

故命题成立。证毕。

自然数平方和公式

i=1ni2=n(n+1)(2n+1)6\sum_{i = 1}^{n} i^2 = \frac{n(n + 1)(2n + 1)}{6}

OEIS:A000330

证明

可以应用数学归纳法来证明自然数平方和公式。

n=1n = 1 时,有:

12=1=1×2×36=1\begin{aligned} 1^2 &= 1 \\ &= \frac{1 \times 2 \times 3}{6} \\ &= 1 \\ \end{aligned}

此情况下公式成立。

假设 n=kn = k 时公式成立,令 n=k+1n = k + 1,有:

12+22+32++(n1)2+n2=12+22+32++k2+(k+1)2=k(k+1)(2k+1)6+(k+1)2=k(k+1)(2k+1)+6(k+1)26=(k+1)[k(2k+1)+6(k+1)]6=(k+1)(2k2+7k+6)6=(k+1)(2k+3)(k+2)6=n(n+1)(2n+1)6\begin{aligned} & 1^2 + 2^2 + 3^2 + \cdots + (n - 1)^2 + n^2 \\ =& 1^2 + 2^2 + 3^2 + \cdots + k^2 + (k + 1)^2 \\ =& \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 \\ =& \frac{k(k + 1)(2k + 1) + 6(k + 1)^2}{6} \\ =& \frac{(k + 1)[k(2k + 1) + 6(k + 1)]}{6} \\ =& \frac{(k + 1)(2k^2 + 7k + 6)}{6} \\ =& \frac{(k + 1)(2k + 3)(k + 2)}{6} \\ =& \frac{n(n + 1)(2n + 1)}{6} \\ \end{aligned}

故公式成立。证毕。

Lucas 定理

对于质数 pp,有:

(nm) mod p=(n/pm/p)(n mod pm mod p) mod p\binom{n}{m} \bmod p = \binom{\lfloor n / p \rfloor}{\lfloor m / p \rfloor} \cdot \binom{n \bmod p}{m \bmod p} \bmod p

代码

完整代码请在 GitSB 上查看。

int lucas(int n, int m, int p) {
    if (!m) return 1;
    return static_cast<long long>(C(n % p, m % p, p)) * lucas(n / p, m / p, p) % p;
}

Catalan 数(卡特兰数)

定义

Catn={1(n{1,2})i=1nCati1Catni(n2,nN)\mathit{Cat}_n = \begin{cases} 1 & (n \in \{1, 2\}) \\ \sum_{i = 1}^{n} \mathit{Cat}_{i - 1} \cdot \mathit{Cat}_{n - i} & (n \geq 2, n \in \N^*) \\ \end{cases}

递推定义:

Catn=4n2n+1Catn1\mathit{Cat}_n = \frac{4n - 2}{n + 1} \mathit{Cat}_{n - 1}

通项公式:

Catn=(2nn)n+1 (n2,nN)\mathit{Cat}_n = \frac{\binom{2n}{n}}{n + 1} ~~~ (n \geq 2, n \in \N^*)

组合意义

  1. 给定 nn00nn11,他们按照某种顺序排成一个长度为 2n2n 的序列,满足任意前缀中 00 的个数都不少于 11 的个数的序列的数量可以记作 Catn\mathit{Cat}_n
  2. 一个栈的进栈序列为 1,2,3,,n1, 2, 3, \dots, n,不同的出栈序列的方案数;
  3. nn 个节点可以构造的二叉树数目;
  4. 在圆上选择 2n2n 个点,将这些点成对连接起来使得所得到的 nn 条线段不相交的方法数;
  5. 等等。

参考资料

  1. 0x36 组合计数,《算法竞赛进阶指南》(ISBN 978-7-83009-313-6,河南电子音像出版社),李煜东,2019 年 5 月第 5 次修订版。
  2. 排列组合,OI Wiki,2022 年 7 月 17 日。
  3. 卡特兰数,OI Wiki,2022 年 2 月 25 日。
  4. 组合数学,石家庄市第二中学信息学竞赛集训,张闰清,2022 年 1 月 19 日。