组合数学第一讲.ppt

第一章 排列与组合容易看出从(0,1)到(m,n)接触x=y的格路与(1,0)到(m,n)的格路(必穿过x=y)一一对应yy=x(m,n)O(1,0)x(0,1)..故所求格路数为()－()。m+n-1m+n-1mm-1第一章 排列与组合若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得x－y=1，(0,0)关于x－y=1的对称点为(1,-1).格路也是一种常用模型m+nm+nmm-1(m+n)!(m+n)!m!n!(m-1)!(n+1)!m+nmn+1-mn+1所求格路数为()－()=———－————=———()yx-y=1(m,n)x(0,0)(1,-1).....第一章 排列与组合例CnH2n+2是碳氢化合物,随着n的不同有下列不同的枝链：H|H—C—H|HH|H—C—H|H—C—H|HH|H—C—H|H—C—H|H—C—H|Hn=1甲烷n=2乙烷n=3丙烷第一章 排列与组合H|H—C—H|H—C—H|H—C—H|H—C—H|HH|HH—CH||H—C—C—H||H—CH|HHn=4丁烷n=4异丁烷这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2.4全排列的生成算法01就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。02全排列的生成算法有许多种，我们仅介绍其中一种--序数法03第一章 排列与组合第一章 排列与组合全排列的生成--序数法任一自然数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)得到生成排列，为1了方便起见,不妨今n个对象分别是1,2,…n.2建立起对应的规则如下：3设序列(an-1,an-2,…a2,a1)4对应某个排列(p)=p1p2,…,pn，5其中ai可以看作是排列(p)中数i+1所在位置后6面比i+1小的数的个数，7也就是排列(p)中从数i+1开始向右统计小于8或等于i的数的个数。9第一章 排列与组合第一章 排列与组合以排列4213为例，4后面比它小的数的个数(即a3)为3;3后面比它小的数的个数(即a2)等于0;2后面比它小的数的个数(即a1)为1；排列中比1小的数是没有的．故得(p