【数学】组合数学与计数

文章相关

写在前面

感谢 caq 的奇奇怪怪的组合数学笔记，实在看不下去了！

文中如无特殊说明，只有在出现 (A_{n}^{m}) 的式子中，组合数才使用 (C_{n}^{m})，其余一律用 (dbinom{n}{m})。

updates

暂无

概念

计算式会在正文给出。

排列

从 (n) 个数中选择 (m) 个数，与排列顺序有关的方案数被称为 (n) 排列 (m)，记作 (A_{n}^{m})。

全排列

特别的，当 (n = m) 时，(A_{n}^{m})，被称为 (n) 或 (m) 的全排列。

组合

从 (n) 个数中选择 (m) 个数，只与选择的数有关的方案数被称为 (n) 选 (m)，记作 (dbinom{n}{m}) 或 (C_{n}^{m})。

实际应用中，组合的应用范围远远比排列要广。排列经常只被使用全排列这一种形式来辅助组合的计算。

正文

计算式

组合：

[inom{n}{m} = frac{n!}{m!(n - m)!} ]

排列：

[A_{n}^{m} = frac{n!}{(n - m)!} ]

因此那么显然有：

全排列：

[A_{n}^{n} = n! ]

排列与组合的关系：

[A_{n}^{m} = C_{n}^{m} imes A_{m}^{m} ]

接下来我们把目光重点放在组合上。

组合数计算式

计算式

下面提供四种计算组合数的计算式。

[inom{n}{m} = frac{n!}{m!(n - m)!} ag{1} ]

[inom{n}{m} = inom{n - 1}{m - 1} + inom{n - 1}{m} ag{2} ]

[inom{n}{m} = frac{n}{m}inom{n - 1}{m - 1} ag{3} ]

[inom{n}{m} mod p = inom{n mod p}{m mod p}inom{lfloordfrac{n}{p} floor}{lfloordfrac{m}{p} floor} mod p(p in mathbb P)( ext{Lucas 定理}) ag{4} ]

证明

待填。

实现

第一个，预处理出阶乘即可。

如果要求在取模意义下，分母部分可以预处理阶乘的逆元。

预处理时，只需计算出最大可能的 (n) 的阶乘的逆元，然后倒推即可。

复杂度是 (O(n)) 的，一般用于计算 (n, m le 10^6) 范围内的组合数，是很有用的组合数计算方式。

具体实现可以参考我的 这篇题解。

同时，这个方法也可以用来预处理一整个数列的乘法逆元。不难推导，读者可以自行思考一下。

第二个，是组合数的递推式。

如果把组合数的 (n,m) 较小的答案算出来，不难发现就是个“杨辉三角”。

因此就可以递推了。

这个方法的时空复杂度都是 (mathcal O(n^2)) 的，不如第一个优秀，这种方法能实现的，第一种方法都能代替。

第三个，是组合数的另一种计算式。

这种方法把直接用组合数计算式 (dfrac{n!}{m!(n - m)!}) 分子中的 (n!)、分母中的 (m!) 拆开来，成为：

[dfrac{n}{m}cdotdfrac{(n - 1)!}{(m - 1)![(n - 1) - (m - 1)]!} ]

即

[dfrac{n}{m}dbinom{n - 1}{m - 1} ]

我们知道，当 (m = 0) 时，无论 (n) 为何值， (dbinom{n}{m}) 恒为 (1)。

因此，这种方法可以一直迭代下去，直到表示到 (m = 1)。

常用于 (n) 巨大（一般在 (10^9) 级别），而 (m) 较小（一般在 (10^5) 级别）的时候组合数的计算。

实现时可以预处理 (1) 到 (m) 的逆元。

第四种，待填。