最后更新: 2025-01-22 08:57 ● 参与者查看: 17 次纠错分享参与项目词条搜索

集合的排列

排列
定义6．1 从 $n$ 个元素的集合 $S$ 中有序选取的 $r$ 个元素称为 $S$ 的一个 $r$－排列，不同的排列总数记为 $p(n, r)$ 。若 $r=n$ ，则称此排列为全排列。当 $r>n$ ，规定 $p(n, r)=0$ 。

定理 6.3 对 $r \leqslant n$ 的正整数 $n, r$ ，有

$$
p(n, r)=n(n-1) \cdots(n-r+1)
$$

证明：从集合 $S$ 中选取第一个元素有 $n$ 种可能，再选取第二个元素有 $n-1$ 种可能，$\cdots \cdots$ ，依次类推，选取第 $r$ 个元素有 $n-r+1$ 种可能，由乘法原理得，$p(n, r)=n(n-1) \cdots(n-r+1)$ 。

令 $n!=n \times(n-1) \times \cdots \times 2 \times 1$ ，且规定 $0!=1$ ，则：$p(n, r)=n!/(n-r)!$ 。
例 6.2 从 $n$ 个编号的不同球中选取 $r(0 \leqslant r \leqslant n)$ 个排成一行，则可能出现的不同行有 $p(n$ ， $r$ ）个。这个属于有序选取放球问题。

例 6.3 某产品加工需要一，二，三，四，五共 5 道工序，则安排这些加工工序共有 $p(5,5)=120$ 种方法。若工序一必须先加工，则有 $p(4,4)=24$ 种方法。若工序三不能放在最后加工，此时的安排加工工序的方法数可这样来求：由于工序三的加工安排有 $p(4,1)=4$ 种。而其余的工序安排共有 $p(4,4)=24$ 种，由乘法原理知共有 $4 \times 24=96$种方法。
例 6.4 在上例中，（1）若规定工序四必须紧跟在工序三的后面，有多少种安排方法？
（2）若规定工序二必须在工序五的前面，有多少种安排方法？
解：（1）把工序三，工序四看成一个工序，因此有共 $p(4,4)=24$ 种方法。
（2）把工序二放在工序五的前面，有四种情况。
（1）工序二，工序五在一起，有 24 种。
（2）工序二，工序五中间间隔一道工序，则有 $p(3,3) \times p(3,1)=18$ 种。
（3）工序二，工序五中间间隔两道工序，则有 $p(2,2) \times p(3,2)=12$ 种。
（4）工序二，工序五中间间隔三道工序，则有 $p(1,1) \times p(3,3)=6$ 种。
由加法原理知，要使工序二在工序五之前，安排加工工序的方法共有 60 种。
环排列
前面讨论的排列确切地说应该称为线形排列，下面将介绍环排列。
定义6．2 从有限集合 $A=\left\{a_1, a_2, \cdots, a_n\right\}$ 上选取 $r$ 个元素排成一个环形，这样的排列称为 $A$的一个 $r$－环排列。

例如排列 54371 与排列 43715 是不同的排列，但首尾相接成环时就是同一个环排列了，因此从集合中选取元素排成一个环，其排列数将比线形排列数少。

定理 6.4 由 $n$ 个元素组成的集合 $A$ 的 $r$－环排列数是

$$
p(n, r) / r
$$

证明：把 $A$ 的所有 $r$－线形排列分成组，使得同组的每个线形排列可以连接成同一个环排列。又因一个 $r$－环排列可产生 $r$ 个 $r$－线形排列，即每组中恰含有 $r$ 个 $r$－线形排列，所以 $A$的所有 $r$－环排列数为 $p(n, r) / r$ 。

当 $r=n$ 时，$A$ 的环排列数为 $p(n, n) / n=(n-1)!$ 。
例6．5（1） 10 个男孩和 5 个女孩站成一排，若没有两个女孩相邻，问有多少种排法？
（2） 10 个男孩和 5 个女孩站成一个圆圈，若没有两个女孩相邻，问有多少种排法？
解：把男孩看成格子的分界，而每两个男孩之间则看成一个空格。
（1） 10 个男孩站成一排的排法有 $p(10,10)$ 种，对于每一种排法有 11 个空位置放置女孩，有 $p(10,5)$ 种放法。由乘法原理得所求排列数是 $p(10,10) \times p(10,5)=(10!\times 11!) / 6!$ 。
（2） 10 个男孩站成一圈的排法实际上就是 10 个元素的环排列数，为 $p(10,10) / 10$ 。而对于每一种排法有 10 个空位置放置女孩，故方法数为 $p(10,5)$ 。由乘法原理得所求排列数是 $(p(10,10) / 10) \times p(10,5)=(10!\times 9!) / 5!$ 。

上一篇：基本计数原理

下一篇：集合元素的组合

本文对您是否有用？有用 (0) 无用 (0)