第二章 排列组合

1. 基本计数原理

设集合S的 一个划分 即为S的子集的集合，使得S的每一个元素恰好是这些子集之一的元素：

子集称为该划分的部分。

集合S的元素个数表示为, 又称之为S的大小。

加法原理

设集合S划分为部分 。则S的元素个数可以通过找出它的每一个划分的个数来确定，我们把这些数相加，得到：

如果集合可以重叠，那么要使用一个更深刻的原理（容斥原理）来计数S中的元素个数。

用选择的术语叙述加法原理的形式为 ：如果有p种方法能够从一堆中选择一个物体，而有q种方法能从另一堆中选择一个物体，那么从这两堆中选择一个物体的方法共有p+q种。这种形式的加法原理可以很容易推广到多堆。

乘法原理

令S是元素的有序对(a, b)的集合，其中一个元素a来自大小为p的一个集合，而对a的每个选择，元素b存在着q种选择。于是，S的大小为p × q :

乘法原理的第二种形式： 如果一项任务有p项结果，而不论第一项任务的结果如何，第二项任务都有q个结果，那么，这两个任务连续执行就有p×q个结果。

注意这里两项任务的关系不能存在依赖的情况，如果出现，需要交换次序，优先选择约束性最强的选择。

减法原理

令A是一个集合，而U是包含A的更大的集合。设

是A在U中的补。那么A中的元素个数|A|由下列法则给出：

在应用减法原理中，集合U通常是包括讨论中所有元素的某个自然的集合（即所谓的泛集）。使用减法原理只有当对U中的元素计数和对中元素计数比对A中元素计数容易时才有意义。

除法原理

令S是一个有限集，它以下述方式被划分成k部分，每一部分包含相同数目的元素。此时，划分中的部分的数目由下述公式给出：

(在一个部分中的元素个数)

于是，如果我们知道S中元素个数以及各部分所含元素的相同的个数，则可以确定部分的数目。

计数问题的分类

多重集：集合有一条重要原则，即集合中的元素都是不可重复的，而多重集则没有这一限制

多数计数问题都可以分类为一下形式：

1. 计数对象的有序排列的个数或者是有序选择的个数

• 任何对象都不重复（这里重复是指排列过后不能再次排列或者拿过的东西不能再拿一遍）
• 允许对象重复（可以再次排列或拿取，但可能有限制）

2. 计数对象的无序组合的个数或者是无序选择的个数

• 任何对象都不重复（同上）
• 允许对象重复（同上）

如果我们允许对象重复，可以变换一种思维方式，将集合扩展为可重集，这样从可重集中选择对象，选择出来的结果正好对应于集合中对象允许重复的排列组合。

2.排列与组合

集合的排列

令是正整数。 我们把个元素的集合的一个排列理解为：在n个元素中的取出r个元素的有序摆放的数目。

我们用 表示n个元素集合的r排列的数目。如果。显然，对每一个正整数。n元素集合S的一个n排列被更简单地称为S的一个排列或n个元素的一个排列。于是，集合S的一个排列就是以某种顺序列出S的所有元素。

定理1 ： 对于正整数

定义n!（读作n的阶乘）为 。并约定 。于是我们可以写成：

对于，正好与r = 0时的公式一致。n个元素的排列数为

在上面的排列中我们是把对象排成一条线的，称之为线性排列，或线排列。如果我们更看重对象之间的相对位置而不是绝对位置时，就有了圆排列，或循环排列的概念。在两个圆排列中，通过旋转能够重合的，我们认为这是同一个排列。下面给出正式定义：

从集合个不同元素中，取出r个元素按照某种次序（如逆时针）排成一个圆圈，称这样的排列为圆排列，或循环排列。

定理2 : n个元素的集合的循环r排列的个数由给出。特别的，n个元素的循环排列的个数是 。

在圆排列中，还有一种项链排列，在圆排列中，经翻转能与原来重合的排列视为同一排列。项链排列在圆排列的基础上计算，为圆排列的一半。

例子 用20个不同颜色的念珠串成一条项链，能够做成多少不同的项链？
20个念珠共有20！种不同的排列。由于每条项链都可以旋转而不必改变念珠的排列，项链的数目最多为20！/20=19！。又由于项链不可以翻转过来而念珠的排放未改动，因此项链的总数是19！/2。

下面介绍几个排列中常用的恒等式：

image.png