复旦大学：《离散数学——组合数学》电子讲义_第六章 排列与组合（吴永辉）

第6章排列与组合 6.1基本计数原理 62集合的排列 63集合的组合 64多重集的排列和组合 6.5容斥原理

第6章 排列与组合  6.1 基本计数原理  6.2 集合的排列  6.3 集合的组合  6.4 多重集的排列和组合  6.5 容斥原理

6.1基本计数原理 ■组合数学在研究记数时经常要用到最基 本的原理:加法原理和乘法原理

6.1 基本计数原理  组合数学在研究记数时经常要用到最基 本的原理：加法原理和乘法原理

11.1基本计数原理 1加法原理 ■1)定理6.1(加法原理) 设A和B是有限集合的两个互不相 交的子集,且AB=5,则|5=|A4|+|6 /*划分*

11.1 基本计数原理  1 加法原理  1）定理6.1（加法原理）  设A和B是有限集合S的两个互不相 交的子集，且AB=S，则|S|=|A|+|B|。  /*划分*/

■证明:集合S中的元素在子集A中的个数 有|A个,因为A和B互不相交,且AB=S, 故元素不在中必在砷,且B元素 不在冲,所以中不在A中的元素有|6 个,即|S=|A|+|6

 证明：集合 S中的元素在子集 A中的个数 有|A|个，因为 A和 B互不相交，且 AB=S， 故 S中元素不在 A中必在 B中，且 B中元素 不在 A中，所以 S中不在 A中的元素有|B| 个，即|S|=| A|+| B|

2)加法原理实例: ■北京每天直达上海的客车有5次,客机 有3次,则每天由北京直达上海的旅行 方式有5+3=8种

 2）加法原理实例：  北京每天直达上海的客车有 5 次，客机 有 3 次， 则每天由北京直达上海的旅行 方式有 5 + 3 = 8 种

■2乘法原理 ■1)定理6.2(乘法原理) 设A和E是有限集合,|4=p, B=q,则:|A=pq

 2 乘法原理  1）定理6.2（乘法原理） 设A和B是有限集合，|A|=p， |B|=q，则: |AB|=pq

2)乘法原理实例: 从A到B有三条道路,从BC有两条道路,则 从陉经C有3x2=6条道路

 2）乘法原理实例：  从A到B有三条道路，从B到C有两条道路，则 从A经B到C有32=6条道路

3例6.1 ■某学生从2门数学课和4门计算机课中任 选一门,则有2+4=6种选修方法, /要送一/数学课或一门计算机课,但 两者不同的都选,2门数学课和4门计算 机课为该生的选课范围,则该生能以 2+4=6种选修方法选择一门课。为

 3 例6.1  某学生从2门数学课和4门计算机课中任 选一门，则有2+4=6种选修方法。  /*要选一门数学课或一门计算机课，但 两者不同时都选，2门数学课和4门计算 机课为该生的选课范围，则该生能以 2+4=6种选修方法选择一门课。*/

■若他要选数学课和计算机课各一门,则 有2x4=8种选修方法

 若他要选数学课和计算机课各一门，则 有 2 4=8种选修方法

乘法原理可被推广到3,4或任意有限多个 集合的情形。 例:梅利莎病毒:通过以含恶意宏的字 处理文档为附件的电子邮件传播。当字 处理文档被打开时,宏从用户的地址簿 中找到前50个地址,并将字处理文档为 附件发给它们。 病毒按乘法原理飞快地扩款为

 乘法原理可被推广到3, 4或任意有限多个 集合的情形。  例：梅利莎病毒：通过以含恶意宏的字 处理文档为附件的电子邮件传播。当字 处理文档被打开时，宏从用户的地址簿 中找到前50个地址，并将字处理文档为 附件发给它们。  /*病毒按乘法原理飞快地扩散*/