排列、组合与圆排列

阶乘、排列与组合：乘法原理到除去重复

对正整数 $n$，定义 $n!=n(n-1)\cdots2\cdot1$，约定 $0!=1$。从 $n$ 个不同元素中选出 $m$ 个排成有顺序的一列（$0\le m\le n$），第一位有 $n$ 种，第二位有 $n-1$ 种，依次相乘得

不区分选中元素的顺序时，每个 $m$ 元子集恰被其 $m!$ 种排列重复计算。因此

$m=0$ 时有一个空选择，故排列数与组合数都为 $1$。符号 $P_n^m$ 有时也表示排列数，应先看教材约定；不能把相同字母不同用法混用。

例如从 $5$ 人选出 $2$ 人：不分工有 $\binom52=10$ 种；分别任队长、副队长有 $A_5^2=20$ 种。二者差别在“结果是否包含角色顺序”，不在计算技巧。

允许重复选择与相同元素排列

允许重复选择。 从 $n\ge1$ 种元素中依次选择 $m\ge0$ 次，每次均可选择任一种，且区分选择顺序，则有 $n^m$ 种结果。原因是每一步都有 $n$ 种选择，使用乘法原理即可。$m=0$ 时只有一个空序列。

给定重数的排列。 有 $k$ 种元素，第 $i$ 种有 $r_i$ 个，同种元素不可区分；设 $r_i\ge0$ 且 $r_1+\cdots+r_k=n$。使用全部元素排成一列的不同结果数为

证明。 先给每个元素贴上不同编号，得到 $n!$ 个排列。擦去编号后，同种元素内部的 $r_i!$ 种编号次序产生同一结果。每个最终排列恰有 $\prod_i r_i!$ 个带编号原像，因此除以这个固定重数。

这两个模型的区别在于：前者只规定种类和总长度，后者还规定每一类恰好使用多少个。若每一类的库存有限，允许重复选择公式 $n^m$ 只有在任何长度为 $m$ 的选择都不超库存时才能直接使用；每类库存均至少为 $m$ 是一个充分条件。

计数求和中常约定：对非负整数 $n$，当 $m<0$ 或 $m>n$ 时 $\binom nm=0$。这个约定方便统一公式，不代表能从 $n$ 个元素中实际选出超过 $n$ 个不同元素。