【暖*墟】 #组合# 多重集的排列与组合

【多重集的排列与组合】

如果S是一个多重集合，那么S的一个r排列，是S中r个对象的一个有序放置。

如果S的对象总数是n(重复对象计数在内)，那么S的n排列也称为S的排列。

例如，如果S=｛2·a，1·b，3·c｝，那么

acbc　　cbcc

都是S的4排列，而

abccca

是S的一个排列。多重集合S没有7排列，因为7>2+1+3=6，即7大于集合S的对象个数。

我们首先计算多重集合S的r排列的个数，其每一个重复数都是无限的。

定理2.4.1　设S是有k种不同类型对象的多重集合，每一个元素都有无限重复数。那么，S的r排列的数目是kr。

证明　在构造S的r排列的过程中，我们可以把第一项选择为k个类型中任意类型的一个对象。

类似地，第二项可以是k个类型中任意类型的一个对象，等等。因为S的所有重复数都是无限的，

所以任意一项的不同选择数量也总是k，它不依赖于前面项的选择。根据乘法原理，r项可以有kr种选择方法。

这个定理的另一种描述是：k个不同对象（每一个对象的供给是无穷的）的r排列数量等于kr。

我们还注意到，如果S的k种不同类型的对象的重复数都至少是r，那么定理也是成立的。

重复数无限的假设是保证我们在构造r排列时不能用尽任何类型的对象的一种简单保证。

例子　最多有4位的三元数的个数是多少？

//一个三元数（ternary numeral）或者三进制数是用3的幂表示一个数而得到的数。

//例如，46=1×33+2×32+0×31+1×30。所以46的三元数是1201。

这个问题的答案是多重集合｛∞·0，∞·1，∞·2｝或多重集合｛4·0，4·1，4·2｝的4排列的个数。

根据定理2.4.1，这个数等于34=81。

现在我们计数有k种不同类型的对象且有有限重复数的多重集合的排列。

定理2.4.2　设S是多重集合，它有k种不同类型的对象，且每一种类型的有限重复数分别是n1，n2，…，nk。

设S的大小为n=n1+n2+…+nk。则S的排列数目等于  

证明　给定多重集合S，它有k种类型对象，比如说a1，a2，…，ak，

且重复数分别是n1，n2，…，nk，对象总数n=n1+n2+…+nk。

我们想要这n个对象的排列数量。可以这样考虑这个问题。

一共有n个位置，而我们想要在每一个位置放置S中的一个对象。

首先，我们确定放置a1的位置。a1的数量是n1，因此必须从n个位置的集合中取出n1个位置的子集。

这样做的方法数是。下一步，要确定放置a2的位置。

此时还剩下n-n1个位置，我们必须从中选取n2个位置来。

这样做的方法数量是。再接下来我们有种方法为a3选择位置。

继续这样做下去，利用乘法原理，我们发现S的排列个数等于

使用定理2.3.1，我们看到上面这个数等于

消去分子分母上的相同因子，上面的数化简成为

例子　词MISSISSIPPI中的字母的排列数是

因为这个数字等于多重集合｛1·M，4·I，4·S，2·P｝的排列数。

如果多重集合S只有两种类型的对象a1，a2，且它们的重复数分别是n1和n2，其中n=n1+n2，

那么按照定理2.4.2，S的排列数是

因此，我们可以把看成是n对象集合的n1子集的数量，

还可以看成是一个有两种类型的对象且它们的重复数分别是n1和n-n1的多重集合的排列个数。

在定理2.4.2中出现的数还有另外一种解释。

它涉及这样一个问题：把一个对象集合划分成指定大小的各个部分，其中这些部分都有指定给它们的标签。

为了理解上面这段话的意思，我们给出下面的例子。

例子　考虑有4个对象的集合｛a,b,c,d｝，把它划分成两个子集，每一个大小为2。

如果这两部分没有做标签，那么有3种不同的划分：

｛a,b｝，｛c,d｝；　｛a,c｝，｛b,d｝；　｛a,d｝，｛b,c｝

现在假设给这些部分做上不同的标签（例如，红色和蓝色）。

那么划分数量增大；实际上，有6个划分，因为我们要用两种方法给划分的每一部分标上红色和蓝色。

例如，对于上面的划分{a,b｝，｛c,d｝，有   红盒｛a,b｝，蓝盒｛c,d｝   和     蓝盒｛a,b }，红盒｛c,d｝。

在一般情形下，我们可以用B1，B2，…，Bk(看成是颜色1，颜色2，…，颜色k)标记这些部分，

并把这些部分想象成一些盒子。这时，下面定理成立。

定理2.4.3　设n是正整数，并设n1,n2,…，nk是正整数且n=n1+n2+…+nk。

把n对象集合划分成k个标有标签的盒子，且第k个盒子含有nk个对象，这样的划分方法数等于

如果这些盒子没有标签，且n1=n2=…=nk，那么划分数等于：

证明　这一证明是乘法原理的直接应用。我们必须在满足大小限制的情况下选取哪些对象放进哪些盒子。

首先，我们选取n1个对象放入第1个盒子，然后从剩下的n-n1个对象中选取n2个对象放入第2个盒子，

然后从剩余的n-n1-n2个对象中选取n3个对象放入第3个盒子，…，最后将n-n1-…-nk-1=nk个对象放入第k个盒子。

由乘法原理，进行这些选择的方法数为

同定理2.4.2的证明一样，上面这个数等于

如果这些盒子没有标签，且n1=n2=…=nk，那么这个结果就必须除以k!。

这是因为，同前面的例子一样，对于把这些对象分配到k个没有标签的盒子里的每一种方法，

都有k！种方法给这些盒子标上标签1,2，…，k。

因此，使用除法原理，我们发现没有标签盒子的划分的个数是

这类例子考虑的是国际象棋棋盘上的非攻击型车。为免除读者担心本书要求事先具有国际象棋的知识，

我们在这里给出唯一需要知道的国际象棋知识：两个车能够互相攻击当且仅当它们位于棋盘的同一行或同一列上。

除此之外，无需知道国际象棋的其他知识(且这些知识也于事无补)。

因此，棋盘上非攻击型车的集合指的就是叫做“车”的那些棋子的集合，

它们占据着棋盘上的一些方格，并且没有两个车位于同一行或同一列上。

例子　有多少种方法在8×8棋盘上放置8个非攻击型车?

在8×8棋盘上放置8个非攻击型车的例子如下：

我们给棋盘上每一个方格赋予一个坐标对（i,j）。整数i指明这个方格所处的行，

而整数j指明这个方49格所处的列。因此i，j都是1和8之间的整数。

因为这个棋盘是8×8的并且有8个不能相互攻击的车放在棋盘上，所以每一列一定只存在一个车。

因此，这些车占据8个方格，其坐标是

(1，j1)，(2，j2)，…，(8，j8)

但是，每一列上也必须存在一个车，这使得j1，j2，…，j8中没有两个是相等的。更准确地说，

j1，j2，…，j8

必须是｛1，2，…，8｝的一个排列。反过来，如果j1，j2，…，j8是｛1，2，…，8｝的一个排列，

那么把车放在坐标是(1，j1)，(2，j2)，…，(8，j8)的各个方格上，就得到棋盘上的8个非攻击型车。

因此，8×8棋盘上8个非攻击型车的集合与｛1，2，…，8｝的排列之间存在一一对应，

因为｛1，2，…，8｝有8!个排列，所以，把8个车放到8×8棋盘上使得它们具有非攻击性的方法也有8!个。

在上面讨论中，我们实际上已经间接假设这些车彼此没有区别，

即它们构成只有一种类型的8个对象的一个多重集合。因此，唯一重要的是车要占据哪些方格。

如果我们有8个不同的车，比如，用8种不同的颜色分别给8个车着色，

那么还要考虑在8个被占据的每一个方格里放的是哪个车。假设有8个不同颜色的车。

在决定哪8个方格要被这些车占据后(8!种可能)，我们现在还要决定在每个所占据的方格上的车是什么颜色的?

观察从第一行到第8行的这些车时我们看到8种颜色的一个排列。

因此，决定了哪8个方格要被这些车占据之后(8!种可能)，就必须确定8种颜色的哪个排列(8!种排列)。

于是，在8×8棋盘上具有8种不同颜色的8个非攻击型车的放置方法数等于

8!8!=(8!)2

现在假设不是有8个不颜色的车，而是有1个红(R)车、3个蓝(B)车和4个黄(Y)车，

而且还假设同颜色的车彼此没有区别1。现在，当我们从第1行到第8行观察这些车时，看到多重集合

｛1·R，3·B，4·Y｝

的一个颜色排列。根据定理2.4.2，这个多重集合的排列个数等于

因此，在8×8棋盘上放置1个红车、3个蓝车和4个黄车并使它们彼此不能互相攻击的方法数等于

前面例子中的推理具有相当的普遍性，直接导致下面的定理。

定理2.4.4　有k种颜色共n个车，第一种颜色有n1个，第二种颜色有n2个，…，第k种颜色有nk个。

把这些车放置在一个n×n的棋盘上使得车之间不能相互攻击的方法数等于

注意，如果这些车都有不同的颜色（即k=n,ni=1），那么上面的公式给出的答案就是（n！）2。

如果这些车的颜色都相同（即k=1,n1=n），那么上面的公式给出的答案就是n！。

设S是n元素多重集合，其重复数分别是n1,n2，…，nk，且n=n1+n2+…+nk。

定理2.4.2给出了求S的n排列数的简单公式。如果r<n，一般来说，没有求S的r排列数的简单公式。

尽管如此，可以利用生成函数技术进行求解，我们将在第7章对此加以讨论。

在某些情况下，还是可以像下面的例子那样进行论证。

例子　考虑3种类型9个对象的多重集合S=｛3·a，2·b，4·c｝。求S的8排列的个数。

S的8排列可以被划分成3个部分：

（ⅰ）｛2·a，2·b，4·c｝的8排列数，有

（ⅱ）｛3·a，1·b，4·c｝的8排列数，有

（ⅲ）｛3·a，2·b，3·c｝的8排列数，有

因此，S的8排列的个数是

420+280+560=1260