排列

什么是排列

从 $n$ 个不同元素中选取 $m$ 个元素 $(m\leqslant n)$ ，按照一定的顺序排成一列，称为从 $n$ 个元素中取出 $m$ 个元素的一个排列(permutation)，（换句话说，这 $m$ 个元素对顺序是敏感的，例如 $ab$ 和 $ba$ 是两个不同的排列）可以记作 $P^m_n$ 或 $A^m_n$ 。而当 $m=n$ 时，这个排列被称为全排列(all permutation)，记为 $P_n$ 或 $A_n$ ，也就是 $n$ 的阶乘，记为 $n!$ 。

计算排列 $P^m_n$ 的公式： $P^m_n=\frac{n!}{(n-m)!}=n\times (n-1)\times (n-2)\times\cdots\times(n-m+1)$

选排列

上述的通用排列计算公式就是用于计算选排列的，指从 $n$ 个不同元素中取出 $m$ 个元素，且 $m<n$ ，这 $m$ 个元素按顺序排列。

错位排列

一个有 $n$ 个元素的排列，如果一个排列中的所有元素都不在其原来位置上，那么就称这样的排列是原排列的一个错位排列。

可以使用递推获取所有错位排列的种类。例如，将 $n$ 个编号元素放入 $n$ 个位置，编号元素与位置是一一对应的，编号元素和位置不对应的情况总数用 $D(n)$ ，$D(n-1)$ 表示 $n-1$ 个编号元素放入 $n-1$ 个编号位置的不对应情况总数，以此类推，计算步骤：

• 把编号为 $n$ 的元素放入一个位置 $k$ ，共有 $n-1$ 种方法。
• 下面为 $k$ 寻找可能的位置，此时有两种情况：
  • 把为编号 $k$ 的元素放入位置 $n$ 中，此时剩下的 $n-2$ 个元素就有 $D(n-2)$ 种情况；
  • 不放入，此时对于这 $n-1$ 个元素则有 $D(n-1)$ 种情况。
• 从步骤1、2中可知， $D(n)=(n-1)[D(n-2)+D(n-1)]$ 。

在上面三个步骤的基础之上，可以推导出其通项公式： $n=1$ 时，$D(1)=0$;$n=2$ 时，$D(2)=1$ 。

假设 $D(n)=n!M(n)$ ，那么 $M(1)=0$ ，$M(2)=\frac{1}{2}$ 。当 $n\geqslant 3$ 时，将 $n!M(n)$ 带入步骤3中，可以推出下列算式：

$n!M(n)=(n-1)[(n-2)!M(n-2)+(n-1)!M(n-1)]$ $=(n-1)!M(n-2)+n!M(n-1)-(n-1)!M(n-1)$ $nM(n)=nM(n)=M(n-2)+nM(n-1)-M(n-1)$ $nM(n)=nM(n)-nM(n-1)=M(n-2)-M(n-1)$ $M(n)-M(n-1)=-\frac{1}{n}[M(n-1)-M(n-2)]$ $=-\frac{1}{n}(-\frac{1}{n-1})(-\frac{1}{n-2})\cdots(-\frac{1}{3})(M(2)-M(1))$ $=(-1)^n\frac{1}{n!}$ $M(n)=(-1)^n\frac{1}{n!}+M(n-1)$ $=(-1)^n\frac{1}{n!}+(-1)^{n-1}\frac{1}{(n-1)!}+\cdots+(-1)^2\frac{1}{2!}$ $D(n)=n!M(n)=n![(-1)^2\frac{1}{2!}+(-1)^3\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}]$

循环排列

又称为圆排列或环排列，指从 $n$ 个元素中取出 $m$ 个元素，将这 $m$ 个元素首尾相连，排列成一个环形 $(1\leqslant m\leqslant n)$ 。当且仅当所取元素的个数相同、元素的取法、元素在环上的排列顺序一致时，才能判断两个循环排列相同。

在全排列 $(m=n)$ 的情况下，直线排列可能的情况数为 $n!$ ，由于围成一圈，循环排列可能的情况数为 $(n-1)!$ 。

循环排列公式为： $\frac{n!}{(n-m)!\times m}$

全排列情况下，上述公式变为： $\frac{n!}{0!\times n}=(n-1)!$

组合

什么是组合

从 $n$ 元素中不考虑顺序地选取 $m$ 元素 $(m\leqslant n)$ ，称为从 $n$ 个不同元素中取出的一个有 $m$ 个元素的组合，用数学符号 $C^m_n$ 表示，公式如下：

$C^m_n=\frac{n\times(n-1)\times(n-2)\times\cdots\times(n-m+1)}{m\times(m-1)\times(m-2)\times\cdots\times1}$

与排列不同的是，排列的区分是对顺序有要求的，而组合的区分对顺序是没有要求的，也就是说，只要两个组合的内容是完全相同的，不管它们的顺序是否完全相同，也判定这两个组合是相同的。例如：$ab$ 和 $ba$ 被认为是两种排列，但被认为是同一个组合。

在计算组合问题时，常用的有以下 $8$ 个恒等式：

• $C^m_n=C^{n-m}_n$

• $C^m_n=C^{m-1}_{n-1}+C^m_{n-1}$

• $C^n_n+C^n_{n+1}+C^n_{n+2}+\cdots+C^n_{n+r}=C^{n+1}_{n+r+1}$

• $C^0_n+C^1_n+C^2_n+\cdots+C^n_n=2^n$

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

• $kC^k_n=nC^{k-1}_{n-1}$

• $C^r_nC^m_r=C^m_nC^{r-m}_{n-m}$

• $C^0_n-C^1_n+C^2_n+\cdots+(-1)^nC^n_n=0$

重复组合

上述的组合计算公式仅限于不重复的组合方式，如果在组合的基础上允许重复，则计算公式变为：

$C^m_{n+m-1}=\frac{(n+m-1)\times(n+m-2)\times\cdots\times[(n+m-1)-m+1]}{m\times(m-1)\times(m-2)\times\cdots\times1}$

不相邻组合

不相邻组合是指从 $n$ 个元素中取出 $m$ 个元素，在这 $m$ 元素中，任意的两个元素都是不相邻的，例如， $1,4,7,9$ 就是一个不相邻组合。计算组合数的公式为 $C^m_{n-m+1}$ 。

计数原理

什么是计数原理

计数原理是上述排列、组合在数学中的应用，其中加法原理和乘法原理是计算计数问题时最基本、最重要的方法，被称为基本计数原理。

分类加法计数原理

加法原理是指在完成一个目标时可以用 $n$ 中不同的方法，而每种方法中又包含 $m_i$ 个不同的分支，那么完成这个目标的方法数量共有 $N$ 种：

$N=\sum_{i=1}^nm_i=m_1+m_2+\cdots+m_n$

例题：

【题目】

从 甲地 到 乙地 可以乘坐高铁、飞机或轮船，一天中高铁有3列，飞机有2班，轮船有6艘，那么一天中共有几种方法从 甲地 前往 乙地 ？

【解法】

套公式，$3+2+6=11$ 种方法。

分步乘法计数原理

乘法原理是指完成一个目标时需要分成 $n$ 个步骤，第 $i$ 个步骤时有 $m_i$ ，那么完成这个目标共有 $N$ 种不同方法：

$N=\prod_{i=1}^nm^i=m_1\times m_2\times\cdots\times m_n$

例题：

【题目】

如图，从 甲地 到 乙地 有3条路，从 乙地 到 丙地 有2条路，从 丙地 到 丁地 有5条路，求从 *甲地 *到 丁地 有几种方法？

【解法】

本题想要从 甲地 到 丁地 ，必然会经过 乙地 和 丙地 ，适用乘法原理，有 $3\times2\times5$ 种方法。

两种计数原理的区别

	加法原理	乘法原理
区别	完成目标共有 $n$ 种方法，每一种都能独立完成，且每一种都是独立的	完成目标共有 $n$ 个步骤，每一个步骤之间是互相关联的，不能缺少一步