组合数学义排列组合.pptVIP

Combinatorics组合数学 陈克非 上海交通大学计算机科学与工程系 Kfchen@ 6/ 第二章：排列组合 加法法则、乘法法则 排列、组合 举例 排列、组合生成 字典排序法 邻位互换法 注记 基本计数原理 集合S的划分： 加法原理 若S划分为S1, S2,…, Sm, 则 乘法原理 S为有序对(a,b)集合，其中a有p种选择， b有q种选择，则 注：乘法原理是加法原理的一个推论（可以证明）。 举例 例1. 两位数中，有多少两位互异且非零的数？ ab为有序对(a,b)， 共9x8=72 例2. 现有6个橘子，9个苹果，欲组成果篮。要求果篮非空，有多少种不同的可能？ 橘子{0,1,2,3,4,5,6} 苹果{0,1,2,3,4,5,6,7,8,9} 不同组合7x10=70 除去(0,0)的情况，有69种可能 计数问题的类型 对元素的有序的摆放数或有序的选择数进行计数 没有重复如何元素 允许元素重复（但可能是有效次重复） 对元素的无序的摆放数或无序的选择数进行计数 没有重复如何元素 允许元素重复（但可能是有效次重复） 举例 例1. 在1000和9999有多少具有不同数字的奇数？ 有个、十、百、千4个位置可以选择 个位：1,3,5,7,9有5种选择 千位：剩下8种选择 十/百位：8种选择，剩下一位只有7种选择 共计5x8x8x7=2240种 选择顺序影响乘法原理的使用 例2. 在0和10000之间整数恰好有一位数字是5？ Si是i 位数集合(i=1,2,3,4) |S1|=1；|S2|=17:个位是5有8种，十位是5有9种 |S3|=225:个位是5有8x9种，十位是5有8x9种，百位是5有9x9种；|S4|=2763 排列、组合问题 [定义]从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。 排列的全体组成的集合用P(n,r)表示。排列的个数用P(n,r)表示。当r=n时称为全排列。 [定义]从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。 组合的全体组成的集合用C(n,r)表示，组合的个数用C(n,r)或 表示。 组合vs.排列 从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，……，第r个有n-r+1种选择。故有P(n,r)=n(n-1)……(n-r+1) 有时也用[n]r记n(n-1)……(n-r+1) 若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。 故有C(n,r)·r!=P(n,r), 例 问题：求1000!中的尾数有几个零？ 分析：一个零对应一对因子2和5 1000以内5的倍数有200个 1000以内25的倍数有40个 1000以内125的倍数有8个 1000以内625的倍数有1个 所以， 1000!中5的幂有200+40+8+1=249个 1000!中2的幂远多于249个 解： 1000!中有249个0 树的数目 图论问题：对n个顶点v1, v2, …,vn用n-1条边连接起来，问有多少种方案？ 例，给定一棵有标号 的树，边上的标号表 示摘去叶的顺序（摘 去一个叶子相应去掉一条边） 逐个摘去标号最小的叶子，叶子的相邻顶点形成一个序列，序列的长度为n-2 第一次摘掉②，③为②相邻的顶点，得到序列的第一个数3,以此类推，得到序列31551,长度为7-2=5,这是由树形成序列的过程。 n顶点树与n-2序列的对应 由序列形成树的过程： 给定序列31551（1） 从序列1234567（2）中找第一个不在（1）出现的数“2”，建立边“（2,3）” 得到1551（1’）及134567（2’），类似得到边（3,1） 再得到551（1’’）及14567（2’’）依此类推得到边（4,5），（6,5），（7,1） 最后序列（2）中剩下的2个数构成最后的边（1,5） 这表明， n顶点树与n-2序列建立了1-1对应 Cayley定理 定理：n个有标号的顶点的树的数目等于nn-2 证明：由1-1对应关系知 n个顶点树的数目＝序列b1, b2, …,bn-2 (0b=n)的数目 相应序列的数目为nn-2 注：一个问题与另一个问题1-1对应，则可将一个问题转化为另一个问题来处理。在处理组合计数问题时，常常通过问题的1-1对应实现模型的转换，以便于问题的求解。 生成排列 问题：从已知排列出发，生成新的排列 目的：提高效率，减少开销 n个元素的排列的个数太多， （Stirling公式） 任务：寻找好的算法 序数法 如十进制、二进制，