排列组合

前言

排列组合计算公式推导及代码实现。

加法原理、乘法原理

分类计数原理：完成一件事情，存在$n$类方法，第1类有$m_1$种方式，第2类有$m_2$种方式，…，第$n$类有$m_n$种方式，则完成此事共有$N = m_1 + m_2 + … + m_n$种不同方法。

分步计数原理：若完成某事需经过$n$个步骤，第1步有$m_1$种方法，第2步有$m_2$种方法，…，第$n$步有$m_n$种方法，则总共有$N = m_1 \times m_2 \times \cdots \times m_n$种不同方法。

区别：分类计数原理是加法规则，各类方法数相加求和；分步计数原理是乘法规则，各步骤方法数相乘得总数。

排列（Arrangement）

排列数

从$n$个不同元素中选取$m(m \leq n)$个元素的所有不同排列的个数，叫做从$n$个不同元素中选取$m$个元素的排列数，记作$\mathrm{A}_n^m$。

排列数公式

$$\mathrm{A}_n^m = n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!}, \quad n, m \in \mathbb{N}^*, m \leq n$$

推导：从$n$个不同元素中选取$m$个元素进行排序，按计数原理分布进行，取第一个有$n$种取法，取第二个有$n-1$种取法…取第$m$个有$n-m+1$种取法，根据分步乘法原理推导出上式。

排列数性质

• $\mathrm{A}_n^m = n\mathrm{A}_{n-1}^{m-1}$：为“某特定位置”先安排，再安排其余位置。
• $\mathrm{A}_n^m = m\mathrm{A}_{n-1}^{m-1} + \mathrm{A}_{n-1}^m$：含特定元素的排列有$m\mathrm{A}_{n-1}^{m-1}$种，不含特定元素的排列有$\mathrm{A}_{n-1}^m$种。

组合（Combination）

组合数

从$n$个不同元素中选取$m$（$m \leq n$）个元素的所有不同组合的数目，称为从$n$个不同元素中取出$m$个元素的组合数，用符号$\mathrm{C}_n^m$表示。

组合数公式

$$\mathrm{C}_n^m=\frac{\mathrm{A}_n^m}{\mathrm{A}_m^m}=\frac{n(n-1)(n-2)\cdots(n-m+1)}{m!}=\frac{n!}{m!(n-m)!},\quad n,m\in \mathbb{N}^*,m\leq n$$ $$\mathrm{C}_n^0=\mathrm{C}_n^n=1$$

证明：通过排列与组合的关系以及排列公式推导证明。

将排列问题$\mathrm{A}_n^m$分为两步：

1. 第一步：从$n$个球中抽取$m$个，不考虑顺序，即组合问题$\mathrm{C}_n^m$；

2. 第二步：将抽出的$m$个球排序，即全排列$\mathrm{A}_m^m$。

依据乘法原理，$\mathrm{A}_n^m=\mathrm{C}_n^m \mathrm{A}_m^m$，因此

$$\mathrm{C}_n^m=\frac{\mathrm{A}_n^m}{\mathrm{A}_m^m}=\frac{n(n-1)(n-2)\cdots(n-m+1)}{m!}=\frac{n!}{m!(n-m)!}$$

组合数的性质

• $\mathrm{C}_n^m = \mathrm{C}_n^{n-m}$：反转组合，未选的变选，选了的变未选，组合数相同。
• 递推公式$\mathrm{C}_n^m=\mathrm{C}_{n-1}^m+\mathrm{C}_{n-1}^{m-1}$：含特定元素组合数为$\mathrm{C}_{n-1}^{m-1}$，不含特定元素组合数为$\mathrm{C}_{n-1}^m$。

示例
令（$n=5$），($m=2$)。

从1，2，3，4，5中取出2个元素的组合$\mathrm{C}_n^m$：

12 13 14 15 23 24 25 34 35 45

这些组合要么含”1”，要么不含。

• 含”1”的组合：12 13 14 15 → 挖去”1”得2 3 4 5 → 等价于从2，3，4，5中取出1个元素的组合。（此处m-1为1）
• 不含”1”的组合：23 24 25 34 35 45 → 等价于从2，3，4，5中取出2个元素的组合。（此处m为2）

总方案数是上述两种情况的和，即$\mathrm{C}_n^m=\mathrm{C}_{n-1}^m+\mathrm{C}_{n-1}^{m-1}$。

组合数求和公式

$$\sum_{i=0}^{n} \mathrm{C}_n^i=2^n$$

直观理解：从$n$个球中抽取0到$n$个球的组合数之和。

严谨证明可采用数学归纳法：

1. 当$n=1$，$\mathrm{C}_1^0+\mathrm{C}_1^1=2=2$成立。
2. 假设$n=k$时公式成立，$\sum_{i=0}^{k} \mathrm{C}_k^i=2^n$，则$n=k+1$时亦成立。
3. 由1、2归纳得公式对所有$n\in \mathbb{N}^*$成立。

或用二项式定理简证：

$$(a+b)^n=\sum_{k=0}^{n}\mathrm{C}_n^k a^{n-k}b^k$$

设$a=b=1$，

$$\sum_{i=0}^{n} \mathrm{C}_n^i=2^n$$

相关公式

由$\mathrm{C}_n^m = \mathrm{C}_n^{n-m}$推导：

$$\mathrm{C}_n^0 + \mathrm{C}_n^2 + \mathrm{C}_n^4 + ... = \mathrm{C}_n^1 + \mathrm{C}_n^3 + \mathrm{C}_n^5 + ... =2^{n-1}$$

Java：组合求和

// author: SilenceZheng66
public long factorialWithRecursion(long n) {
    if (n == 0 || n == 1) return 1;
    return n * factorialWithRecursion(n - 1);
}

public long combination(long n, long m){
    long numerator = factorialWithRecursion(n);
    long denominator1 = factorialWithRecursion(m);
    long denominator2 = factorialWithRecursion(n-m);
    return numerator/(denominator1*denominator2);
}

拓展：组合数的加权求和公式

$$\sum_{i=0}^{n} i \binom{n}{i} = n \cdot 2^{n-1}$$

通常被称为 组合数的加权求和公式 或者 组合数的加权和公式。这个公式用于计算组合数 $\binom{n}{i}$ 与下标 $i$ 的乘积之和。

相关概念

• 二项式系数：$\binom{n}{i}$ 是从 $n$ 个元素中选择 $i$ 个元素的不同方式的数量。
• 二项式定理：$\sum_{i=0}^{n} \binom{n}{i} = 2^n$，表示所有二项式系数的和等于 $2^n$。

证明

1. 简化求和：从 $i=1$ 开始求和，因为 $i=0$ 时 $i \binom{n}{i} = 0$。
2. 利用组合数性质：$i \binom{n}{i} = n \binom{n-1}{i-1}$。
3. 改变求和变量：令 $j = i-1$，则 $i = j + 1$。
4. 利用二项式定理：$\sum_{j=0}^{n-1} \binom{n-1}{j} = 2^{n-1}$。

最终得到公式：

$$\sum_{i=0}^{n} i \binom{n}{i} = n \cdot 2^{n-1}$$

这个公式是组合数学中的一个重要结论，有助于快速计算组合数的加权求和。

参考文献

[1] https://www.cnblogs.com/1024th/p/10623541.html

赏

谢谢打赏哟！

支付宝

微信