南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 09 计数

计数

计数 1

本节提要 口内容1:容斥原理 口内容2:鸽笼原理 口内容3:排列与组合

 内容1：容斥原理  内容2：鸽笼原理  内容3：排列与组合 本节提要

两个有限集合并集的计数 已知某个班级学英语的50 人,学法语的30人,分别 F 记为: E⌒F E|=50;|F|=30 问这个班级一共多少人? 显然,只要E∩地,班级 人数就并非80人。 既学英语,又学法语的同学F|=(E|+FED=EAF

两个有限集合并集的计数 既学英语，又学法语的同学 E F EF 已知某个班级学英语的50 人，学法语的30人，分别 记为： |E| = 50; |F| = 30 问这个班级一共多少人？ 显然，只要EF，班级 人数就并非80人。 |EF| =(|E|+|F|) - |EF|

数字排列的例子 口将0,1,2,,9排成一列,要求第1个数字大于1,最后一 个数字小于8,共有多少种排法? 口这10个数字所有的排法构成全集U,|U|=10 口第1个数字不大于1的排法构成子集A(即所有以0或者1开头的排法), A|=2·9 口最后一个数字不小于8的排法构成子集B(即所有以8或者9结束的 排法),|B|=2·9 口|A∩B|=2·28 口题目要求的排法构成子集(~A∩~B) a|(~A∩~B)|=|U|-|AUB|=|U|-|A|-|B|+|A∩B|=10 -4◆9!+4◆8!=2338560

数字排列的例子  将0,1,2,...,9排成一列，要求第1个数字大于1，最后一 个数字小于8，共有多少种排法？  这10个数字所有的排法构成全集U, |U|=10!  第1个数字不大于1的排法构成子集A(即所有以0或者1开头的排法), |A|=29!  最后一个数字不小于8的排法构成子集B(即所有以8或者9结束的 排法), |B|=29!  |AB|=228!  题目要求的排法构成子集(~A~B)  |(~A~B)| = |U| - |AB| = |U| -|A| - |B| + |AB| = 10! - 49! + 48! = 2,338,560

三个有限集合并集的计数 口假设定义全集的三个子集ABC则: A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|ABC 证明: A∪B∪C|=|A∪B|+|C|-|(A∪B∩C =|A|+|B|-|A⌒B|+|C|-|(A⌒C∪(B⌒C =|A|+|B|-|A^B|+|C|-|(A⌒C|-|B∩O|+|AB∩O =|A|+|B|+|C|-|A^B|-|A⌒C|-|B⌒C|+|AB⌒C

三个有限集合并集的计数  假设定义全集的三个子集A,B,C。则： |ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC| 证明： |ABC|=|AB|+|C|-|(AB)C| =|A|+|B|-|AB|+|C|-|(AC)(BC)| =|A|+|B|-|AB|+|C| - |(AC)|-|(BC)|+|(ABC)| =|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|