1、第三章 排列与组合3.1 两个基本计数原理集合的划分若 S1, S2 , , Sm均是集合 S的子集，且同时满足： Si Sj （ i j） S1 S2 Sm S 则称 S1, S2 , , Sm是集合 S的一个 划分 。于 “ 离散数学 ” 中的划分定义一样：不重叠分干分净。1一、 加法原理设 S1, S2 , , Sm是集合 S的一个划分，则S= S1+ S2 + + Sm其中 S表示 S中元素的个数注意，加法原理的前提条件 “划分 ”是重要的，它强调了集合 S的各个子集不允许重叠。对于可能重叠的情况，我们将在第 6章容斥原理中进行讨论 ,这里的集合元素已经是广义的。2设 A， B为两个不
2、同类事件，若事件 A有 m种 产生方式，事件 B有 n种产生方式，则“事件 A或者事件 B”有 m+n种产生方式。加法原理的通俗说法是：部分之和等于全体 。 约束条件是： (1) 讨论范围局限于有限集；(2) 任意两个部分都不相交。3例 1 小于 100的正偶数有 49个 ,小于 100的正奇数有 50个 ,则小于 100的正整数有 49+50=99个 . 例 2 某班选修 “企业管理 ”的有 18 人 ,不选的有 10人 , 则该班共有 18 + 10 = 28 人。例 3 北京每天直达上海的客车有 5 次，客机有 3 次， 则每天由北京直达上海的旅行方式有 5 + 3 = 8 种。4二 乘
3、法原理 设 S1, S2 是两个集合，现根据 S1， S2定义集 合 S如下：S = S1 S2 =(x,y) x S1 y S2 则 : S = S1S2要精通加法原理和乘法原理，可以通过尝试解决大量问题来实现。 5设 A， B为二不同类事件，若事件 A有 m种产生 方式，事件 B有 n种产生方式，则 “事件 A与事件 B” 有 mn种产生方式 用集合论的术语，乘法原理也可描述如下： 设 S， T为二集，若 S为 m元集， T为 n元集，则S与 T的叉积之集合 ST为 mn元集。例 1 从 u到 v有 3条不同的道路 ,从 v到 w有 2条不同的道路 ,则从 u经 v到 w有 32=6条不同
4、的道路 .6例 2 某高级语言的标识符规定长度最多为 6位，其中第一位限取字母，其余各位可取字母， 也可取数字。 求所有可能出现的标识符总数。 解 :长为 1的只有 26个 ;长为 2的由乘法原理有26(26+10)个； 长为 6的由乘法原理有26(26+10)5个。最后由加法原理，所有可能出现的标识符 总数为 : 7例 3 用四子于两路棋盘 ,能摆出 34=81种两两不同的棋局； 用九子于三路棋盘，能摆出 39=19683种两两不同的棋局；用 16子于四路棋盘，能摆出 316=43 046 721种两两不同的棋局，用 25子于五路棋盘，能摆出 325=847 288 609 443种两两不同
5、的棋局； 用 361子于十九路棋盘，能摆出 3361种两两不同的棋局。 注 : 本例指围棋，现代围棋采用十九路，即有1919=361个交叉点可落黑子、 白子或留 空 。8例 4从包括五本不同的计算机书，三本不同的数学书和两本不同的美术书中，选择两本不同的书有多少种方法？运用乘法原理，我们发现可以选择两本书，一本计算机书和一本数学书，有 53=15种方法。同理，我们也可以选择一本计算机书和一本美术书，有 52=10种方法。我们也可以选择一本数学书和一本美术书，有 32=6种方法。因为这些选法的集合互不相交，所以我们可以用加法原理得出共有 15+10+6=31种方法从不同的计算机书、数学书和美术书选择两本。9例 5 求含有数字 1的 4位数的个数。 解 先求不含有 1的 4位数的个数，即求由 0, 2, 3, 4, 5, 6, 7, 8, 99个数字组成的 4位数的个数（第一位不得出现 0）。由乘法原理，有 8999=5832个又 4位数共有 9999-999=9000个。 因此 , 含有数字 1的 4位数的个数为 9000-5832=3168。 注： 本例中用到了一种求补原理。提法是： 由总数中去掉不满足某些性质的物件数，则剩余者即为满足该性质的物件总数。10
