多重集的排列

2024年1月30日发(作者：新款兰德酷路泽lc300)

13.4 多重集的排列设S是一个集合它含有Ri个xiij1 2… m. 且对于不同的ij有xi≠xj

则称S是一个多重集记为Sxi xi xi xi … xj xj xj ……k1·x1 k2·x2 k3·x3… km·xm例如S 2·a1·b3·c2当多重集S中的某个元素的个数为1时则其重复数可以省略。即S2·a1·b3·c2·ab3·c如果S是一个多重集那么S的一个r-排列是S中r个元素的有序排放。如果S的元素总个数是n包括重复元素那么S的n-排列也称为S的排列。对于S2·a1·b3·c3于是acbccbcc均是S的4-排列而abccca是S的一个6-排列因为n r6。注意b b a

b c c c a c均不是S的排列 S 中没有2b个和4个c。同样S中没有7-排列因为S中所能选出的最多元素只能是6个。4定理3.4.1 令S是一个多重集它有k个不同类型的元素每个元素在S中均有重复数并且是无限的。那么S的r-排列的个数为kr。证明:在S的一个r-排列中每一种元素均有r个位置的k种选择因此不同r-排序的个数为kr。例如用数码012…89排8位的电话号码的个数是10×10×……×1010810种10种.....10种5例如最多4位数字的二进制的个数是2416即从多重集·0 ·1中或者是从多重集4·0 4·1中选择4-排列的个数由于只是4位数字我们仅仅需要多重集4·0 4·1就够选择了2×2×2 ×2 24最多4位数字的三进制的个数是3481即在4·0 4·1 4·2选择4-排列的个数3种3种3种3种6定理3.4.2设S是一个多重集有个k不同类型的元素各个元素的重复数分别是:n1n2….nk。设S的大小S n n1n2….nk。则S的所有排列数n-排列等于证明我们注意到S的每个排列包含了S中的每一个元素并且每个元素在排列中的出现次数必须等于它在S中的重复数。给n个元素的每一个指定位置来构造S的排列。.....21knnnn7我们为第1类的n1个指定位置有Cnn1种方法。指定之后我们可以为第2类的n2个项指定位置有Cn-n1n2种方法等等。根据乘法原理排列元素的方法数为32化简后得看的出重复排列的个数少于不重复元素的排列个数这是因为重复排列中有相同的元素相同元素之间交换位置并不会产生新的排列而在不同元素之间交换位置肯定能构成新的排列。从排列数的多少上可以看出区别同一类的相同元素自己的全排列数ni要除掉。0.....21knnnn9例用下列字母可以组成多少个字符串M I S S I S S I P P I因为字母允许重复答案就不再是11而是小于11的某个数其中相同元素交换位置后的排列没有变化。我们来考虑用字母来填充11个空的问题。———————————。对2个字母P有C112种方法来选择位置。一旦P的位置选定有C94种方法来为4个S选择位置。10一旦S的位置选定有C54种方法选择位置来填四个I。一旦这些位置选好剩下一个位置来填M。根据乘法原理排列字母的方法数为种3465545494922例在3个学生中分8本不同的书如果张三得到4本书而李四和王五每人2本书有多少种分法将书以一定的顺序摆放现在考虑4个B2个S和2个M的序列。一个例子为BBBSMBMS每一种这样的序列决定了书的一种分配方法。如上例中的排序张三得到第123和6本书李四得到了第48本书王五得到了第512和第7本书。于是排列BBBBSSMM的方法数等于分配书的方法数。根据定理此数为。如果多重集Sn1·a1 n2·a2n1n2n只有两类型的元素a1和a2它们对应的重复数分别是n1和n2那么按照定理3.4.2集合S的排列数为:11121nnnnnnnnn420224813因此可以把C n n1 看作是n个元素集合的n1-组合数也可以看成是具有两种类型的元素并且它们的重复数分别是n1和n-n1的多重集的排列的个数此时排列与组合类似。例求8×8棋盘上的8个非攻击型车的不同放法数解所谓两个车可以互相攻击当且仅当二车位于棋盘的同一行或同一列上。因此非攻击型车

是指这些车占据着棋盘上的一些方格14但任意两个车都没有位于同一行或同一列上。如图所示a中的任意两个车均为非攻击型b、c中的两个车都属攻击型因为b中的车位于同行c中的车位于同列a中的车既非同行又非同列。车车车车车车车abc15若给8×8棋盘的每个方格指定一对坐标ij其中i指明方格所在的行号j指明方格所在的列号。由于棋盘有8行要使8个车在棋盘上互不攻击每行或列上有且只能有一个车。从而8个车在棋盘上所占方格的坐标为序偶1j12j2…8j8又因在每列均恰有一个车这使得坐标中的j1j2…j8中任意两个都不相等。换言之16j1j2…j8必须是12…8的一个不重复的排列。反过来对12…8的每个排列对应着一组j1j2…j8把8个车按行排有8个排列。再按列排又有8个排列。分放在坐标为1j12j2…8j8的8个方格上就得到棋盘上8个非攻击型车。事实上8×8棋盘上的8个非攻击型车的放置方式与12…8的排列之间形成一双射函数这里认为8个车是相同的。唯一的关键是确定哪些方格可被8个车占据。17若进一步将8个车设为是互不相同的比如有8种不同颜色的车则在确定了8种行方案后对每一种方案还要确定究竟是哪种颜色的车在哪方格中。观察第一行到第八行可以看到8种颜色的一个排列。注意到对8种位置排列的任一种颜色的排列都有8个由乘法原理在8×8棋盘上具有8种不同颜色的8个非攻击型车的放置方案数为:8·88218现再设有1个红R车3个蓝B车4个黄Y车并设同色车无区别。这时对某一放置当从第1行到第8行观察这些车时可视为多重集1·R3·B4·Y的一个8-排列。由定理3.4.2这个多重集的8排列数为8/134。因此在8×8棋盘上放置1个红车3个蓝车4个黄车并使它们互不攻击包括同色车的放置方案数为:431843188219定理3.4.3 有n个车共有k种颜色第i种颜色的车有ni个i12…k。现将这n个车放在n×n的棋盘上使得没有车能够互相攻击的摆放方法数等于: 并且若这n个车均有不同的颜色则方法数为n2若这n个车均属相同的颜色则方法数为n。21221mmnnnnnnnnn20例设S3·a 2·b 4·c求S的8排列的个数。解S的8排列可分为以下三类12·a 2·b 4·c的8排列数目为420422823·a 1·b 4·c的8排列数目为28041382133·a 2·b 3·c的8排列数目为5603238因此S的全部8排列的个数为42 本题中重复次数324限制了排列的数量如果重复数多的话全部8排列的个数会很多。22172221例求26个英文字母的排列中任意两个元音字母都不相邻的方案数。解:21个辅音字母的排列计有21个对其中的任一排列5个元音添入的位置有22个故共有P225种方式由乘法原理26个英文字母的排列中使得元音字母任意两个都不相邻的方案数为:1722233.5 多重集的组合下面我们考虑允许重复的无序选择的计算问题。如果S是一个多重集那么S的r-组合是S中r个元素的一个无序选择。因此S的一个r-组合本身就是一个多重集——S的一个子多重集。如果S有n个元素那么S只有一个n-组合既S自己。如果S有k种不同类型的元素那么S就有k个1-组合。24例如果S2·a 1·b 3·c 那么的3-组合有用穷举法2·a 1·b 2·a 1·c 1·a 1·b 1·c 1·a 2·c 1·b 2·c 3·c在容斥原理章节中我们还要专门讨论。无限重复数多重集的r-组合数例考虑三种书计算机物理历史。假设图书馆中至少每种书有6本。我们选择六本书有多少种方法假设每种书的数量是无限的。25问题是从集合计算机书物理书历史书中无序选择的选择6本书并且允许重复。一种选择方法是由每一类书的已选数量唯一确定一种。例如我们列出一种计算机书物理书历史书 计算机书×3物理书×2历史书×126也可以是计算机书×0物理书×4历史书×2计算机书物理书历史书 六个―‖和两个―‖的每种排序表示了一种选择。于是我们的问题就变化成了从8个可能的位置中为―‖选择两个的方法数C8 2 28 . 或者从8个可能的位置中为― ‖选择六个的方法数27C 86 C 82

28 本题中用的方法可以用来得到一个通用的结果。定理3.5.1设S为具有k种类型元素的一个多重集每种元素均有无限的重复数。则S的r-组合的个数等于证明令S·a1 ·a2… ·ak考虑由r个―‖和k-1个―‖构成的rk-1个位置和rk-1符号。1-1-1-kkrrkr28把这些符号放到那些位置中的每一种方法决定了一个选择方式。从―‖到第一个―‖的数目代表选择了m1个a1。在第一个―‖和第二个―‖之间的数目m2代表了选择了m2个a2等等。因为选择―‖的位置有:种方法因此有: 种选择方式1-1-kkr1-1-kkr29它也等于选择―‖的位置的方法数:因此从S中允许重复的选择r元素无序r-组合数为: 证毕r1-kr1-1-1-kkrrkr30例假设有红兰绿三堆球每一堆至少包含8个球。a 选择8个球有多少种方法b 如果每一种颜色至少有一个球那么选择8个球有多少种方法解a 根据上定理选择8个球的方法数为452101-31-3831b 如果我们首先为每一种颜色选择一个球余下的5个球则也可以用上定理来解决问题。要完成选择我们必须另选择五个球。因此就有种方法。例一家面包房生产8种面包。如果盒装面包内有一打12个面包那么您能够买到多少种不同的盒装面包21271-31-3532解由题意面包房里生产的面包很多每个品种都在12个以上假设盒里的面包摆放顺序与买卖它无关这是一个组合问题。不同盒装的数量等于每种元素都可以提供无限多个数的8种类型元素的多重集的12-组合数。由定理这个数等于1219121-81233例由1234…..k中重复取出r个数组成非减序列的个数是多少解我们可以把被取数的集合看成多重集S·1 ·2 ·3 ….. ·k所取每组r个数够成的序列就是从S中取一个r-组合由于规定了非减排序其组合数为 如果不要求递增排序结果会不一样需用重复排列来求rr1-k34定理多重集S·a1·a2…·ak则S中不同元素至少出现一次的r-组合数为:证明:―每个元素至少出现一次‖则每个组合中已经固定了k个元素a1a2…ak。这时再从余下k类元素中选择r-k个来组合的r-k-组合数应是11krrrkrkkkr11111前面选择三种球的例题已经用了这个结论。35对多重集S·a1·a2 …·ak而言它的任意一个r-组合均呈x1·a1x2·a2 …xk·ak的形式其中x1x2 …xk皆为非负整数并且x1x2 …xk r.反之满足方程x1x2 …xk r的每个非负整数解x1x2 …xk对应S的一个r-组合故方程x1x2 …xk r 的解的个数就是S的r-组合数。我们同样可以利用对多重集S的r-组合数的求法来求多元方程的非负整数解的个数。36我们用―‖表示r-组合里的元素用―‖表示间隔r-组合里各类型元素的分隔符那么就可以构造新的多重集Tr· k-1· 它只有两种元素它的排列数就等于S的r-组合数。由P41关于两类型元素的排列数的求法得rkrkrkr11137例令S是由四种元素abcd构成的多重集S·a·b·c·d。S的使得4种元素每种都至少出现一次的10-组合的数目是多少解本题中r10k4由定理直接得例继续考虑面包装盒问题如果要求每盒中各种面包至少有一个这种盒装面包应该有多少种解题中r12k8有题意套用公式得84391411011kr38例方程x1x2x3x420其中x1≥3x2≥1x3≥0x4≥5。求该方程的整数解解根据定理的要求xi≥0我们引入新的变量y1x1–3y2x2–1y3x3–0y4x4–5这样保证了yi≥0方程变为:y1y2y3y411整数解的个数为:33kr364rkr39本次课我们介绍了多重集的r-排列和r-组合的原理以及排列数和组合数的求法等知识。多重集的r-排列和r-组合是在基本排列和组合知识上的推广也可以称为广义的排列组合。40作业如下:P47 1619

26 28 3416. 6个没有区别的车放在6×6棋盘上使没有两个车能够互相攻击的放置方法有多少如果是2个红车4个蓝车那么放置方法又是多少4119. 确定9的循环排列的个数其中0和9不在对面。提示计算0和9在对面的循环排列的个数26.确定多重集S3·a 4·b 5·c的10-排列的个数28.列出多重集S2·a 1·b 3·c的所有3-组合和4-组合。4234.

在三个孩子之间分发12个完全相同的苹果和1个橘子使每个孩子至少得到一个水果有多少种分发方法下次上课内容4.1 生成排列4.2 排列中的逆序