竞赛组合数学(3)-容斥原理
清北学堂2013寒假培训组合数学（3）-容斥原理
知识点：设S为有限集合，S1 S,S1 S S1.则有
定理（容斥原理）。设S为有限集合，Sk S,Sk S Sk(k 1,2,..,n)。则有
|S1 S2 ... Sn| |S| |Si|
i 1
n
1 i j n
|S
i
Sj| ... ( 1)k
1 i1 ... ik n
|S
i1
Si2 Sik|+
... ( 1)n|S1 S2 ... Sn|；
定理（对偶定理）
|S1 S2 ... Sn|
|Si|
i 1
n
1 i j n
k 1
|S S| ... ( 1) ij
1 i1 ... ik n
|S
i1
Si2 Sik|
... ( 1)n 1|S1 S2 ... Sn|。
注意：（1）使用容斥原理的前提是：一个问题是以连续的否定形式出现；
连续的肯定也是连续的否定！
（2）一个组合公式中有" "交错符号；
（3）这里所涉及到的集合S是若干个子集合的并，可以相交。这是与前面的加法原理根本区别。
二个集合的情况：设A1,A2是二个集合。则
|A1 A2| |A1| |A2| |A1 A2|。
例1. 由数字1,2,3组成的n位数，要求n位数中1,2，和3中的每一个至少出现一次。
求所有这种n位数的个数。
例2. 有8个乘客随意踏上6节车厢，使得恰好有两节车厢空着的上法的总数是多少？
例3.设n是正整数， (n)为满足0 k n,(k,n) 1的整数k的个数。则有：
(n) n 1
p|n
1
。 p
例4. 求方程 错误！未找到引用源。 在约束条件
0 ≤错误！未找到引用源。 ≤ 3 , 0 ≤错误！未找到引用源。 ≤ 4 , 0 ≤错误！未找到引用源。 ≤ 5 下整数解个数 .
1,2,...,m , Bn 1,2,...,n . Bm 到 Bn 上的映射为满射 . 例5.设 m n , Bm
你可能喜欢
- 小学奥数题库
- 题库.教师版
- 数学理论
- 组合数学课件
- 小学奥数容斥原理
- 小学奥数题库1103页
- 小学四年级奥数题库5页
- 小学奥数智巧趣题题库学生版6页
- 小学奥数智巧趣题题库教师版8页
- 小学奥数盈亏问题题库学生版7页
- 小学奥数盈亏问题题库教师版11页
- 6-2-3溶液浓度问题.题库教师版16页
- 6-牛吃草问题.题库教师版-空的16页
- 时钟问题.题库教师版5页
- 6-2-4比例应用题.题库教师版17页
- 小学奥数统筹规划题库教师版.14页
- 小学奥数年龄问题题库教师版.14页
- 高中数学课件-排列组合和二项式定理35页
- 高中数学课件 圆柱、圆锥、圆台、球的结构特征、简单组合体的结构特征52页
- 组合数学课件60页
- 数学课件精品课件： 排列 组合 二项式定理98页
- 组合数学课件a51页
- 二上数学课件---组合问题114页
- 小学奥数《容斥原理》13页
- 小学五年级奥数容斥原理专题解析1页
- 小学奥数经典专题点拨：容斥原理2页
- 小学奥数之容斥原理(二)4页
- 小学奥数之容斥原理5页
- 小学奥数之容斥原理8页
