离散第6讲 重集的排列与组合3.3

1、 计算机专业基础课程计算机专业基础课程 授课人：梁妍授课人：梁妍vPowerPoint Template_Sub 1计数基本原理计数基本原理2排列与组合排列与组合3重集的排列与组合重集的排列与组合v重集的排列与组合重集的排列与组合 Page 38 to 43 Page 38 to 43离散数学离散数学第第6 6讲讲-4-第第6讲讲 重集的排列与组合重集的排列与组合v内容提要内容提要重集的概念重集的概念重集、元素、元素的重数、重集的表示重集、元素、元素的重数、重集的表示重集的排列计数重集的排列计数无穷重数重集的排列计数无穷重数重集的排列计数有穷重数重集的全排列计数有穷重数重集的全排列计数重集的组

2、合计数重集的组合计数无穷重数重集的组合计数无穷重数重集的组合计数任意重集的组合计数（结合具体例子）任意重集的组合计数（结合具体例子）禁位排列的计数禁位排列的计数错置计数错置计数不相邻禁位排列的计数不相邻禁位排列的计数-5-第第6讲讲 重集的排列与组合重集的排列与组合v内容回顾内容回顾容斥原理容斥原理|.|21nSSS问题问题学校学校1807个新生中有个新生中有453人选了计算机科学课，人选了计算机科学课，567人选了人选了数学数学 课，课，299人同时选了计算机科学课和数学课。问有多人同时选了计算机科学课和数学课。问有多少学生既没选计算机科学课又没选数学课？少学生既没选计算机科学课又没选数学课

3、？用用S表示全体新生，用表示全体新生，用A、B分别表示选了计算机科学课和分别表示选了计算机科学课和数学课的新生集合，那么数学课的新生集合，那么 | A B | = |S| |A| |B| +|AB| = 1807 453 567 + 299 = 1086 人人-6-第第6讲讲 重集的排列与组合重集的排列与组合v内容回顾内容回顾排列的计数排列的计数线排列线排列圆排列圆排列组合的计数组合的计数-7-第第6讲讲 重集的排列与组合重集的排列与组合v问题问题把英文单词把英文单词SUCCESS中的字母打乱之后重新排列，中的字母打乱之后重新排列，能得到多少不同的字符串？能得到多少不同的字符串？一家面包店生产

4、一家面包店生产12种面包，小张准备买种面包，小张准备买6个面包，共个面包，共有多少种不同的搭配方法？有多少种不同的搭配方法？-8-第第6讲讲 重集的排列与组合重集的排列与组合v重集的概念重集的概念重集是把多个重集是把多个相同的对象相同的对象同时表示出来的特定集合同时表示出来的特定集合重集中的对象仍称为重集的重集中的对象仍称为重集的元素元素同一个元素出现的次数称为该元素的同一个元素出现的次数称为该元素的重数重数用用n1 a1, n2 a2, , nm am表示具有表示具有n1个个a1 ， n2个个a2，nm个个am的重集，称为的重集，称为n（=n1+n2+nm）个元素的个元素的m元重集元重集重集

5、中某些元素的重数可以是无穷大，例如重集中某些元素的重数可以是无穷大，例如 a1, n2 a2, , nm am-9-第第6讲讲 重集的排列与组合重集的排列与组合v重集的排列重集的排列定义定义3.3：重集的重集的r-排列排列是指从重集是指从重集n1 a1, n2 a2, , nm am（其中各（其中各ni可以是可以是 ）中每次取出）中每次取出r个元素个元素 进行进行有序的排列有序的排列，此时可得到的排列的，此时可得到的排列的总数总数称为称为 r-排列数排列数。当。当r=n1+nm时，称此时，称此r-排列为全排排列为全排 列，列，此时可得到的排列的总数称为此时可得到的排列的总数称为全排列数。全排列

6、数。 给定重集：给定重集：1 a, 2 b 2-排列：排列：abbabb全排列：全排列：abbbabbba-10-第第6讲讲 重集的排列与组合重集的排列与组合v无穷重数重集的无穷重数重集的r r排列排列定理定理3.11：无穷重数无穷重数的的m元重集元重集 a1, a2, am的的r-排列数是排列数是mr此结论对于各此结论对于各ni (1i m) r 的重集均成立的重集均成立-11-第第6讲讲 重集的排列与组合重集的排列与组合例例3.7：（1）用）用7颗六彩的珠子串成长链，可以串出多少种不同颗六彩的珠子串成长链，可以串出多少种不同的长链？（假定六彩的珠子取之不尽，并且不考虑链子的反转）的长链？（

7、假定六彩的珠子取之不尽，并且不考虑链子的反转）（2）用）用7颗六彩的珠子串成环链，至少用两种颜色的珠子，可以颗六彩的珠子串成环链，至少用两种颜色的珠子，可以串出多少种不同的环链？（假定六彩的珠子取之不尽，并且不串出多少种不同的环链？（假定六彩的珠子取之不尽，并且不考虑链子的反转）考虑链子的反转）解解. （1）用）用7颗六彩的珠子串成长链，可以串出不同的长链颗六彩的珠子串成长链，可以串出不同的长链 (种种)（2）用）用7颗六彩的珠子串成环链，至少用两种颜色的珠子，可以颗六彩的珠子串成环链，至少用两种颜色的珠子，可以串出不同的环链串出不同的环链 （种）（种）注意：这里重集的圆排列元素个数注意：这里

8、重集的圆排列元素个数r必须是质数，否则一个必须是质数，否则一个r-圆圆排列未必可以展开成排列未必可以展开成r个（线）排列（请读者自行给出反例）。个（线）排列（请读者自行给出反例）。27993667399907)66(7-12-第第6讲讲 重集的排列与组合重集的排列与组合v有穷重数重集的全排列有穷重数重集的全排列定理定理3.12： m元重集元重集n1 a1,n2 a2,nm am的全排的全排列数是列数是n!/(n1!*n2!* *nm!)，其中，其中n=n1+n2+nm证明：证明：一个全排列共占据一个全排列共占据n1+n2+nm个位置。为确定一个个位置。为确定一个排列，首先在所有位置中选择排列，

9、首先在所有位置中选择n1个位置给个位置给a1，再从剩下的位，再从剩下的位置中选择置中选择n2个位置给个位置给a2，最后从剩下的位置中选择，最后从剩下的位置中选择nm个位置给个位置给am。 根据根据乘法原理乘法原理，共有，共有 种排列。种排列。mmmmnnnnnnnnnnCCC.232121.mmmmnnnnnnnnnnCCC.232121.! 0!.)!.( !)!.()!.( !)!.(4323232121mmmmmmnnnnnnnnnnnnnnnn!.!21mnnnn-13-第第6讲讲 重集的排列与组合重集的排列与组合v重集全排列举例重集全排列举例重新排列重新排列SUCCESS中的字母能得

10、到多少不同中的字母能得到多少不同的字符串？的字符串？解解：单词中包含单词中包含3个个S、1个个U、2个个C、1个个E 可看作重集可看作重集3S, 1U, 2C, 1E的全排列数问题的全排列数问题 根据定理，共能排出不同的字符串根据定理，共能排出不同的字符串! 1!2! 1!3)!1213(种420-14-第第6讲讲 重集的排列与组合重集的排列与组合v重集重集r-r-排列举例排列举例一个盒子里有七个标有号码一个盒子里有七个标有号码 1、2、7 的球，每次的球，每次取出一个，记下它的号后再放回盒子，共取取出一个，记下它的号后再放回盒子，共取(放放)四次，四次，求四次中最大标号恰是求四次中最大标号恰

11、是 5 的取法数的取法数解解：可看作可看作无穷重数的无穷重数的7元重集元重集的的4-排列问题排列问题。为使最大。为使最大标号恰为标号恰为5，排列中必须出现号码，排列中必须出现号码5，且不能出现，且不能出现6和和7。不出现不出现6、7的的4排列共有排列共有54个，而其中不出现个，而其中不出现5的有的有44个个最大标号恰是最大标号恰是 5 的取法数共有的取法数共有5444 = 369种种-15-第第6讲讲 重集的排列与组合重集的排列与组合v例例3.83.8一位秘书在某大厦（一位秘书在某大厦（B）工作，该大厦在她家（）工作，该大厦在她家（H）东边）东边9个个街段，北边街段，北边7个街段。假定她每天从

12、家里到大厦去上班都不走个街段。假定她每天从家里到大厦去上班都不走回头路（即只向东和向北行走）。问她可以有多少种不同的回头路（即只向东和向北行走）。问她可以有多少种不同的走法？走法？解解：不走回头路，上班路径必恰好：不走回头路，上班路径必恰好包含包含9个向东街段和个向东街段和7个向北街段个向北街段一种上班路径相当于一种上班路径相当于重集重集9E, 7N的一个全排列的一个全排列，其中，其中E表示向东，表示向东，N表示向北表示向北根据定理，可有根据定理，可有=11440 种走法种走法 !7!9)!79(HB2468246-16-第第6讲讲 重集的排列与组合重集的排列与组合v例例3.83.8一位秘书在

13、某大厦（一位秘书在某大厦（B）工作，该大厦在她家（）工作，该大厦在她家（H）东边）东边9个个街段，北边街段，北边7个街段。假定她每天从家里到大厦去上班都不走个街段。假定她每天从家里到大厦去上班都不走回头路（即只向东和向北行走）。问她可以有多少种不同的回头路（即只向东和向北行走）。问她可以有多少种不同的走法？走法？若图中的若图中的AC段积水，使她无法通过，这时她又可以有段积水，使她无法通过，这时她又可以有多少种不同的走法？多少种不同的走法？HB2468246解解：经过：经过AC段的走法可如下计算：段的走法可如下计算：先从先从H走到走到A，有，有 种走法；种走法；然后从然后从A到到C，一种走法；，

14、一种走法；最后从最后从C到到B，有，有 种走法。种走法。所以，根据所以，根据乘法原理乘法原理，经过，经过AC段共有段共有35 1 70=2450 种走法。种走法。不经过不经过AC段的走法数为段的走法数为114402450 = 8990 种种 35! 3! 4)!34(70!4!4)!44(A AC C-17-第第6讲讲 重集的排列与组合重集的排列与组合v例例3.93.9方程方程x1+x2+xm = r有多少组自然数解？有多少组自然数解？m = 3 r = 5x1 + x2 + x3 = 5111110以下均是该方程的自然以下均是该方程的自然数解：数解：x1 = 2, x2 = 1, x3 =

15、2x1 = 0, x2 = 0, x3 = 5x1 = 2, x2 = 3, x3 = 00111110 011111 001100111x1 = 2, x2 = 0, x3 = 31111100 x1 = 5, x2 = 0, x3 = 00111110 x1 = 0, x2 = 5, x3 = 01110101x1 = 3, x2 = 1, x3 = 1-18-第第6讲讲 重集的排列与组合重集的排列与组合v例例3.93.9方程方程x1+x2+xm = r有多少组自然数解？有多少组自然数解？解解：考虑：考虑m1个个0和和r个个1组成的组成的0,1序列，我们把这样的一个序列，我们把这样的一个序

16、列看作是序列看作是m1个个0把把r个个1分成分成m组的一个分割。组的一个分割。一个一个0,1序列的分割对应于方程的一组自然数解，反之，方序列的分割对应于方程的一组自然数解，反之，方程的一组自然数解也对应着一个这样的程的一组自然数解也对应着一个这样的0,1序列分割序列分割因此方程因此方程x1+x2+xm = r的自然数解的组数等于重集的自然数解的组数等于重集(m-1)0, r1的全排列数，即的全排列数，即 rrmCrmrm1!)!1()!1(-19-第第6讲讲 重集的排列与组合重集的排列与组合v例例3.93.9方程方程x1+x2+xm = r有多少组正整数解？有多少组正整数解？解解：考虑由：考虑

17、由r个个1组成的序列，之间有组成的序列，之间有r-1个空位。个空位。 在这些空位中选择在这些空位中选择m-1个插入个插入0，得到，得到1个个0,1序列，可看序列，可看作是作是m1个个0把把r个个1分成分成m组，且每组至少有组，且每组至少有1个个1。 这对应着方程这对应着方程x1+x2+xm = r的一组正整数解。的一组正整数解。 反之，一组正整数解也对应着这样的一个反之，一组正整数解也对应着这样的一个0,1序列分割。序列分割。 因此，方程正整数解的组数等于从因此，方程正整数解的组数等于从r-1个空位中选择个空位中选择m-1个空位的组合数，即个空位的组合数，即 11mrC-20-第第6讲讲 重集

18、的排列与组合重集的排列与组合v重集的组合重集的组合定义定义3.4：重集的重集的r-组合组合是指从重集是指从重集n1 a1,n2 a2, nm am（其中各（其中各ni可以是可以是 ）中每次取出）中每次取出r个元素组个元素组成子重集成子重集，此时可得到的子重集的总数称为，此时可得到的子重集的总数称为r-组合组合数数定理定理3.13：无穷重数的无穷重数的m元重集元重集 a1, a2, am的的r-组合数是组合数是C(m1+r, r)证明：证明：m元重集的元重集的r-组合是组合是r个元素组成的子重集个元素组成的子重集x1a1, x2a2, xmam ，其中，其中x1+x2+xm = r。因此，。因此

19、，r-组合数组合数即方程即方程x1+x2+xm = r的自然数解数目。的自然数解数目。根据上一小节的例子，根据上一小节的例子，r-组合数为组合数为 。!)!1()!1(1rmrmCrrm此结论对于各此结论对于各ni(1im)r 的重集均成立的重集均成立-21-第第6讲讲 重集的排列与组合重集的排列与组合v重集的组合重集的组合定理定理3.14：要求无穷重数的要求无穷重数的m元重集元重集 a1, a2, am的的r-组合中组合中a1，a2，am均至少入选一均至少入选一次的次的r-组合数是组合数是C(r1, m 1)此结论对于各此结论对于各ni (1i m) r 的重集均成立的重集均成立证明：证明：

20、所要求的所要求的r-组合，即组合，即r个元素组成的子重集个元素组成的子重集x1a1, x2a2, xmam ，其中，其中x1+x2+xm = r，且各，且各xi(1im)均均为正整数。为正整数。因此，相当于方程因此，相当于方程x1+x2+xm = r的正整数解数目。的正整数解数目。根据上一小节的例子，每个元素至少入选一次的根据上一小节的例子，每个元素至少入选一次的r-组合数组合数为为 。11mrC-22-第第6讲讲 重集的排列与组合重集的排列与组合v重集组合求解例重集组合求解例1 1从包含从包含1元、元、2元、元、5元、元、10元、元、20元、元、50元和元和100元的钱袋中取元的钱袋中取5张

21、纸币，若不关心选取顺序，且每张纸币，若不关心选取顺序，且每种纸币至少有种纸币至少有5张，共有多少种选法？张，共有多少种选法？解解：每种纸币至少有每种纸币至少有5张张 相当于求重集相当于求重集 a1, a2, , a7的的5-组合数问题组合数问题 根据定理，共有根据定理，共有 = 462 种选法种选法5157C-23-第第6讲讲 重集的排列与组合重集的排列与组合v例例3.103.10一家面包店卖一家面包店卖6种面包，假如你要买种面包，假如你要买12个面包，可以个面包，可以有多少种选择方案有多少种选择方案(假定各种面包的数量都大大超过假定各种面包的数量都大大超过12只只)？假如你要买？假如你要买1

22、2个面包，且每种面包至少一只，个面包，且每种面包至少一只，可以有多少种选择方案？可以有多少种选择方案？ 解解：第一问是一个求重集：第一问是一个求重集 的的12-组组合数的问题。因此其解是合数的问题。因此其解是 第二问则是求重集第二问则是求重集 的、每个的、每个元素至少取一个的元素至少取一个的12-组合数的问题。因此其解是组合数的问题。因此其解是,621aaa61882345131415161751751216121216CCC,621aaa4622345789101151116112CC-24-第第6讲讲 重集的排列与组合重集的排列与组合v例例3.113.11设设S = 1 a1, 1 a2,

23、 ,1 at, at+1, at+2, , am，求，求S的的r-组合数，组合数，tr解解：将：将S分为两个子集，分为两个子集，S1 = 1a1, 1a2,1at，S2 = at+1, at+2, am 。求求S的的r-组合可以分为两步：组合可以分为两步：1)先从先从S1中取中取i (i=0,1,2,t)个元素个元素（普通集合的（普通集合的i-组合问题），组合问题），2)再从再从S2中取中取r-i个元素个元素（无穷重集的（无穷重集的(ri)-组合问题），组合问题），根据加法、根据加法、乘法原理乘法原理，S的的r-组合数是组合数是 irirtmtiitCC10itCirirtmC1S2中只含有中

24、只含有m-t种种不同的元素不同的元素只从只从S2中取中取r-i个元素，其余个元素，其余的的i个元素已从个元素已从S1中取出中取出-25-第第6讲讲 重集的排列与组合重集的排列与组合v例例3.123.12计算重集计算重集S = 3 a, 4 b, 5 c的的10-组合数组合数解解：令重集：令重集T= a, b, c。设。设T的所有的所有10-组合集合为组合集合为K。全集全集K中含有多于中含有多于3个个a的的10-组合集合为组合集合为Pa，含有多于，含有多于4个个b的的10-组合集合为组合集合为Pb，含有多于，含有多于5个个c的的10-组合集合为组合集合为Pc。因此因此S的的10-组合数为：组合数

25、为： |PaPbPc|容斥原理容斥原理：|PaPbPc| = |KPaPbPc| = |K| (|Pa|+|Pb|+|Pc|) + (|PaPb|+|PaPc|+|PbPc|) |PaPbPc|-26-第第6讲讲 重集的排列与组合重集的排列与组合v例例3.123.12计算重集计算重集S = 3 a, 4 b, 5 c的的10-组合数组合数根据定理，根据定理，|K| = =66|Pa|= =28 （取定（取定4个个a后，再取后，再取T的一个的一个6-组合）组合）|Pb|= =21 （取定（取定5个个b后，再取后，再取T的一个的一个5-组合）组合）|Pc|= =15 （取定（取定6个个c后，再取后

26、，再取T的一个的一个4-组合）组合）|PaPb|= =3 （取定（取定4个个a和和5个个b后，再取后，再取T的一个的一个1-组合）组合）|PaPc|= 1 （取定取定4个个a和和6个个c后，已无需再取）后，已无需再取）|PbPc|= 0 （多于（多于4个个b、5个个c的的10-组合不存在）组合不存在）|PaPbPc|= 0 （多于（多于3个个a、4个个b、5个个c的的10-组合不存在）组合不存在）|PaPbPc|= 66-28-21-15+3+1+0-0 = 6 101103C6163C5153C4143C1113C-27-第第6讲讲 重集的排列与组合重集的排列与组合v例例3.123.12计算

27、重集计算重集S = 3 a, 4 b, 5 c的的10-组合数组合数解法解法2：重集重集S中共有中共有12个元素，每次取出个元素，每次取出10个后还剩个后还剩2个个S的的10-组合与组合与2-组合一一对应组合一一对应求求10-组合数相当于求组合数相当于求2-组合数组合数S中每种元素均大于中每种元素均大于2个，所以可看作无穷重集的个，所以可看作无穷重集的2-组合问组合问题。根据定理，共有题。根据定理，共有 C(3+2-1,2) = 6 种不同的种不同的2-组合组合S的的10-组合数为组合数为6 -28-第第6讲讲 重集的排列与组合重集的排列与组合v任意重集的组合数求解方法任意重集的组合数求解方法

28、计算重集计算重集S = n1 a1, n2 a2, , nm am的的r-组合数组合数若若n1 , n2, , nmr ，可看作无穷重数的，可看作无穷重数的m元重集元重集 a1, a2, am的的r组合问题，为组合问题，为C(m1+r, r)若某些元素的出现次数小于若某些元素的出现次数小于r，则，则将重集将重集T= a1, a2, , am的所有的所有r组合的集合看作全组合的集合看作全集集K，将其中元素，将其中元素ai的取出次数大于的取出次数大于ni的的r组合集合记为组合集合记为Pi利用容斥原理，求利用容斥原理，求-29-第第6讲讲 重集的排列与组合重集的排列与组合v禁位排列的计数禁位排列的计数定义定义3.5（错置）：（错置）：集合集合1, 2, 3, , n的全排列，的全排列，使得每个数使得每个数i都不在第都不在第i位上，称这样的排列为位上，称这样的排列为1, 2, 3, , n的一个的一个错置错置-30-第第6讲