📄 1_4.htm
字号:
<html><head><title>Untitled Document</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><body bgcolor="#FFFFFF"><h1>1.4模型转换</h1><p>“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。<br> 如我们说A集合有n个元素|A|=n，无非是建立了将A中元与[1,n]元一一对应的关系。<br> 在组合计数时往往借助于一一对应实现模型转换。<br> 比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。</p><p><b>[例]简单格路问题</b>|(0,0)→(m,n)|=<img src="1_4pic/image002.gif" width="55" height="48" align="middle">,从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？</p><p><object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0" width="220" height="200"> <param name=movie value="1_4pic/1_4_1.swf"> <param name=quality value=high> <embed src="1_4pic/1_4_1.swf" quality=high pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" type="application/x-shockwave-flash" width="220" height="200"> </embed> </object></p><p>无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。 则(0,0)→(m,n)的每一条路径可表示为m个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号，可得m!n!个m+n元的无重全排列。<br> 设所求方案数为p(m+n；m，n),则P(m+n；m,n)·m!·n!=(m+n)!<br> 故P(m+n;m,n)=<img src="1_4pic/image004.gif" width="55" height="41" align="middle">=<img src="1_4pic/image002.gif" width="55" height="48" align="middle">=C(m+n,m) 设c≥a,d≥b,则由(a,b)到(c,d)的简单格路数为|(a,b)(c,d)|=<img src="1_4pic/image006.gif" width="120" height="48" align="middle"></p><p><b>[例]</b>在上例的基础上若设m<n，求(0,1)点到(m,n)点不接触对角线x=y的格路的数目(“接触”包括“穿过”)<br> 从(0,1)点到(m,n)点的格路，有的接触x=y，有的不接触。对每一条接触x=y的格路，做(0,1)点到第一个接触点部分关于x=y的对称格路，这样得到一条从(1,0)到(m,n)的格路。</p><p><object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0" width="220" height="200"> <param name=movie value="1_4pic/1_4_3.swf"> <param name=quality value=high> <embed src="1_4pic/1_4_3.swf" quality=high pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" type="application/x-shockwave-flash" width="220" height="200"> </embed> </object><object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0" width="220" height="200"> <param name=movie value="1_4pic/1_4_4.swf"> <param name=quality value=high> <embed src="1_4pic/1_4_4.swf" quality=high pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" type="application/x-shockwave-flash" width="220" height="200"> </embed> </object></p><p>容易看出从(0,1)到(m,n)接触x=y的格路与(1,0)到(m,n)的格路(必穿过x=y)一一对应</p><p>故所求格路数为<img src="1_4pic/image008.gif" width="181" height="244" align="top"></p><p>若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得x－y=1，(0,0)关于x－y=1的对称点为(1,-1).<br> 所求格路数为 <img src="1_4pic/image010.gif" width="425" height="48" align="middle"></p><p><i>格路也是一种常用模型</i></p><p><b>[例]</b>C<sub>n</sub>H<sub>2n+2</sub>是碳氢化合物,随着n的不同有下列不同的枝链： </p><table width="67%" border="0" cellspacing="0" cellpadding="0" align="center"> <tr align="center"> <td><object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0" width="130" height="130"> <param name=movie value="1_4pic/1_4_5.swf"> <param name=quality value=high> <embed src="1_4pic/1_4_5.swf" quality=high pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" type="application/x-shockwave-flash" width="130" height="130"> </embed> </object></td> <td><object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0" width="130" height="160"> <param name=movie value="1_4pic/1_4_6.swf"> <param name=quality value=high> <embed src="1_4pic/1_4_6.swf" quality=high pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" type="application/x-shockwave-flash" width="130" height="160"> </embed> </object></td> <td><object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0" width="130" height="210"> <param name=movie value="1_4pic/1_4_7.swf"> <param name=quality value=high> <embed src="1_4pic/1_4_7.swf" quality=high pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" type="application/x-shockwave-flash" width="130" height="210"> </embed> </object></td> </tr> <tr align="center"> <td>n=1甲烷 </td> <td>n=2 乙烷 </td> <td>n=3 丙烷</td> </tr></table><table width="70%" border="0" cellspacing="0" cellpadding="0" align="center"> <tr align="center"> <td><object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0" width="130" height="210"> <param name=movie value="1_4pic/1_4_8.swf"> <param name=quality value=high> <embed src="1_4pic/1_4_8.swf" quality=high pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" type="application/x-shockwave-flash" width="130" height="210"> </embed> </object></td> <td><object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0" width="180" height="210"> <param name=movie value="1_4pic/1_4_9.swf"> <param name=quality value=high> <embed src="1_4pic/1_4_9.swf" quality=high pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" type="application/x-shockwave-flash" width="180" height="210"> </embed> </object></td> </tr> <tr align="center"> <td>n=4 丁烷 </td> <td>n=4异丁烷 </td> </tr></table><p> </p><p>这说明对应C<sub>n</sub>H<sub>2n+2</sub>的枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。从而可以通过研究具有上述性质的 树找到不同的碳氢化合物C<sub>n</sub>H<sub>2n+2</sub>. </p><p><b>[例]</b>在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？<br> [解]一种常见的思路是按轮计场，费事。<br> 另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。</p><p><b>[例]</b>(Cayley定理)n个有标号的顶点的树的数目等于n<sup>n+2</sup>.<br> 生长点不是叶子,每个生长点是[1,n]中的 任一元.有n种选择。两个顶点的树是唯一的。 </p><p><b>[例]</b>给定一棵有标号的树,边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边)<br> <object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0" width="270" height="100"> <param name=movie value="1_4pic/1_4_10.swf"> <param name=quality value=high> <embed src="1_4pic/1_4_10.swf" quality=high pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" type="application/x-shockwave-flash" width="270" height="100"> </embed> </object></p><p>逐个摘去标号最小的叶子，叶子的相邻顶点(不是叶子,是内点)形成一个序列，序列的长度为n-2,第一次摘掉②，③为②相邻的顶点，得到序列的第一个数3,以此类推，得到序列31551,长度为7－2=5,这是由树形成序列的过程。</p><p>由序列形成树的过程：<br> 由序列31551得到一个新序列111233455567,生成的过程是首先将31551排序得到11355，因为序列31551的长度为5，得到按升序排序 的序列1234567，序列的长度为5+2(即n+2)，然后将11355按照大小插入到序列1234567中，得到111233455567,然后将两个序列排在一起<img src="1_4pic/image014.gif" width="115" height="48" align="middle"></p><p><a href="1_4pic/4_1.zip"><img src="down.gif" width="9" height="15" border="0">下载计算过程（ppt版本)</a></p><p>上述算法描述：<br> 给定序列b=(b<sub>1</sub>b<sub>2</sub>…b<sub>n-2</sub>),设a=(123…n-1 n),将b的各位插入a,得a',对<img src="1_4pic/image012.gif" width="31" height="48" align="middle">做操作。a'是2n-2个元的可重非减序列。操作是从a'中去掉最小无重元，设为a<sub>1</sub>,再从b和a'中各去掉一个b中的第一个元素，设为b<sub>1</sub>，则无序对(a<sub>1</sub>,b<sub>1</sub>)是一条边。重复这一操作，得 n-2条边，最后a'中还剩一条边，共n-1条边，正好构成一个树。b中每去掉一个元，a'中去掉2个元。<br> 由算法知由树T得b=(b<sub>1</sub>b<sub>2</sub>…b<sub>n-2</sub>)，反之，由b可得T。即f:T→b是一一对应。由序列确定的长边过程是不会形成回路的。因任意长出的边(u,v)若属于某回路，此回路中必有一条最早生成的边，不妨就设为(u,v),必须使u,v都在长出的边中重复出现，但照算法u,v之一从下行消失，不妨设为u，从而不可能再生成与u有关的边了，故由<img src="1_4pic/image012.gif" width="31" height="48" align="middle">得到的边必构成一个n个顶点的树。</p><p>[证]由一棵n个顶点的树可得到一个长度为n－2的序列，且不同的树对应的序列不同<sup>*</sup>，因此|T|≤n<sup>n-2</sup>。</p><p>*:对n用归纳法可证.</p><p>反之，由一个长度为n－2的序列(每个元素为1~n的一个整数)，可得到一棵树，且不同的序列对应的树是不同的，因此n<sup>n-2</sup>≤|T|, |T|=n<sup>n-2</sup></p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -