📄 2_1.htm

📁 组合数学清华大学研究生课程课件呵呵
💻 HTM
字号:
<html><head><title>组合数学</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><body><h1>§2.1  母函数&nbsp;</h1></p> <p>&nbsp;&nbsp;&nbsp; 递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如&nbsp;</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image002.gif" width="526" height="113"></p><p>x<sup>2</sup>项的系数a<sub>1</sub>a<sub>2</sub>+a<sub>1</sub>a<sub>3</sub>+<sup>...</sup>+a<sub>n-1</sub>a<sub>n</sub>中所有的项包括n个元素a<sub>1</sub>，a<sub>2</sub>，  …a<sub>n</sub>中取两个组合的全体；同理项系数包含了从n个元素a<sub>1</sub>，a<sub>2</sub>，  …a<sub>n</sub>中取3个元素组合的全体。以此类推。&nbsp;</p> <p>&nbsp;&nbsp;&nbsp; 若令a<sub>1</sub>=a<sub>2</sub>= …=a<sub>n</sub>=1，在（2-1-1）式中a<sub>1</sub>a<sub>2</sub>+a<sub>1</sub>a<sub>3</sub>+<sup>...</sup>+a<sub>n-1</sub>a<sub>n</sub>项系数： 中每一个组合有1个贡献，其他各项以此类推。故有：</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;<img border="0" src="2_1.pic/image011.gif" width="410" height="64"></p><p>&nbsp;&nbsp;&nbsp; 另一方面：&nbsp;</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image013.gif" width="278" height="35"></p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image015.gif" width="398" height="132"></p><p>&nbsp;&nbsp;&nbsp; 比较等号两端项对应系数，可得一等式&nbsp;</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image017.gif" width="378" height="58"></p><p>&nbsp;&nbsp;&nbsp; 同样对于(1+x)<sup>n</sup>(1+1/x)<sup>m</sup>，（设n&gt;=m ），用类似的方法可得等式：&nbsp;</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image023.gif" width="398" height="53"></p><p>正法如下：&nbsp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image025.gif" width="324" height="32"></p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image027.gif" width="420" height="127"></p><p>比较等式两端的常数项，即得公式(2-1-3)&nbsp;</p><p>&nbsp;&nbsp;&nbsp; 又如等式：&nbsp;</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image029.gif" width="324" height="69"></p><p>令x=1 可得&nbsp;</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image031.gif" width="346" height="59"></p><p>(2-1-2)式等号的两端对x求导可得：&nbsp;</p><p>　</p><p>等式(2-1-5)两端令x=1，得：&nbsp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image033.gif" width="444" height="63"></p><p>用类似的方法还可以得到：&nbsp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image037.gif" width="360" height="67"></p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image039.gif" width="408" height="66"></p><p>&nbsp;&nbsp;&nbsp; 还可以类似地推出一些等式，但通过上面一些例子已可见函数(1+x)<sup>n</sup>在研究序列C(n,0),C(n,1),<sup>...</sup>,C(n,n)的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概念如下：&nbsp;</p> <p>&nbsp;&nbsp;&nbsp; 定义：对于序列a<sub>0</sub>，a<sub>1</sub>，a<sub>2</sub>，…构造一函数：&nbsp;</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_1.pic/image047.gif" width="266" height="36"></p><p>称函数G(x)是序列a<sub>0</sub>，a<sub>1</sub>，a<sub>2</sub>，…的母函数&nbsp;</p><p>*</p><p>&nbsp;&nbsp;&nbsp; 例如(1+x)<sup>n</sup>是序列C(n,0),C(n,1),<sup>...</sup>,C(n,n)的母函数。&nbsp;</p> <p>&nbsp;&nbsp;&nbsp; 如若已知序列a<sub>0</sub>，a<sub>1</sub>，a<sub>2</sub>，…则对应的母函数G(x)便可根据定义给出。反之，如若以求得序列的母函数G(x)，则该序列也随之确定。&nbsp;</p> <p>&nbsp;&nbsp;&nbsp; 序列a<sub>0</sub>，a<sub>1</sub>，a<sub>2</sub>，…可记为{a<sup>n</sup>} 。</p>  </body></html>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -