解:设S为所给字母的全排列,令A1,A2,A3分别为排列中出现单 词MATH,IS,FUN的排列集合。显然,其补集代表它们不作为连 续字母出现的集合。根据题意有 S 9! A1中的排列可以看成6个字母MATH, I, S, F, U, N的排列,因 此 A1 6! , 同理 ,A2 8!, A3 7! ; A B 中的排列是5个字母MATH, IS, F, U,N的排列, 因此 A1 A2 5!, 同理,A1 A3 4!,A2 A3 6!, A1 A2 A3 3! 。 根据容斥原理,在所有排列中,MATH,IS和FUN都不作为连续 字母出现的排列数为 A1 A2 A3 9!6!8!7!5!4!6!3! 317658 .
i 1 i
n
又因为在m个性质中取出一对性质的方法有C(m,2)个,故y是C(m,2)个 | C(m,2) , 集合Ai∩Aj(i≠j)的一个元素,在 |Ai Aj 中被计算的次数为
……,
i j
因此y在等式右端被计算的次数净值
C(m,0)-C(m,1)+C(m,2)+…+(-1)n C(m,n), 由于m<k时,C(m,k)=0,有
§5.1 包含排斥原理
•
|A| |S||A|
S
A
§5.1 包含排斥原理 5.1.1 引论
引例1 把1,2,3,…,n全排列,计算“1”不在第1个位置的排列数. 解: 集合格式写法 A {1排在第一个位置的前 n个数的排列 } } 令 S {1,2,...,n的排列 , ,
§5.1 包含排斥原理
3 5
根据容斥原理,从1到500的整数中不能被3和5整除的数的个数为
15