组合数学2015_02.pptVIP

第2章 排列与组合 §2.1 加法法则和乘法法则（1） §2.1 加法法则和乘法法则（2） §2.1 加法法则和乘法法则（3） §2.1 加法法则和乘法法则（3） §2.2 排列（1） §2.2 排列（2） §2.2 排列（3） §2.2 排列（4） §2.2 排列（5） §2.2 排列（6） * 主讲教师：王新红 办公电话：0531部 门：软件教研中心（新信息楼803） 组合数学课件 Email地址： ise_wangxh@ujn.edu.cn 本章重点介绍以下的基本计数方法： 加法法则和乘法法则 排列 组合 二项式定理的应用 §2.1 加法法则和乘法法则 2.1.1 加法法则 加法法则 相互独立的事件 A、B 分别有 k 和 l 种方法产生，则产生 A 或 B 的方法数为 k+l 种。 集合论定义 若|A|=m，|B|=n ，且A∩B=Φ ，则|A∪B| = m+n 。 例 题 例1、有一所学校给一名物理竞赛优胜者发奖，奖品有三类，第一类是三种不同版本的法汉词典；第二类是四种不同类型的物理参考书；第三类是二种不同的奖杯。这位优胜者只能挑选一样奖品。那么，这位优胜者挑选奖品的方法有多少种？ 例2、大于0小于10的奇偶数有多少个？ 例3、小于20可被3或6整除的自然数有多少个？ 解：设S是所有这些奖品的集合，Si是第i类奖品的集合(i=1,2,3)，显然，Si∩Sj=Φ (i≠j) ，根据加法法则有 解：设S是符合条件数的集合，S1、S2分别是符合条件的奇数、偶数集合，显然，S1∩S2=Φ ，根据加法法则有 §2.1 加法法则和乘法法则 2.1.2 乘法法则 乘法法则 相互独立的事件 A、B 分别有 k 和 l 种方法产生，则产生 A 与 B 的方法数为 k×l 种。 集合论定义 若|A|=m，|B|=n ，A×B={(a,b)|a∈A，b∈B}， 则|A×B| = m×n 。 例 题 例4、从A 地到B地有二条不同的道路，从B地到C地有四条不同的道路，而从C地到D地有三条不同的道路。求从A地经B、C两地到达D地的道路数。 例5、由数字1,2,3,4,5可以构成多少个所有数字互不相同的四位偶数？ 例6、求出从8个计算机系的学生、 9个数学系的学生和10个经济系的学生中选出两个不同专业的学生的方法数。 解：设S是所求的道路数集合，S1、S2、S3分别是从A到B、从B到C、从C到D的道路集合，根据乘法法则有 解：所求的是四位偶数，故个位只能选2或4，有两种选择方法；又由于要求四位数字互不相同，故个位选中后，十位只有四种选择方法；同理，百位、千位分别有三种、两种选择方法，根据乘法法则，四位数互不相同的偶数个数为 2×4×3×2=48 解：由乘法法则有 选一个计算机系和一个数学系的方法数为8×9=72 选一个数学系和一个经济系的方法数为9×10=90 选一个经济系和一个计算机系的方法数为10×8=80 由加法法则，符合要求的方法数为 72+90+80=242 §2.1 加法法则和乘法法则 练习： 练习1、求小于10000的含1的正整数的个数 练习2、求小于10000的含0的正整数的个数 练习1 解法1：小于10000的正整数可看作0，1，2，3，4，5，6，7，8，9中取4个数构成的4位数,但0000除外. 故根据乘法法则共有104－1＝9999个 同理，小于10000的不含1的正整数的个数应为 94-1=6561-1=6560 故小于10000并且含1的正整数的个数为 9999－ 6560＝3439 解法2：全部4位数有104个,不含1的四位数有94个 则含1的4位数个数为两个的差: 104－94 = 3439 练习2 解：不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个 不含0小于10000的正整数有 9+92 +93 +94 =(95－1)/(9－1)=7380个 含0小于10000的正整数有 9999－7380=2619个 练习3、在1000到9999之间有多少个各位数字不同的奇数？ 练习3解： 第4位必须是奇数，可取1，3，5，7，9,共有5种选择 第1位不能取0，也不能取第4位已经选定的数字， 所以在第4位选定后第1位有8种选择 第2位不能取第1位，4位已经选定的数字，共有8种选择 类似地，第3位有7种选择 从而满足题意的数共有5?8?8?7＝2240个 还有没有其他解法？ 练习4、n=73 ? 112 ? 134,求除尽n的数的个数。 练习4解： 除尽n的数可以写成 故除尽n