组合数学_第02讲_两个基本的计数原理(0229).pptVIP

组合数学 王新红 第1章 绪论 第2章 排列与组合 第3章 容斥原理 第4章 鸽笼原理 第5章 母函数 第6章 递推关系 第7章 Pólya定理 第2章 排列与组合 两个基本的计数原理 (无重)集合的排列 (无重)集合的组合 多重集的排列 多重集的组合 两个基本计数原理 本次课我们将介绍计数的两个基本原理，以及这两个原理的应用。 两个基本计数原理 加法原理 乘法原理 应用举例 计数问题分类 集合的划分 集合的划分 若S1, S2 , …, Sm均是集合S的子集，且同时满足： ① Si ∩ Sj ＝ ? （i≠j） ② S1 ∪ S2 ∪ … ∪ Sm ＝ S 则称S1, S2 , …, Sm是集合S的一个划分。 加法原理 集合论定义 设S1, S2 , …, Sm是集合S的一个划分，则 ?S?= ?S1?+ ?S2? + … +?Sm? 其中 ?S?表示 S中元素的个数 加法原理 例1 小于100的正偶数有49个,小于100的正奇数有50个,则小于100的正整数有49+50=99个. 两个基本计数原理 加法原理 乘法原理 应用举例 计数问题分类 乘法原理 集合论定义 设S1, S2 是两个集合，根据S1，S2定义集合S如下： S = S1 × S2 ={(x, y) ?x ? S1 ∧ y ? S2 } 则: ?S? = ?S1?×?S2? 乘法原理 例4 从u到v有3条不同的道路,从v到w有2条不同的道路,则从u经v到w有3×2=6条不同的道路. 两个基本计数原理 加法原理 乘法原理 应用举例 计数问题分类 基本计数原理应用举例 基本计数原理应用举例 例6 从包括五本不同的计算机书，三本不同的数学书和两本不同的美术书中，选择两本不同类型的书有多少种方法？ 基本计数原理应用举例 例7 求含有数字1的4位数的个数。  基本计数原理应用举例 例8 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数 基本计数原理应用举例 例8 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数 基本计数原理应用举例 例9一个由张一,王二,李三,赵四,刘五和陈六组 成的六人委员会要选出一个主席，一个秘书和一个会计。 (a) 有多少种选择? (b)如果张一或王二必须是主席，有多少种选法？ (c) 如果刘五必须任三职之一，有多少种选法？ (d) 如果赵四和陈六必须任职，有多少种选法？ 基本计数原理应用举例 例9一个由张一,王二,李三,赵四,刘五和陈六组 成的六人委员会要选出一个主席，一个秘书和一个会计。 (a) 有多少种选择? (b)如果张一或王二必须是主席，有多少种选法？ (c) 如果刘五必须任三职之一，有多少种选法？ (d) 如果赵四和陈六必须任职，有多少种选法？ 基本计数原理应用举例 例9一个由张一,王二,李三,赵四,刘五和陈六组 成的六人委员会要选出一个主席，一个秘书和一个会计。 (a) 有多少种选择? (b)如果张一或王二必须是主席，有多少种选法？ (c) 如果刘五必须任三职之一，有多少种选法？ (d) 如果赵四和陈六必须任职，有多少种选法？ 基本计数原理应用举例 例9一个由张一,王二,李三,赵四,刘五和陈六组 成的六人委员会要选出一个主席，一个秘书和一个会计。 (a) 有多少种选择? (b)如果张一或王二必须是主席，有多少种选法？ (c) 如果刘五必须任三职之一，有多少种选法？ (d) 如果赵四和陈六必须任职，有多少种选法？ 基本计数原理应用举例 例9一个由张一,王二,李三,赵四,刘五和陈六组 成的六人委员会要选出一个主席，一个秘书和一个会计。 (a) 有多少种选择? (b)如果张一或王二必须是主席，有多少种选法？ (c) 如果刘五必须任三职之一，有多少种选法？ (d) 如果赵四和陈六必须任职，有多少种选法？ 基本计数原理应用举例 例10 在1000和9999之间有多少不同数字的奇数？ 基本计数原理应用举例 例11 在0和10000之间有多少个整数恰好有一位数 字是5？ 基本计数原理应用举例 例11 在0和10000之间有多少个整数恰好有一位数 字是5？ 基本计数原理应用举例 例12 确定数34×52×117×138的正整数因子的个数。 小结 我们可以将加法原理总结为：当被计数的元素可以被分解到不相交的子集中时，我们将每个子集