组合数学

INFO

若无特殊说明，本章涉及的变量皆为正整数。

简介

排列：从 $n$ 个元素中取出 $m$ 个，按一定顺序排列；
组合：从 $n$ 个元素中取出 $m$ 个，不计排列顺序。

加法原理

一算法有 $n$ 种方式，第 $i$ 种方式有 $a_{i}$ 种方法，该算法共有 $\sum_{i = 1}^{n} a_{i}$ 种实现方法。

EXAMPLE

从 $A$ 地到 $B$ 地有爬行、骑车、飞行三种方式，可以任选一个。而爬行、骑车、飞行分别有 $a_{1}, a_{2}, a_{3}$ 种方法，那么 $A \to B$ 共有 $a_{1} + a_{2} + a_{3}$ 种方法。

乘法原理

一算法有 $n$ 个步骤，第 $i$ 个步骤有 $a_{i}$ 种方法，该算法共有 $\prod_{i = 1}^{n} a_{i}$ 种实现方法。

EXAMPLE

从 $A$ 地到 $B$ 地必须先爬行到车站，再骑车到机场，最后飞行到北京，而爬行、骑车、飞行分别有 $a_{1}, a_{2}, a_{3}$ 种方法，那么 $A \to B$ 共有 $a_{1} \cdot a_{2} \cdot a_{3}$ 种方法。

排列数

从 $n$ 个元素中取出 $m$ 个，按一定顺序排列的方案数，用符号 $A_{n}^{m}$ 表示。

A_{n}^{m} = n (n - 1) (n - 2) \dots (n - m + 1) = \frac{n!}{(n - m)!}

$n = m$ 时的排列称为全排列， $A_{n}^{n} = n!$ 。

组合数

从 $n$ 个元素中取出 $m$ 个，不计排列顺序的方案数，用符号 $C_{n}^{m}$ 或 $(\binom{n}{m})$ 表示。

(\binom{n}{m}) = \frac{A_{n}^{m}}{m!} = \frac{n!}{m! (n - m)!}

特别地，当 $m > n$ 时， $A_{n}^{m} = C_{n}^{m} = 0$ 。

互补性

(\binom{n}{m}) = (\binom{n}{n - m})

证

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

帕斯卡法则

(\binom{n}{m}) = (\binom{n - 1}{m}) + (\binom{n - 1}{m - 1})

证

\begin{aligned} (\binom{n - 1}{m}) = \frac{(n - 1)!}{m! (n - m - 1)!} = \frac{1}{m} \cdot \frac{(n - 1)!}{(m - 1)! (n - m - 1)!} \\ (\binom{n - 1}{m - 1}) = \frac{(n - 1)!}{(m - 1)! (n - m)!} = \frac{1}{n - m} \cdot \frac{(n - 1)!}{(m - 1)! (n - m - 1)!} \end{aligned}

\begin{aligned} (\binom{n - 1}{m}) + (\binom{n - 1}{m - 1}) & = (\frac{1}{m} + \frac{1}{n - m}) \cdot \frac{(n - 1)!}{(m - 1)! (n - m - 1)!} \\ = \frac{n}{m (n - m)} \cdot \frac{(n - 1)!}{(m - 1)! (n - m - 1)!} \\ = \frac{n!}{m! (n - m)!} \\ = (\binom{n}{m}) \end{aligned}

同余

数值分析

多项式

圆锥曲线

组合数学

简介

加法原理

乘法原理

排列数

组合数

互补性

帕斯卡法则

组合数学

简介 ​

加法原理 ​

乘法原理 ​

排列数 ​

组合数 ​

互补性 ​

帕斯卡法则 ​

简介

加法原理

乘法原理

排列数

组合数

互补性

帕斯卡法则