离散数学第2版作者王元元离散第6讲重集的排列与组合课件.ppt

第6讲 重集的排列与组合 重集的排列与组合 Page 88 to 94 内容提要 重集的概念 重集、元素、元素的重数、重集的表示 重集的排列计数 无穷重数重集的排列计数 有穷重数重集的全排列计数 重集的组合计数 无穷重数重集的组合计数 任意重集的组合计数（结合具体例子） 禁位排列的计数 错置计数 不相邻禁位排列的计数 内容回顾 容斥原理 内容回顾 排列的计数 线排列 圆排列 组合的计数 问题 把英文单词SUCCESS中的字母打乱之后重新排列，能得到多少不同的字符串？ 一家面包店生产12种面包，小张准备买6个面包，共有多少种不同的搭配方法？ 重集的概念 重集是允许多个相同的对象同时出现的特定集合 重集中的对象仍称为重集的元素 同一个元素出现的次数称为该元素的重数 用{n1· a1, n2· a2, …, nm· am}表示具有n1个a1，n2个a2，…，nm个am的重集，称为n（=n1+n2+…+nm）个元素的m元重集 重集中一个元素的重数可以是无穷大，例如{? · a1, n2· a2, …, nm· am} 重集的排列 定义6.3：重集的r-排列是指从重集{n1· a1, n2· a2, …, nm· am}（其中各ni可以是?）中每次取出r个元素 进行有序的排列，此时可得到的排列的总数称为 r-排列数。当r=n1+…+nm时，称此r-排列为全排 列，此时可得到的排列的总数称为全排列数 无穷重数重集的r排列 例：用8颗七彩的珠子串成长链，可以串出多少种不同的长链？（假定七彩的珠子取之不尽，并且不考虑链子的反转） 有穷重数重集的全排列 定理6.12： m元重集{n1· a1,n2· a2,…,nm· am}的全排列数是n!/(n1!*n2!* … *nm!)，其中n=n1+n2+…+nm 重集全排列举例 重新排列SUCCESS中的字母能得到多少不同的字符串？ 重集排列求解例1 一个盒子里有七个标有号码 1、2、…、7 的球，每次取出一个，记下它的号后再放回盒子，共取(放)四次，求四次中最大标号恰是 5 的取法数 重集排列求解例2 一位秘书在某大厦（B）工作，该大厦在她家（H）东边9个街段，北边7个街段。假定她每天从家里到大厦去上班都不走回头路（即只向东和向北行走）。问她可以有多少种不同的走法？ 重集排列求解例2（续） 一位秘书在某大厦（B）工作，该大厦在她家（H）东边9个街段，北边7个街段。假定她每天从家里到大厦去上班都不走回头路（即只向东和向北行走）。问她可以有多少种不同的走法？若图中的AC段积水，使她无法通过，这时她又可以有多少种不同的走法？ 重集排列求解例3 方程x1+x2+…+xm = r有多少组自然数解？ 重集排列求解例3（续） 方程x1+x2+…+xm = r有多少组自然数解？ 重集排列求解例4 方程x1+x2+…+xm = r有多少组正整数解？ 重集的组合 定义6.4：重集的r-组合是指从重集{n1· a1,n2· a2,…,nm· am}（其中各ni可以是?）中每次取出r个元素组成子重集，此时可得到的子重集的总数称为r-组合数 重集的组合 定理6.14：要求无穷重数的m元重集{? · a1, ? · a2,…, ? · am}的r-组合中a1，a2，…，am均至少入选一次的r-组合数是C(r?1, m ?1) 重集组合求解例1 从包含1元、2元、5元、10元、20元、50元和100元的钱袋中取5张纸币，若不关心选取顺序，且每种纸币至少有5张，共有多少种选法？ 重集组合求解例2 设S = {1 · a1, 1 · a2, …,1 · at, ? · at+1, ? · at+2, …, ? · am}，求S的r-组合数，t≤r 重集组合求解例3 计算重集S = {3 · a, 4 · b, 5 · c}的10-组合数 重集组合求解例3（续） 计算重集S = {3 · a, 4 · b, 5 · c}的10-组合数 重集组合求解例3（续） 计算重集S = {3 · a, 4 · b, 5 · c}的10-组合数 任意重集的组合数求解方法 计算重集S = {n1 · a1, n2 · a2, …, nm · am}的r-组合数 若n1 , n2, …, nm≥r ，可看作无穷重数的m元重集{?·a1, ?·a2,…, ?·am}的r组合问题，为C(m?1+r, r) 若某些元素的出现次数小于r，则 将重集T={?·a1, ?·a2, …, ?·am}的所有r组合的集合看作全集K，将其中元素ai的取出次数大于ni的r组合集合记为Pi 利用容斥原理，求 问题 餐厅里一个新服务员在寄存n个人的帽子时忘记把寄存号放在帽子上，当顾客取回他们的