组合数学--1.1加法原则与乘法原则

第1章基本计数问题1.1加法原则与乘法原则1.2集合的排列与组合1.3重集的排列与组合1.4分配问题1.5排列的生成算法1.6组合的生成算法1.7二项式系数1.8二项式定理的推广1.1加法原则与乘法原则加法原则（additionprinciple）全体等于它各部分和把集合S划分为S1,S2,…,Sn这n块，则︱S︱＝︱S1︱＋︱S2︱＋…＋︱Sn︱注意，运用加法原则，把要计数的集合S划分成不太多的易于处理的块S1,S2,…,Sn1.1加法原则与乘法原则乘法原则（multiplicationprinciple）如果某事件能分成连续n步完成，第一步有r1种方式完成，且不管第一步以何种方式完成，第二步都始终有r2种方式完成，而且无论前两步以何种方式完成，第三步都始终有r3种方式完成，以此类推，那么完成这件事共有r1×r2×…×rn种方式注意，运用乘法原则，后步结果可随前步结果而变化，但每一步完成方式的数量却是固定不变，不依赖任何一步。1.1加法原则与乘法原则例1.1.1在1000到9999之间有多少个各位数字不同的奇数？1.1加法原则与乘法原则解分四步：5×8×8×7＝2240百位千位十位个位可取1，3，5，7，9共5种选择不能取0，也不能取个位已选定的数字，始终有8种选择有8种选择有7种选择1.1加法原则与乘法原则思考分以下四步？百位千位十位个位有几种选择？5？4？不能取0，有9种选择有9种选择有8种选择1.1加法原则与乘法原则例1.1.2用a,b,c,d,e,f做三字母串，字母重复且要包含字母e，共构成多少个？1.1加法原则与乘法原则解一符合题意的三字母串可分成三类：(1)形如e□□，乘法原则，共有6×6＝36个;(2)形如□e□，为与第一类不同，第一位置不能取e，乘法原则，共有5×6＝30个;(3)形如□□e，为与第一、二类均不同，第一、二位置都不能取e，乘法原则，共有5×5＝25个。加法原则，共有36＋30＋25＝91个1.1加法原则与乘法原则解二符合题意的三字母串可分成三大类：(1)含一个e,再分为三类(2)含两个e,再分为三类(3)含三个e，即eee这1个。加法原则，共有25＋25＋25＋5＋5＋5＋1＝91个个，共形如个，共形如个，共形如2555e2555e2555e个，共形如个，共形如个，共形如5ee5ee5ee1.1加法原则与乘法原则例1.1.3把2n个人分成n组，每组2人，有多少种不同的分组方法？1.1加法原则与乘法原则解把2n个人按题意要求分组的不同分组方法数计作an，显然a1＝1。按两步完成分组：(1)确定与甲同组的人,有＝2n－1种方法(2)把剩下的2n－2个人按题意要求进行分组，有an-1种方法由乘法原则，有an＝(2n－1)an-1C11n21.1加法原则与乘法原则而an＝(2n－1)an-1＝(2n－1)(2n－3)an-2＝(2n－1)(2n－3)(2n－5)an-3＝…＝(2n－1)(2n－3)(2n－5)…3a1＝(2n－1)×(2n－3)×(2n－5)×…×3×1＝!n)!n2(2n1.1加法原则与乘法原则例1.1.4某停车场有6个入口处，每个入口处每次只能通过一辆汽车。有9辆汽车要开进停车场，试问有多少种入场方案？1.1加法原则与乘法原则解可分9步确定入场方案：(1)确定第1辆车的入场方案，有6个入口可选择，有6种入场方案。(2)确定第2辆车的入场方案，不论第1辆车从哪个入口进场，第2辆车仍有6个入口可选择，但当它选择与第1辆车相同入口入场时，有在第1辆车前后两种方式，因而共有7种入场方案。(3)确定第3辆车的入场方案，共有8种入场方案。……乘法原则，有6×7×8×…×14＝726485760种方案