第十一章排列与组 计数的基本原理是加法原理和乘法原理, 容斥原理是加法原理的推广
第十一章 排列与组合 计数的基本原理是加法原理和乘法原理， 容斥原理是加法原理的推广
111基本计数原理 定理1加法原理)设A和B是有限集合S 的两个互不相交的子集,且A∪B=S, 则S=A+B ·证明:因为S=AUB,先求A中元素个数 为A,再求S中其余元素个数。 因为A和B是有限集合S的两个互不相交 的子集, 所以S中的元素不在A中必在B中,且B 中元素不在A中 所以S中不在A中的元素有B个,即 S|=A|+Bl
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|
定理2乘法原理):设集合A和B都是 有限集,AF=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,23,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位数， 问有多少种选法？ • 这两个问题不同点在于前者不允许重复选取， 而后者则允许重复。 • 首先考虑不重复问题
定义11从n个元素的集合S中有序选取 的r个元素称为S的一个r排列,不同的 排列总数记为p(m,r)。若r=n,则称此排 列为全排列。当r>n,规定p(m,r)=0。 定理113:对rm的正整数n,r,有 p(n,r)=n(n-)…(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)!