第十一章排列与组合 计数的基本原理是加法原理和乘法原理 容斥原理是加法原理的推广
第十一章 排列与组合 计数的基本原理是加法原理和乘法原理， 容斥原理是加法原理的推广
111基本计数原理 定理11(加法原理)设A和B是有限集合S 的两个互不相交的子集,且A∪B=S, 则|S|=|AH+|B| 证明:因为S=AUB,先求A中元素个数 为A|,再求S中其余元素个数。 因为A和B是有限集合S的两个互不相交 的子集, 所以S中的元素不在A中必在B中,且B 中元素不在A中 所以S中不在A中的元素有B个,即 SA+B
11.1 基本计数原理 • 定理11.1(加法原理)设A和B是有限集合S 的两个互不相交的子集，且A∪B=S， 则|S|=|A|+|B|。 • 证明：因为S=A∪B，先求A中元素个数 为|A|，再求S中其余元素个数。 • 因为A和B是有限集合S的两个互不相交 的子集， • 所以S中的元素不在A中必在B中，且B 中元素不在A中， • 所以S中不在A中的元素有|B|个，即 |S|=|A|+|B|
定理1,乘法原理):设集合A和B都是 有限集,A|=p,|B|=q,则:|A×B=pq 证明从略。 例:某学生从2门数学课和4门计算机 课中任意选修一门, 有2+4=6种选修方法。 若他要选修数学课和计算机课各一门, 则有2×4-8种选修方法
• 定理11.2(乘法原理)：设集合A和B都是 有限集，|A|=p，|B|=q，则：|A×B|=pq • 证明从略。 • 例：某学生从 2 门数学课和 4 门计算机 课中任意选修一门， • 有2+4=6种选修方法。 • 若他要选修数学课和计算机课各一门， • 则有2×4=8种选修方法
112集合的排列 集合的排列 将讨论集合的排列,包括环排列问题 1排列 (1)从{1,2,3,4,5,6,7,8,9}选取数字构成4位数, 如果要求每位数字都不相同,问有多少种选 法? (2)从{1,2,3,4,5,6,7,8,9}选取数字构成4位数, 问有多少种选法? 这两个问题不同点在于前者不允许重复选取, 而后者则允许重复。 首先考虑不重复问题
11.2 集合的排列 • 一、集合的排列 • 将讨论集合的排列，包括环排列问题。 • 1.排列 • (1)从{1,2,3,4,5,6,7,8,9}选取数字构成4位数， 如果要求每位数字都不相同，问有多少种选 法？ • (2)从{1,2,3,4,5,6,7,8,9}选取数字构成4位数， 问有多少种选法？ • 这两个问题不同点在于前者不允许重复选取， 而后者则允许重复。 • 首先考虑不重复问题
定义111从n个元素的集合S中有序选取 的r个元素称为S的一个r排列,不同的 排列总数记为p(m,r)。若r=n,则称此排 列为全排列。当r>n,规定p(n,r)=0 定理11.3:对r≤n的正整数n,r,有 p(n,r)=n(n-1)(n-r+1) 令n!=n(n-1)21,且规定0!=1,则 p(n,r)=n!/(n-r)!
• 定义11.1:从n个元素的集合S中有序选取 的r个元素称为S的一个r-排列，不同的 排列总数记为p(n,r)。若r=n，则称此排 列为全排列。当r>n，规定p(n,r)=0。 • 定 理 1 1 . 3 ： 对 rn 的正整数 n,r， 有 p(n,r)=n(n-1)…(n-r+1) • 令 n!=n(n-1)…2•1， 且 规 定 0 ! = 1 ， 则 p(n,r)=n!/(n-r)!
例:某产品加工需要一、二 五共5道工序, 则安排这些加工工序共有p(5,5)=120种 方法 若工序一必须先加工,则有p(4,4)=24种 方法。 若工序三不能放在最后加工,此时的安 排加工工序的方法数可这样来求 由于工序三的加工安排有p(4,1)=4种, 而其余的工序安排共有p(4,4)=24种, 由乘法原理知共有4×24=96种方法
• 例：某产品加工需要一、二、三、四、 五共 5 道工序， • 则安排这些加工工序共有 p(5,5)=120种 方法。 • 若工序一必须先加工，则有p(4,4)=24种 方法。 • 若工序三不能放在最后加工，此时的安 排加工工序的方法数可这样来求： • 由于工序三的加工安排有p(4,1)=4种， • 而其余的工序安排共有p(4,4)=24种， • 由乘法原理知共有4×24=96种方法
例:在上例中,(1)若规定工序四必须紧跟在工序 三的后面,有多少种安排方法? ·(2)若规定工序二必须在工序五的前面,有多少种 安排方法? 解:(1)把工序三、四看成一个工序,这样就相当于 四道工序,因此有p(4,4)=24种方法。 (2)把工序二放在工序五的前面,有四种情况: 1)工序二、五在一起,相当于四道工序, 因此有24种; 2)工序二、五中间间隔一道工序,中间一道工序从一、 三、四中选,有p(3,1)=3种, 把工序二、五连同中间间隔一道工序看成一个工序, 这样就相当于三道工序, 因此有p(3,3)=6种方法, 由乘法原理得p(3,3)×p(3,1)=18种;
• 例：在上例中，(1)若规定工序四必须紧跟在工序 三的后面，有多少种安排方法? • (2)若规定工序二必须在工序五的前面，有多少种 安排方法? • 解：(1)把工序三、四看成一个工序，这样就相当于 四道工序，因此有p(4,4)=24种方法。 • (2)把工序二放在工序五的前面，有四种情况: • 1)工序二、五在一起，相当于四道工序， • 因此有 24 种; • 2)工序二、五中间间隔一道工序，中间一道工序从一、 三、四中选，有p(3,1)=3种， • 把工序二、五连同中间间隔一道工序看成一个工序， • 这样就相当于三道工序， • 因此有p(3,3)=6种方法， • 由乘法原理得p(3,3)×p(3,1)=18种;
3)工序二、五中间间隔两道工序, 中间两道工序从 、四中选,有p(3,2)种, 把工序二、五连同中间间隔两道工序看成一个 工序 这样就相当于两道工序,因此有p(2,2)种方法, 由乘法原理得p(2,2)Xp(3,2)=12种; 4)工序二、五中间间隔三道工序,则有 p(3,3)=6种。 由加法原理知,要使工序二在工序五的前面, 安排加工工序的方法共有24+18+12+6=60种
• 3)工序二、五中间间隔两道工序， • 中间两道工序从一、三、四中选，有p(3,2)种， • 把工序二、五连同中间间隔两道工序看成一个 工序， • 这样就相当于两道工序，因此有p(2,2)种方法， • 由乘法原理得p(2,2)×p(3,2)=12种; • 4 ) 工 序 二 、 五 中 间 间 隔 三 道 工 序 ， 则 有 p(3,3)=6种。 • 由加法原理知，要使工序二在工序五的前面， 安排加工工序的方法共有24+18+12+6=60种
例:十进制数字中,没有重复的4位数 有多少个? 解:这是从10个数字0,1,2,3,4,5,6,78,9中取4个 的排列问题, 所以P(104)=5040。 又因为4位数首位不能为0,必须去掉这种情 况 而首位是0的4位十进制字符串个数就是考虑 另三位从1,2,3,4,5,6,7,8,9中选取的问题, 即为P(9,3)=504。 所以十进制数字中,没有重复的4位数有 5040-504=4536
• 例：十进制数字中，没有重复的4位数 有多少个？ • 解：这是从10个数字0,1,2,3,4,5,6,7,8,9中取4个 的排列问题， • 所以P(10,4)=5040。 • 又因为4位数首位不能为0，必须去掉这种情 况。 • 而首位是0的4位十进制字符串个数就是考虑 另三位从1,2,3,4,5,6,7,8,9中选取的问题， • 即为P(9,3)=504。 • 所以十进制数字中，没有重复的4位数有 5040-504=4536
例:排列26个字母,使得在a和b之间正好有7 个字母,问有多少种排法? 解:(1)a首b尾,中间恰含7个字母的排列有 P(24,7) b首a尾,中间恰含7个字母的排列有P(24,7) 因此以a,b为端点的9个字母排列有2P(24,7) (2把上述9个字母看成整体,与剩下的17个字 母共18个进行全排列,有P(18,18)=18 因此由乘法原理得“排列26个字母,使得在a 和b之间正好有7个字母”的排法有2P(24,7)18!
• 例：排列26个字母，使得在a和b之间正好有7 个字母，问有多少种排法? • 解：(1)a首b尾，中间恰含7个字母的排列有 P(24,7)； • b首a尾，中间恰含7个字母的排列有P(24,7)。 • 因此以a,b为端点的9个字母排列有2P(24,7)。 • (2)把上述9个字母看成整体，与剩下的17个字 母共18个进行全排列，有P(18,18)=18! • 因此由乘法原理得“排列26个字母，使得在a 和b之间正好有7个字母”的排法有2P(24,7)18!