1、3.3 多重集的 排列与组合 3.3.1 多重集的排列 3.3.2 多重集的组合 吉林大学 多重集 中可以有重复的元素。 多重集合表示为其中： 互不相同 M中有 ki个 ai（ 1in）， 称 ki为 ai的重复度ki是正整数，也可以是 ，表示 M中有无限多个 ai 例子 是一个 10个元素的多重集合， 其中有 3个 a， 1个 b， 2个 c， 4个 d. M表示为 定理 3.3.1 多重集合的 r-排列数是 nr证明 在构造 M的一个 r-排列时，排列中的第一个元素有 n种选择，第二个元素也有 n种选择， ，第 r个元素也有 n种选择。由于 M中的每个元素都是无限次地重复，所以 r-排列中
2、的任意一项都有 n种选择，而且不依赖于前面各项的选择，故 M的 r-排列数为 nr 3.3.1 多重集的排列 这个问题对应的 分配问题模型 是：将 r个有区别的球放入 n个不同的盒子中，且每个盒子的球数不加以限制，而且同盒的球不分次序，则不同的放法为 nr种 若 M中每个元素的重复度大于等于 r，则结论仍然成立。 例 3.3.1 用 26个英文字母可以构造出多少个包含 2个元音字母（可以相同）且长度为 8的 “单词 ”解 该问题 是求 的包含 2个元音字母的 8-排列数。在 长 度 为 8的字符串中， 2个元音字母出 现 的位置的 选取方式有 种，而每个元音位置可取 5个元音字母中的一个，剩余
3、 6个 辅 音字母的位置可取 21个 辅 音字母中的任一个，因而， 满足 题 意的 “单词 ”有 52216个 . 证 明 首先把 M中所有的个元素看成是互不相同的， 则 全排列数为 。但 ki个 ai的位置相同，且其他元素排列也相同的排列 实质 上是同一个排列。故 M的全排列数 为 例 3.3.2使用英文字母表中 26个字母构成 8个字母的单词且 允许字母重复 ，如果要求每个单词至少含有 3个元音字母，那么能构成多少个这样单词解 因为一共有 5个元音字母，每个单词至少含有 3个元音字母即包含 3个， 4个或者 5个元音字母。则分三种情况，有 3个元音字母的单词有有 4个元音字母的单词有有 5
4、个元音字母的单词有根据加法原理共例 3.3.3 求多重集 的 8-排列数解 可分三种情况 计 算： M-a的 8-排列数 , 即 为 排列数为 ： M-b的 8-排列数 ,即 为 排列数为 ： M-c的 8-排列数 ,即 为 排列数为 ： 多重集 M的 8-排列数 为 420+280+560=1260 例 3.3.4 从 4个 a， 4个 b， 4个 c， 4个 d中选择字母形成一个 10个字母的序列，如果每个字母至少出现两次，有多少种方法形成这样的序列 解 这个问题实际上是求 的 10-排列数，但要求每个 10排列中包含a,b,c,d每个字母至少两个。我们设 ，则原问题可以分成如下两大类共 10种情况：
