环址列 列,但首尾相接成环时就是同一个环排 列了,因此从集合中选取元素排成一个 环,其排列数将比线形排列数少
• 2.环排列 • 前面讨论的排列确切地说应该称为线形 排列，下面将介绍环排列。 • 定义11.2：从有限集合A={a1 ,a2 ,…,an }上 选取r个元素排成一个环形，这样的排 列称为A一个r-环排列。 • 例如排列12345与排列45123 是不同的排 列，但首尾相接成环时就是同一个环排 列了，因此从集合中选取元素排成一个 环，其排列数将比线形排列数少
512345 34512 因此每组中恰含有r个r线形排列,所以A 的r环排列数为p(n,r)r。 当r=n时,A的环排列数为p(n,n)mn=(n-1
• 定理11.4：由n个元素组成的集合A的r- 环排列数是： p(n,r)/r。A的n-环排列数 是P(n,n)/n=(n-1)! • 证明：把A的所有r-线形排列分成组， 使得同组的每个线形排列可以连接成同 一个环排列。 • 而对于一个r-环排列可产生 r个r-线形排 列(在r个位置上断链，产生r个不同排列 r-线形排列)， 因此每组中恰含有r个r-线形排列，所以A 的r-环排列数为p(n,r)/r。 当r=n时，A的环排列数为p(n,n)/n=(n-1)!
例5:(1)10个男孩和5个女孩站成一排,若 没有两个女孩相邻,问有多少种排法? ·(2)10个男孩和5个女孩站成一个圆圈,若没有 两个女孩相邻,问有多少种排法? 解:把男孩看成格子的分界,而每两个男孩 之间则看成一个空格。 (1)10个男孩站成一排的排法有p(10,10)种, 对于每一种排法有11个空位置放置5个女孩, 有p(15种放法。 由乘法原理得所求排列数是 p(10,10)×p(11,5)=(10!×11!)/6!
• 例11.5：(1)10个男孩和5个女孩站成一排~ ，若 没有两个女孩相邻，问有多少种排法? • (2)10个男孩和5个女孩站成一个圆圈，若没有 两个女孩相邻，问有多少种排法? • 解：把男孩看成格子的分界，而每两个男孩 之间则看成一个空格。 • (1) 10 个男孩站成一排的排法有p(10,10)种， • 对于每一种排法有 11 个空位置放置5个女孩， • 有p(11,5)种放法。 • 由乘法原理得所求排列数是 • p(10,10)×p(11,5)=(10!×11!)/6!
·(2)10个男孩站成一圈的排法实际上就 是10个元素的环排列数, 为p(10,0)/10。 而对于每一种排法有10个空位置放置女 孩, 故方法数为p(10.5 ·由乘法原理得所求排列数是 p(10,10)/10)×p(10,5)=(10×9)/!
• (2) 10 个男孩站成一圈的排法实际上就 是 10 个元素的环排列数， • 为p(10,10)/10。 • 而对于每一种排法有10个空位置放置女 孩， • 故方法数为p(10,5)。 • 由乘法原理得所求排列数是 p(10,10)/10)×p(10,5)=(10!×9!)/5!
113集合的组合 集合的组合问题 C(n,k)的有关性质及恒等式。 集合的组合 定义113:从n个元素的集合A中无序选 取r个元素组成S的子集称为S的一个r组 合,不同的组合总数记为C(n,r)。当n0, 规定C(n,0)=1。 显然当r>n时,C(m,r)=0
11.3 集合的组合 • 集合的组合问题 • C(n,k)的有关性质及恒等式。 • 一、集合的组合 • 定义11.3：从n个元素的集合A中无序选 取r个元素组成S的子集称为S的一个r-组 合,不同的组合总数记为C(n,r)。当n0， 规定C(n,0)=1。 • 显然当r>n时，C(n,r)=0