满足性质选了西班牙语的学生人数.ppt

4.6 容斥原理的应用 容斥原理的另一种形式(P180) P178 例4：转换问题描述 |S|＝满足性质“选了西班牙语”的学生人数 |F|＝满足性质“选了法语”的学生人数 |R|＝满足性质“选了俄语”的学生人数 没有选西班牙语、法语、俄语中任一门外语的学生人数 4.6 容斥原理的应用 容斥原理的另一种形式(P180) P178 例4：转换问题描述 没有选西班牙语、法语、俄语中任一门外语的学生人数 ＝？ 4.6 容斥原理的应用 容斥原理的另一种形式(P180) P178 例4中，增设条件总学生人数＝2100 请问：没有选西班牙语、法语、俄语中任一门外语的学生人数是多少？ 减法结合容斥原理 4.6 容斥原理的应用 容斥原理的另一种形式(P180) 设有全集 S 及其 n 个子集 A1, A2, …, An 子集 Ai 中元素具有性质 Pi |Ai|＝Ai 中元素个数＝具有性质 Pi 的元素个数 同时具有性质 Pi 和 Pj 的元素个数 不具有性质 Pi 的元素个数 同时不具有性质 Pi 和 Pj 的元素个数 4.6 容斥原理的应用 容斥原理的另一种形式(P180) 设有全集 S 及其 n 个子集 A1, A2, …, An 子集 Ai 中元素具有性质 Pi |Ai|＝Ai 中元素个数＝具有性质 Pi 的元素个数 不具有性质 P1 , P2 ,…Pn 中任一条的元素个数 ＝？ 4.6 容斥原理的应用 容斥原理的另一种形式(P180) 有全集 S 及其 n 个子集( Ai 中元素有性质 Pi) 不具有性质 P1, P2,…,Pn 中任一条的元素个数＝ 减法结合容斥原理 4.6 容斥原理的应用 容斥原理的另一种形式(P180)：令 不具有性质 Pi 的元素个数 元素总个数 不具有 P1, P2, … , Pn 中任一条的元素个数 具有性质 Pi 的元素个数 同时具有性质 P1, P2, … , Pn 的元素个数 4.6 容斥原理的应用 容斥原理的另一种形式(P180) 以集合方式表示的等价公式 4.6 容斥原理的应用 例1(P180) 比较：P131 例5 非负整数?解的总数 变量值受限：≤，且，交集 ≤?≥，且?或，交集?并集 排除：减法 容斥 4.6 容斥原理的应用 4.6.3 Eratosthenes筛 程序设计要点 数组、素数的标志 4.6 容斥原理的应用 4.6.4 映上(满射)函数个数：例2 回顾：P107 例6(函数)、例7(一对一) 满射函数个数 ＝ 函数个数 － 非满射函数个数 非满射函数：伴域中存在元素不在值域中 1 个元素不在：C(4, 1)*35 2 个元素不在：C(4, 2)*25 3 个元素不在：C(4, 3)*15 4 个元素不在：不存在无值域的函数=0 4.6 容斥原理的应用 4.6.5 错位排列：例4 错位排列数＝全排列数－非错位排列数 非错位排列＝A1∪A2∪A3∪…∪An 集合 Ai＝{ 元素 i 位置不变的排列 } 性质 Pi：元素 i 位置不变 Ai∩Aj＝｛ 元素 i、j 位置不变的排列 } Ai∩Aj∩Ak＝ { 元素 i、j、k 位置不变的排列 } … 作业1-1 P179 4, 6 P184 2, 6, 7 第4章 高级计数技术 教师：黄诚 手机邮箱：huangcheng@swpu.edu.cn QQ：449557241 回顾：基本计数技术 计数：确定具有特定性质的个体的个数 基本原则：乘法、加法 存在性计数：鸽巢原理 有序/无序安排计数：排列、组合 回顾：基本计数技术 基本原则：乘法、加法 乘法：P107 例6、例7 从m元集合到n元集合，有多少个函数？一对一函数？ 加法：P108 例12 从3个表（分别含23、15、19个候选课题）中选择一个计算机课题，有多少中选择方法？ 集合不相交！ 回顾：基本计数技术 存在性的计数：鸽巢原理 P114 定理1、例3 期末考试给分从0到100，请问：班上必须有多少个学生，才能保证至少有2个学生分数相同？ 物体比盒子恰好多 1 个 P115 定理2、例6 期末考查给分为A、B、C、D、E，请问：班上必须有多少个学生，才能保证至少有6个学生分数相同？ 物体比盒子个数多 回顾：基本计数技术 有序/无序排放的计数：排列、组合 (有序)排列：P119 定理1 (无序)组合：P120 定理2 回顾：基本计数技术 (有序)排列：P120 例7 字母ABCDEFGH有多少种排列包含ABC？ 固定：组成部分 (无序)组合：P122 例14 长为n的二进制串中，有多少个包含r个1？ 组合对应：串的个数?1的位数 回顾：基本计数技术 可重排列：P129 例1 26个英文字母可以构成多少个n位字符串？ 个体重复次数不限 定理1：n 个元素