第1章 排列、组合、二项式定理.docVIP

PAGE 10组合理论及其应用PAGE 11 STYLEREF 标题 1,章名,章 \* MERGEFORMAT 第1章 排列、组合、二项式定理第1章 排列、组合、二项式定理内容提要：本章主要介绍加法原理、乘法原理、排列与组合、多重集合的排列与组合、二项式系数以及一些常见的组合恒等式、集合的分划与第2类Stirling数、正整数的分拆（无序分拆和有序分拆）与分配问题等．排列和组合是人们普遍遇到的、并已被广泛使用的基本概念，只是人们没有从理论上研究它．例如，学生集合站队问题、买水果问题等．如果考虑的对象与秩序有关，则称之为排列问题；如果考虑的对象与秩序无关，则称之为组合问题．除了这种具有普遍意义的排列和组合之外，还有可重复元素的排列和组合问题．为了能深入研究这些问题，下面首先介绍两个最基本最常用的原理．1.1 加法原理（原则）与乘法原理（原则）加法原理（原则） 设事件A有m种选取方式，事件B有n种选取方式，选A或B共有m?+?n种方式．例如，每周在E校区上4节课，在W校区上8节课，除此之外没有别的课，则每周上4 + 8 = 12节课．这里事件A指的是在E校区上4节课，事件B指的是在W校区上8节课，而每周的课不是在E校区就是在W校区，即属于A或B．如果用集合论的语言描述，则描述如下：定理1.1.1 设A，B为有限集，AB = ?，则|?AB?| = |A| + |B|．证明：当A，B中有一个是空集，定理的结论是平凡的． 设A ? ?，B ? ?，记 A = {a1, a 2,, a m} B = {b1, b 2,, b?n}并做映射 ?：ai →i（1 ? i ? m） bj →m+j（1 ? j ? n）因为 ai ? bj (1 ? i ? m, 1 ? j ? n)所以??是从AB到集合{1，2，，m+n}上的一一映射，因而定理成立．推论1.1.1 设n个有限集合S1, S2,?, Sn满足Si?Sj = ? (1??i ? j???n)则 ．【例1】 在所有6位二进制数中，至少有连续4位是1的有多少个？解：把所有满足要求的二进制数分成如下3类：（1）恰有4位连续的1．它们可能是?01111，011110，11110?，其中，“?”取0或1．故在此种情况下，共有5个不同的6位二进制数．（2）恰有5位连续的1．它们可能是011111和111110，共有2个．（3）恰有6位连续的1．即111111，只有1种可能．综合以上分析，由加法原理知共有5+2+1=8个满足题意要求的6位二进制数．乘法原理（原则） 设事件A有m种选取方式，事件B有n种选取方式，则选取A以后再选取B共有m ? n种方式．用集合论的语言可叙述如下：定理1.1.2 设A，B是两个有限集合，|A| = m，|B| = n，则|A ? B| = |A| ? |B| = m ? n．证明：若m = 0或n = 0，则等式两边均为0，故等式成立． 设m 0，n 0，并且记 A = {a1, a2,, am}， B = {b1, b2,, bn}，定义映射 ?：(ai, bj) →（i – 1）n + j?(1 ? i ? m, 1 ? j ? n)，则??是A?B到集合{1, 2,, mn–1, mn}上的一一映射，所以等式成立．推论1.1.2 设S1, S2, , Sn为n个有限集合，则|S1 ? S2 ?? Sn| = |S1|?|S2|??|Sn|.【例2】 比5400大的4位数中，数字2，9不出现，且各位数字不同的数有多少个？解：比5400大的4位数可以分为4类：（1）千位比5大的符合题意的整数有3 ? 7 ? 6 ? 5个．（2）千位是5，百位比4大的符合题意的整数有3 ? 6 ? 5个．（3）前2位是54，十位不为0且符合题意的整数有5 ? 5个．（4）前3位是540，个位不为0且符合题意的整数有5个．故共有3 ? 7 ? 6 ? 5 + 3 ? 6 ? 5 + 5 ? 5 + 5 = 750个符合条件的整数．【例3】 在1000到9999之间有多少个各位数字不同的奇数？解：方法1 如图1.1所示，第4位必须是奇数，可取1，3，5，7，9，共5种选择．第1位不能取0，也不能取第4位已选定的数字，所以在第4位选定后第1位有8种选择．类似地，第2位有8种选择，第3位有7种选择．从而，满足题意的数字共有5 ? 8 ? 8 ? 7 = 2240个．????第1位????第1位第2位第3位第4位图 1.1（1）4位数中没有0出现．类似方法1的分析，第4位有5种选择，第3位有8种选择，第2位有7种选择，第1位有6种选择