组合数学第三章(1)

1、2021-6-29计算机科学与技术学院1 第三章第三章 基本计数原理基本计数原理 n3.1 加法原则与乘法原则加法原则与乘法原则 n3.2 排列与组合排列与组合 n3.3 排列和组合的生成排列和组合的生成 n3.4 二项式系数二项式系数 n3.5 集合的分划与第二类集合的分划与第二类Stirling数数 n3.6 正整数的分拆正整数的分拆 n3.7 分配问题分配问题 2021-6-29计算机科学与技术学院2 加法原理加法原理 (1) 加法原理加法原理 如果有如果有p1种不同方法能够从种不同方法能够从 一堆物体中选择出一个物体，有一堆物体中选择出一个物体，有p2种不同种不同 方法能够从另一堆物体

2、中选择出一个物体方法能够从另一堆物体中选择出一个物体 ，那么从两堆物体中选择出一个物体的方，那么从两堆物体中选择出一个物体的方 法共有法共有p1+p2种。种。 2021-6-29计算机科学与技术学院3 推广形式推广形式 如果有p1种不同方法能够从第1堆物体中 选择出一个物体，有p2种不同方法能够第 2堆物体中选择出一个物体，有pn种 不同方法能够第n堆物体中选择出一个物 体，那么从这n堆物体中选择出一个物体 的方法共有p1+p2+pn种 2021-6-29计算机科学与技术学院4 集合表达形式集合表达形式 设集合 ，且对任意的 1in时，时， P(n,r)0。 n0！1 nP(n,0)=1 nP

3、(n,n)=n! 2021-6-29计算机科学与技术学院17 相异元素不允许重复的组合数相异元素不允许重复的组合数 定义定义 从从n元集元集S中无序地取出中无序地取出r个元素，叫做个元素，叫做S的一个的一个r- 组合组合。不同组合的总数记作。不同组合的总数记作C(n,r)。 nC(n,0) =1,n 0 nrn时，有时，有C(n,r) =0 nC(n,0)=C(n,n)=1 n若若0 r n，则，则C(n,r)= C(n,n-r) 2021-6-29计算机科学与技术学院18 (4) 的组合意义 是n元集合S的r元子集的个数， 是集合S的n-r元子集的个数. 设A是S的r元子集，则S-A是S的n

4、-r元子集， 这种对应关系显然是一一的。即S的r元子集的 个数等于S的n-r元子集的个数 r n rn n 2021-6-29计算机科学与技术学院19 集合排列组合问题抽象为分配问题 n 将r个有区别的小球放入n个不同的盒子，每 盒不超过一个，则总的放法为P(n,r)。 n 同样，若小球不加以区别，则有种 放法。 r n 2021-6-29计算机科学与技术学院20 相异元素不重复排列数和组合数相异元素不重复排列数和组合数 2021-6-29计算机科学与技术学院21 相异元素不重复排列数和组合数相异元素不重复排列数和组合数 2021-6-29计算机科学与技术学院22 相异元素不重复排列数和组合数

5、相异元素不重复排列数和组合数 2021-6-29计算机科学与技术学院23 相异元素不重复排列数和组合数相异元素不重复排列数和组合数 2021-6-29计算机科学与技术学院24 例例3.2.4 把把10个有区分的小球放到个有区分的小球放到5个个 不同的盒子中，如果要求每个盒子中的不同的盒子中，如果要求每个盒子中的 小球有次序之分，求有多少种不同的放小球有次序之分，求有多少种不同的放 法法 相异元素不重复排列数和组合数相异元素不重复排列数和组合数 2021-6-29计算机科学与技术学院25 解：方法解：方法1 分析把分析把10个小球一一放到个小球一一放到5个盒子中的所有情况个盒子中的所有情况 12

6、 3 3 3 3 3 3 3 1 2 2 2 2 2 2 相异元素不重复排列数和组合数相异元素不重复排列数和组合数 !4 !14 14765 12 3 3 3 3 3 3 3 2021-6-29计算机科学与技术学院26 解：方法解：方法2 分析用分析用4个分隔符把个分隔符把10个小球分个小球分 割成割成5堆的情况堆的情况 * * * * * * * * * * 3 5 9 12 相异元素不重复排列数和组合数相异元素不重复排列数和组合数 ! 4 !14 2021-6-29计算机科学与技术学院27 相异元素不重复排列数和组合数相异元素不重复排列数和组合数 12n-1n 2021-6-29计算机科学

7、与技术学院28 n在证明组合等式时不是进行代数推导，而是对等式所在证明组合等式时不是进行代数推导，而是对等式所 代表的组合意义进行分析，通过建立一一对应的方法代表的组合意义进行分析，通过建立一一对应的方法 说明等式两边恰好是对同一组合模型进行计数。说明等式两边恰好是对同一组合模型进行计数。 n这种组合分析的方法是很有用的，请看下面的例子。这种组合分析的方法是很有用的，请看下面的例子。 组合分析的方法组合分析的方法 2021-6-29计算机科学与技术学院29 相异元素不重复排列数和组合数相异元素不重复排列数和组合数 2021-6-29计算机科学与技术学院30 作业作业 npp. 82, 3.4,

8、 3.5 2021-6-29计算机科学与技术学院31 相异元素不允许重复的圆排列相异元素不允许重复的圆排列 2021-6-29计算机科学与技术学院32 定理定理3.2.1 一个n元集S的圆r-排列数是 P(n, r)/r = n!/r(n-r)! 如果rn，则S的圆排列数是(n-1)! 证明证明 我们把我们把S的所有的线形的所有的线形r-排列分成组，使得同组的排列分成组，使得同组的 每个线形排列可以连接成同样的圆排列。因为每组中恰每个线形排列可以连接成同样的圆排列。因为每组中恰 含有含有r个线形排列，所以个线形排列，所以S的圆的圆r-排列数排列数 Np(n,r)/r， 当当rn时，时，S的圆排

9、列数为的圆排列数为p(n,n)/n(n-1)!。 12r-1r 2r 13 r1r-1r-2 相异元素不允许重复的圆排列相异元素不允许重复的圆排列 2021-6-29计算机科学与技术学院33 例例3.2.7 10个人围坐圆桌旁聚餐，如果个人围坐圆桌旁聚餐，如果A和和B不能相邻，不能相邻， 则不同的坐法有多少种？则不同的坐法有多少种？ 解解 不考虑限制条件，不考虑限制条件，10个人的圆排列数为个人的圆排列数为9！，考虑！，考虑A 和和B相邻的情况，有两种情形相邻的情况，有两种情形A在在B的左侧和的左侧和A在在B的右的右 侧，则侧，则A和和B相邻的圆排列数为相邻的圆排列数为28！，所以不同的坐！，

10、所以不同的坐 法有法有9！-28！=78！=282240种。种。 相异元素不允许重复的圆排列相异元素不允许重复的圆排列 12910 2021-6-29计算机科学与技术学院34 例例3.2.8 将将5个不同颜色的珠子串成一条项链，能够串个不同颜色的珠子串成一条项链，能够串 成多少不同的项链？成多少不同的项链？ 解解首先我们考虑首先我们考虑5个元素的圆排列问题，根据定理个元素的圆排列问题，根据定理 3.2.1有有4！=24个不同个不同5-圆排列。但这个问题很特殊，圆排列。但这个问题很特殊， 因为项链可以翻转但不影响珠子的相对位置，即每因为项链可以翻转但不影响珠子的相对位置，即每2个个 圆排列对应同

11、一个项链，因此能够串成圆排列对应同一个项链，因此能够串成12个不同的项链。个不同的项链。 相异元素不允许重复的圆排列相异元素不允许重复的圆排列 2021-6-29计算机科学与技术学院35 l 排列的生成方法排列的生成方法 l (a) 邻位互换法邻位互换法 l (b) 字典序法字典序法 l 组合的生成方法组合的生成方法 l (a) 生成集合生成集合I=1,2,n的所有组合的所有组合 l (b) 生成集合生成集合I=1,2,n 的所有的所有r-组合组合 集合排列和组合的生成集合排列和组合的生成 2021-6-29计算机科学与技术学院36 排列的生成排列的生成 n全排列的生成算法就是对于给定的字符集

12、，用 有效的方法将所有可能的全排列无重复无遗漏 地枚举出来。 n (a) 邻位互换法 n (b) 字典序法 2021-6-29计算机科学与技术学院37 邻位互换法邻位互换法 n基本思想是递归地对集合基本思想是递归地对集合1,2,n-1的的(n-1)!个排列的个排列的 每一个排列每一个排列, 通过把通过把n插入到首、尾和任两个数的中间插入到首、尾和任两个数的中间 共共n个位置，产生集合个位置，产生集合1,2,n的的n个排列，从而产生个排列，从而产生 n (n-1)!=n!个集合个集合1,2,n的排列。的排列。 n 2021-6-29计算机科学与技术学院38 邻位互换法邻位互换法 12 21 12

13、3 132 312 321 231 213 N=2 N=3 N=1 1 2021-6-29计算机科学与技术学院39 邻位互换法邻位互换法 1234 1243 1423 4123 4132 1432 1342 1324 3124 3142 3412 4312 4321 3421 3241 3214 2314 2341 2431 4231 4213 2413 2143 2134 N=4 2021-6-29计算机科学与技术学院40 活动整数定义：活动整数定义： 对任一给定整数对任一给定整数k, 其上加一个箭头表示移动方向其上加一个箭头表示移动方向 , 或或 . 对于集合对于集合1,2,n的任一个排列

14、的任一个排列, 其中每一个整其中每一个整 数都有一个箭头指出其移动方向数都有一个箭头指出其移动方向, 若整数若整数k的箭头指向的箭头指向 与其相邻但比它小的整数与其相邻但比它小的整数, 称称k是活动的是活动的. 举例：举例： 邻位互换法邻位互换法 k k 451362 2021-6-29计算机科学与技术学院41 邻位互换法邻位互换法 n算法算法3.1 邻位互换法生成邻位互换法生成1,2 ,n的所有排列的所有排列 n输入：输入：n n输出：输出：1,2,n的所有n!个全排列 n步骤步骤1：初始化，设 ，输出P； n步骤步骤2：考虑排列P，若排列中无一处于活动状态，则 停止； n步骤步骤3：求所有

15、处于活动状态的数中的最大者，设为 pm。pm和它的箭头所指的一侧的相邻数互换位置，输 出P； n步骤步骤4：令比m大的所有数的箭头改变方向，转步骤2. npppP n 21 21 当当n=4时，算法生成各个排列的顺序时，算法生成各个排列的顺序 2021-6-29计算机科学与技术学院42 邻位互换法邻位互换法 1 2 3 4 1 2 4 3 1 4 2 3 4 1 2 3 4 1 3 2 1 4 3 2 1 3 4 2 1 3 2 4 3 1 2 4 3 1 4 2 3 4 1 2 4 3 1 2 4 3 2 1 3 4 2 1 3 2 4 1 3 2 1 4 2 3 1 4 2 3 4 1 2

16、 4 3 1 4 2 3 1 4 2 1 3 2 4 1 3 2 1 4 3 2 1 3 4 2021-6-29计算机科学与技术学院43 字典序法字典序法 n 对给定的字符集中的字符规定了一个先对给定的字符集中的字符规定了一个先 后关系，在此基础上规定两个全排列的后关系，在此基础上规定两个全排列的 先后是从左到右逐个比较对应的字符的先后是从左到右逐个比较对应的字符的 先后。先后。 2021-6-29计算机科学与技术学院44 字典序法字典序法 n例字符集字符集1,2,3,1,2,3,较小的数字较先较小的数字较先, ,这样按这样按 字典序生成的全排列是字典序生成的全排列是: : n123,132,

17、213,231,312,321123,132,213,231,312,321。 一个全排列可看做一个字符串，字 符串可有前缀前缀、后缀后缀。 2021-6-29计算机科学与技术学院45 字典序法字典序法 高度为4的树 2021-6-29计算机科学与技术学院46 字典序法字典序法 生成给定全排列的下一个排列生成给定全排列的下一个排列 所谓所谓一个的下一个就是就是这一个与与下一个之间之间没有其 他的。这就要求这一个与下一个有尽可能。这就要求这一个与下一个有尽可能长的的共同 前缀，也即变化限制在尽可能，也即变化限制在尽可能短的的后缀上。上。 2021-6-29计算机科学与技术学院47 按从树根到树叶

18、读各边的标号顺序得一个排列，按从树根到树叶读各边的标号顺序得一个排列， 自左至右依次为自左至右依次为 1234，1243，1324，1342，1423，1432， 2134，2143，2314，2341，2413，2431， 3124，3142，32143241，3412，3421， 4123，4132，4213，4231，4312，4321 它是按它是按“字典字典”的顺序排列的，的顺序排列的， 由排列由排列P1P2Pn生成下一个排列的算法如下：生成下一个排列的算法如下： 字典序法字典序法 2021-6-29计算机科学与技术学院48 字典序排列生成算法任务解析字典序排列生成算法任务解析 n找到

19、第一个需要交换的数的位置 n找到第二个需要交换的数的位置 n交换后处理 2021-6-29计算机科学与技术学院49 排列字典序定义排列字典序定义 集合1,2,n上的字典序关系“L”， 对于 和 是集合1,2,n上的两个排列， 则从左向右扫描，当出现第一个元素不同的位置 （不妨设为第i个位置）时： 如果 则定义 L n ppp 21n qqq 21 ii qp n ppp 21n qqq 21 2021-6-29计算机科学与技术学院50 字典序排列生成算法字典序排列生成算法 2021-6-29计算机科学与技术学院51 例：例： P1P2P3P4=3421 (a) i=maxj| Pj-1Pj=2

20、 (b) j=maxk| Pi-1Pk=2 (c) P1与P2互换得4321 (d) 4321中的321的顺序逆转得排列： 4123 字典序法字典序法 2021-6-29计算机科学与技术学院52 组合字典序定义组合字典序定义 n设两个n元组an-1an-2a1a0和n元组bn-1bn-2b1b0，从左至 右比较两个n元组，当出现第一个元素不同的位置时， 例如，第j个位置，若 naj0, bj1：n元组an-1an-2a1a0出现在n元组bn-1bn- 2b1b0的前面； naj1, bj0：n元组an-1an-2a1a0出现在n元组bn-1bn- 2b1b0的后面； 2021-6-29计算机科

21、学与技术学院53 集合集合 1，2，3字典序组合输出字典序组合输出 子集子集 元素元素 123 000 3001 2010 2，3011 1100 1，3101 1，2110 1，2，3111 2021-6-29计算机科学与技术学院54 生成集合生成集合I=1,2,n的所有组合的所有组合 2021-6-29计算机科学与技术学院55 生成集合生成集合I=1,2,n的所有的所有r-组合组合 举例：举例：生成集合生成集合1，2，3，4，5，6的所有的所有4组合组合 n1234，1235，1236，1245，1246，1256， n1345，1346 ，1356, n1456 n2345，2346 ，

22、2356 n2456, n3456 设从1,n中取r元的组合全体为C(n,r). n不妨设C1C2Cr n i Ci (nr+i), i=1,2,r 2021-6-29计算机科学与技术学院56 生成集合生成集合I=1,2,n的所有的所有r-组合组合 2021-6-29计算机科学与技术学院57 多重集多重集 n 多重集中可以有重复的元素。这是对普通集合 的扩展 n多重集的排列，包括多重集 r-排列和全排列 n多重集的组合，多重集r-组合 例子例子 M 表示为表示为 n是一个是一个10个元素的多重集合，个元素的多重集合， n其中有其中有3个个a，1个个b，2个个c，4个个d. ddddccbaaa

23、M, dcbaM4 ,2 ,1 ,3 2021-6-29计算机科学与技术学院58 多重集多重集 2021-6-29计算机科学与技术学院59 多重集合的排列多重集合的排列 定定理理 3.2.2 多多重重集集合合12,nMaaa 的的 r 排排列列数数 为为 nr。 证证明明 在在构构造造 M 的的一一个个 r 排排列列时时，第第一一项项有有 n 种种选选择择，第第二二 项项有有 n 种种选选择择，第第 n 项项有有 n 种种选选择择.由由于于 M 中中的的每每个个元元素素 都都是是无无限限地地重重复复，所所以以 r 排排列列中中的的任任一一项项都都有有 n 种种选选择择，且且不不 依依赖赖于于前

24、前面面各各位位的的选选择择，故故 M 的的 r 排排列列数数为为 nr 这这是是对对应应的的数数学学模模型型是是将将 r 个个有有区区别别的的球球放放入入 n 个个不不同同的的盒盒 子子，每每盒盒的的球球数数不不加加以以限限制制，而而且且同同盒盒的的球球不不分分次次序序。 由由上上面面的的证证明明易易知知，若若 M 中中每每个个元元素素的的重重数数至至少少为为 r，则则定定 理理的的结结论论仍仍然然成成立立。 2021-6-29计算机科学与技术学院60 多重集合的排列多重集合的排列 n这个问题对应的分配问题模型是：将r个有区别 的球放入n个不同的盒子中，且每个盒子的球 数不加以限制，而且同盒的

25、球不分次序，则不 同的放法为nr种 2021-6-29计算机科学与技术学院61 多重集合的排列多重集合的排列 n推论推论 设多重集 且对一切 则S的r-排列数为nr。 n 例例 求不多于四位的二进制数的个数。 解解 这个问题相当于多重集 的4-排列问题。由定理3.2.2，所求的二进制数的个数N 2416。 1122 ,., nn Sk a kaka 1,2,., i inkr有 1, 0S 2021-6-29计算机科学与技术学院62 多重集合的排列多重集合的排列 2021-6-29计算机科学与技术学院63 多重集合的排列多重集合的排列 n例3.3.2 使用英文字母表中使用英文字母表中26个字母

26、构成个字母构成8个字母的单词，个字母的单词，且且 允许字母重复允许字母重复，如果要求，如果要求 每个单词至少含有每个单词至少含有3个元音字母，那么能构成多少个这样的单个元音字母，那么能构成多少个这样的单 词？词？ 解解 不考虑元音情况：不考虑元音情况： 有有0个元音字母的单词有个元音字母的单词有 有有1个元音字母的单词有个元音字母的单词有 有有2个元音字母的单词有个元音字母的单词有 根据加法原理共根据加法原理共 71 215 1 8 8 21 627188 215 2 8 215 1 8 2126 62 215 2 8 8 26 2021-6-29计算机科学与技术学院64 多重集合的排列多重集

27、合的排列 2021-6-29计算机科学与技术学院65 多重集合的排列多重集合的排列 例3.3.3 求多重集 的8-排列数 分析： （1）目前已知的多重集排列公式 （2）多重集的元素个数 （3）每个元素的重复度均小于所求 （4）构造满足公式所求的多重集 cbaM4 ,2 ,3 9423M 2021-6-29计算机科学与技术学院66 解 可分三种情况计算： n M-a的8-排列数, 即为 排列数 为： n M-b的8-排列数,即为 排列数 为： n M-c的8-排列数,即为 排列数 为： n 多重集M的8-排列数为 420+280+560=1260 cbaM4 ,2 ,3 cba4 ,2 ,2 4

28、20 ! 4 ! 2 ! 2 ! 8 cba4 ,1 ,3 280 ! 4 ! 1 ! 3 ! 8 cba3 ,2 ,3 8! 560 3!2!3! 多重集合的排列多重集合的排列 2021-6-29计算机科学与技术学院67 多重集合的排列多重集合的排列 例3.3.4 从4个a，4个b，4个c，4个d 中选择字母形成一个10个 字母的序列，如果每个字母至少出现两次，有多少种方法形成 这样的序列 ？ dcbaM4 ,4 ,4 ,4 164*4M dcbaM2 ,2 ,2 ,2 * 2021-6-29计算机科学与技术学院68 （一）（一） 的的10-排列数排列数; 的的 10-排列数；排列数； 的的

29、10-排列数：排列数： 的的10-排列数，排列数， 这这4种类情况的种类情况的10-排列数相等，均为排列数相等，均为 2 * aM 2 * bM 2 * cM 2 * dM ! 4 ! 2 ! 2 ! 2 !10 （二）（二） 的的10-排列数排列数; 的的 10-排列数；排列数； 的的10-排列数：排列数： 的的10-排列数；排列数； 10-排列数；排列数； 的的10-排列数排列数 这这6种类情况的种类情况的10-排列数相等，均为排列数相等，均为 , * baM , * caM , * daM , * cbM 10! 2!2!3!3! , * dbM , * dcM 满足条件的方法数为满足条

30、件的方法数为 226800 ! 3 ! 3 ! 2 ! 2 !10 6 ! 4 ! 2 ! 2 ! 2 !10 4 2021-6-29计算机科学与技术学院69 多重集的排列问题小结多重集的排列问题小结 2021-6-29计算机科学与技术学院70 多重集的组合多重集的组合 n 多重集合的r-组合是指从M中无序地选出r 个元素 例子例子 cc,c,b,c,a,b,b,b,a,a,a, 62 ,2,2,2 个：组合有的 M cbaM n 如果多重集M有n个元素(包括重复的元素)，则 M的n-组合只有一个，就是M本身。 n 如果M有n种不同元素，则M的1-组合恰有n个。 2021-6-29计算机科学与

31、技术学院71 多重集合的组合多重集合的组合 2021-6-29计算机科学与技术学院72 多重集合的组合多重集合的组合 2021-6-29计算机科学与技术学院73 多重集合的组合多重集合的组合 2021-6-29计算机科学与技术学院74 多重集合的组合多重集合的组合 n推论推论1 设多重集设多重集 且对一切且对一切i=1,2,n有有kir，则，则S的的r-组合数为组合数为C(n+r- 1,r)。 1122 ,., nn Sk a kaka 2021-6-29计算机科学与技术学院75 多重集合的组合多重集合的组合 2021-6-29计算机科学与技术学院76 多重集合的组合多重集合的组合 2021-

32、6-29计算机科学与技术学院77 例例3.3.5 求集合求集合S=1,2,n的的r-组合数，其组合数，其 中要求中要求r-组合中任意两个元素在组合中任意两个元素在S中都不是中都不是 相邻的。相邻的。 如当如当n=6，r=3时，时，S=1,2,3,4,5,6，1,3,5 是满足条件的是满足条件的3-组合，而组合，而1,2,6是不满足是不满足 条件的条件的3-组合，因为组合，因为1,2在在S中是相邻的。中是相邻的。 多重集合的组合多重集合的组合 2021-6-29计算机科学与技术学院78 分析分析 （1）问题求问题求普通集合的普通集合的r-组合数组合数 （2）要求要求对于任一对于任一 r-组合相邻

33、元素在组合相邻元素在S中不相邻中不相邻 （3）问题表示问题表示：任一：任一 r-组合组合 ，不妨，不妨 设为设为 ，那么就是要求，那么就是要求 （4）关心的是选取的相邻元素之间的关系）关心的是选取的相邻元素之间的关系 njjj r 21 1 1, 2 , 12 1 rijj ii , 21r jjj 多重集合的组合多重集合的组合 | 321r jjjj 2021-6-29计算机科学与技术学院79 解解 考虑考虑S的任意一个的任意一个r-组合组合 ， 不妨设不妨设 我们把我们把1,2,n这这 n个数按从小到大的顺序排成一个序列，个数按从小到大的顺序排成一个序列， 其中我们只把其中我们只把 标识出

34、来，其余标识出来，其余 数字用数字用“”表示。表示。 , 21r jjj njjj r 21 1 多重集合的组合多重集合的组合 | 321r jjjj 12 , r jjj 2021-6-29计算机科学与技术学院80 在序列中每个ji后面用以竖线“|”标记，则 设第1个竖线前面的数字个数为x1，第1个 竖线与第2个竖线间的数字个数为x2， 第r个竖线前面的数字个数为xr+1。 根据题意，因为 中任意两个数 都彼此不相邻，所以满足： x11，x22，xr2，xr+10， 因为一共有n个数字，所以 x1+x2+x3+xr+xr+1=n。 | 321r jjjj , 21r jjj 多重集合的组合多

35、重集合的组合 2021-6-29计算机科学与技术学院81 多重集合的组合多重集合的组合 这 样 原 问 题 要 求 的 r - 组 合 数 就 等 价 于 方 程 x1+x2+xr+xr+1=n满足条件x11，x22，xr2， xr+10的整数解个数。 进行代换，令y1=x1-1，y2=x2-2，yr=xr-2， yr+1=xr+1，则y10，y20，yr0，yr+10，且 y1+y2+yr+yr+1=n-1-2(r-1)。 根据定理3.3.3的证明：这个方程的非负整数解个 数是： 因此满足条件不相邻条件的r-组合数为 。 r rn rn rn rn rnr1 12 1 ) 1( 21 1)1( 21) 1( r rn1 2021