组合数学第一章3学习资料

复习题有8人围圆桌就餐，问有多少种就座方式？如果有两人不愿坐在一起，又有多少种就座方式？例某车站有6个入口处，每个入口处每次只能进一人，一组9个人进站的方案有多少？[解]一进站方案表示成：00011001010100其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。[解法1]标号可产生5!个14个元的全排列。故若设x为所求方案，则

x·5!=14!∴x=14!/5!=726485760[解法2]在14个元的排列中先确定“1”的位置，有C(14,5)种选择，在确定人的位置，有9！种选择。故C(14,5)·9!即所求[解法3]把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9号。1号有6种选择；2号除可有1号的所有选择外，还可（也必须）选择当与1号同一门时在1号的前面还是后面，故2号有7种选择；3号的选择方法同2号，故共有8种。以此类推，9号有14种选择。

故所求方案为14!/5!=726485760引例在100名选手之间进行淘汰赛（即一场的比赛结果，失败者退出比赛），最后产生一名冠军，问要举行几场比赛？证明：第1轮要进行50场比赛，留下50名选手；第2轮要进行25场比赛，留下25名选手；第3轮要进行25场比赛，1名轮空，留下13名选手；第4轮要进行6场比赛，1名轮空，留下7名选手；第5轮要进行3场比赛，1名轮空，留下4名选手；第6轮要进行2场比赛，留下2名选手；最后一场决赛，产生1名冠军。根据加法法则，共需要进行50+25+12+6+3+2+1=99场比赛。其实，最后产生1名冠军需要淘汰99人，一场比赛淘汰1人，两者一一对应，需要99场比赛进行。1.3模型转换“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。如我们说A集合有n个元素|A|=n，无非是建立了将A中元与[1,n]元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换。1.3模型转换例

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|Hn=1甲烷n=2乙烷n=3丙烷1.3模型转换

H|H—C—H|H—C—H|H—C—H|H—C—H|H

H|HH—CH||H—C—C—H||H—CH|HHn=4丁烷n=4异丁烷这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2.1.3模型转换例(Cayley定理)n个有标号的顶点的树的数目等于n。n-2生长点不是叶子,每个生长点是[1,n]中的任一元.有n种选择。两个顶点的树是唯一的。1.3模型转换⑦⑥||②—③—①—⑤—④41253逐个摘去标号最小的叶子，叶子的相邻顶点(不是叶子，是内点)形成一个序列，序列的长度为n-2例给定一棵有标号的树边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边)第一次摘掉②，③为②相邻的顶点，得到序列的第一个数3以此类推，得到序列31551,长度为7－2=5这是由树形成序列的过程。1.4模型转换由序列形成树的过程：由序列31551得到一个新序列111233455567生成的过程是首先将31551排序得到11355，因为序列31551的长度为5，得到按升序排序的序列1234567，序列的长度为5+2(即n+2)，然后将11355按照大小插入到序列1234567中，得到111233455567然后将两个序列排在一起315511112334555671.4模型转换

31551111233455567②—③

15511113455567①—③

55111455567④—⑤

51115567⑤—⑥

11157①—⑤

17第一步推导：将上下两个序列同时去掉上行序列的第一个元素3(用黄色表示)，去掉下行序列的第一个无重复的元素2(用红色表示)。生成一条边(②—③)。依此类推，减到下面剩最后两个元素，这两个元素形成最后一条边。最后形成树。1.3模型转换上述算法描述：给定序列b=(b1b2…bn-2)设a=(123…n-1n)将b的各位插入a,得a’,对()做操作。a’是2n-2个元的可重非减序列。ba’操作是从a’中去掉最小无重元，设为a1,再从b和a’中各去掉一个b中的第一个元素，设为b1，则无序对(a1,b1)是一条边。重复这一操作，得n-2条边，最后a’中还剩一条边，共n-1条边，正好构成一个树。b中每去掉一个元，a’中去掉2个元。1.3模型转换由算法知由树T得b=(b1b2…bn-2)，反之，由b可得T。即f：T→b是一一对应。由序列确定的长边过程是不会形成回路的。因任意长出的边(u,v)若属于某回路，此回路中必有一条最早生成的边，不妨就设为(u,v)，必须使u,v都在长出的边中重复出现，但照算法u,v之一从下行消失，不妨设为u，从而不可能再生成与u有关的边了，故由()得到的边必构成一个n个顶点的树。ba’1.3模型转换例简单格路问题|(0,0)→(m,n)|=()从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？m+nmy(m,n)...0...x1.3模型转换无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。则(0,0)→(m,n)的每一条路径可表示为m个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号，可得m!n!个m+n元的无重全排列。1.3模型转换设所求方案数为p(m+n；m，n)则P(m+n；m，n)·m!·n!=(m+n)!故P(m+n;m,n)=———=()=() =C(m+n,m)设c≥a,d≥b,则由(a,b)到(c,d)的简单格路数为|(a,b)(c,d)|=()(m+n)!m+nm+nm!n!mn(c-a)+(d-b)c-a(c,d)(a,b)1.3模型转换例在上例的基础上若设m<n，求(0,1)点到(m,n)点不接触对角线x=y的格路的数目(“接触”包括“穿过”)从(0,1)点到(m,n)点的格路，有的接触x=y，有的不接触。对每一条接触x=y的格路，做(0,1)点到第一个接触点部分关于x=y的对称格路，这样得到一条从(1,0)到(m,n)的格路。1.3模型转换容易看出从(0,1)到(m,n)接触x=y的格路与(1,0)到(m,n)的格路(必穿过x=y)一一对应yy=x(m,n)0(1,0)x(0,1)..yx-y=1(m,n)x(0,0)(1,-1).....1.3模型转换故所求格路数为()－()=———－———=————(—－—)=——()=(1－—)()=——()m+n-1m+n-1mm-1(m+n-1)!(m+n-1)!(m+n-1)!11m!(n-1)!(m-1)!n!(m-1)!(n-1)!mnm+n-1m+n-1mm

n-mmnnm+n-1m

n-mn1.3模型转换若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得x－