组合数学第一讲.pptVIP

第一章 排列与组合 容易看出从(0,1)到(m,n)接触x=y的格路与 (1,0)到(m,n)的格路(必穿过x=y)一一对应 y y=x (m,n) O (1,0) x (0,1) . . 故所求格路数为( )－( )。 m+n-1 m+n-1 m m-1 第一章 排列与组合 若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得x－y=1，　(0,0)关于x－y=1的对称点为(1,-1). 格路也是一种常用模型 m+n m+n m m-1 (m+n)! (m+n)! m!n! (m-1)!(n+1)! m+n m n+1-m n+1 所求格路数为 ( )－( ) = ——— － ———— = ——— ( ) y x-y=1 (m,n) x (0,0) (1,-1) . . . . . 第一章 排列与组合 例 CnH2n+2是碳氢化合物,随着n的不同有下列不同的枝链： H | H — C — H | H H | H — C — H | H — C — H | H H | H — C — H | H — C — H | H — C — H | H n=1甲烷 n=2 乙烷 n=3 丙烷 第一章 排列与组合 H | H — C — H | H — C — H | H — C — H | H — C — H | H H | H H — C H | | H — C — C — H | | H — C H | H H n=4 丁烷 n=4异丁烷 这说明对应CnH2n+2的 枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化 合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2. 第一章 排列与组合 1.4全排列的生成算法 就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 全排列的生成算法有许多种，我们仅介绍其中一种--序数法 第一章 排列与组合 1.4.1全排列的生成--序数法 任一自然数n都可以唯一确定一个p进制数,反之也然。 类似地，有 第一章 排列与组合 同理 所以 即 第一章 排列与组合 不难证明，从0到n!-1的任一个整数m都可唯一地表示为： 所以从0到n!-1的n!个整数与满足上式的序列(an-1,an-2,…a2,a1)一一对应。 然后我们再从(an-1,an-2,…a2,a1)建立与全排列的一一对应关系。 第一章 排列与组合 例 ：m＝4000，即n1＝4000 第一章 排列与组合 现从序列 (an-1,an-2,…a2,a1)得到生成排列，为 了方便起见,不妨今n个对象分别是1,2,… n. 建立起对应的规则如下： 设序列(an-1,an-2,…a2,a1) 对应某个排列(p)=p1 p2,…,pn， 其中ai可以看作是排列(p)中数i+1所在位置后 面比i+1小的数的个数， 也就是排列(p)中从数i+1开始向右统计小于 或等于i的数的个数。 第一章 排列与组合 以排列4213为例， 4后面比它小的数的个数(即a3)为3; 3后面比它小的数的个数(即a2)等于0; 2后面比它小的数的个数(即a1)为1； 排列中比1小的数是没有的． 故得(p)=(4213) ←→ (a3a2