请输入您要查询的字词:

 

单词 GeneratingFunctionForTheCatalanNumbers
释义

generating function for the Catalan numbers


This article derives the formula

Cnxn=1-1-4x2x

for the generating function for the Catalan numbersMathworldPlanetmath, given in the parent (http://planetmath.org/CatalanNumbers) article, in two different ways.

A Dyck pathMathworldPlanetmath is a lattice pathMathworldPlanetmath in the Euclidean planeMathworldPlanetmath from (0,0) to (2n,0) whose steps are either (1,1) or (1,-1), i.e. either upwards diagonals or downwards diagonals, and which never goes below the x-axis. Here are two Dyck paths:

        If you rotate a Dyck path counterclockwise by 45 and then reflect it in the line x=y, the result is a lattice path from (0,0) to (n,n) that never goes above the diagonal. One can also think of such a path as a path from (1,0) to (n+1,n) that never touches or crosses the diagonal. As the article on ballot numbers (http://planetmath.org/LatticePathsAndBallotNumbers) explains, these paths are counted by the Catalan numbers, and thus the number of Dyck paths of length 2n (or Dyck paths of semilength n) is equal to Cn, the nth Catalan number.Note that any Dyck path has a unique decomposition as follows. Every Dyck path returns to the x-axis at some point (possibly at its end). Split the path at the first such point. Then the original path consists of an up step (the first step of the path), an arbitrary (perhaps empty) Dyck path, a down step returning to the x-axis, and then another arbitrary (perhaps empty) Dyck path.Considering the first example above, this decomposition looks like this:So a Dyck path is either empty, or consists of an up/down and two arbitrary Dyck paths. If one thinks about the lengths of the paths involved, it is clear that in terms of the generating function, we haveC(x)=1+xC(x)2since a nonempty Dyck path of semilength n consists of two Dyck paths the sum of whose semilengths is n-1 together with the unique Dyck path of semilength 1 (the up-down steps).Solving this quadratic equation, we getC(x)=1±1-4x2xand we must decide between the plus and minus sign. However, note that C(x) is a formal power series with only nonnegative powers of x, and the expansion of 1-4x starts with the constant termPlanetmathPlanetmath 1. So if the sign were positive, then C(x) would have a leading term of 1x. So we must choose the negative sign, and we getC(x)=1-1-4x2xHere is a second method of getting to the same result; it is more straightforward but less informative.By the generalized binomial formula, we have that1+x=(1+x)1/2=k=0(1/2k)xk=(1/20)+k=1(1/2k)xk=1+k=1(1/2k)xkNow,(1/2k)=(1/2)(1/2-1)(1/2-2)(1/2-k+1)k!=2-k(-1)k-1135(2k-3)k!=2-k(-1)k-1(k-1)!135(2k-3)k!(k-1)!=21-2k(-1)k-1(2k-2)!k!(k-1)!=21-2k(-1)k-11k(2k-2k-1)and so, substituting, we get1+x=1+k=121-2k(-1)k-11k(2k-2k-1)xkReplacing x by -4x, we get1-4x-1=k=121-2k(-1)k-11k(2k-2k-1)(-1)k22kxk=k=1(-2)1k(2k-2k-1)xk=k=0-2k+1(2kk)xk+1where the last equality results from replacing k by k+1 and adjusting the range of summation. On dividing through by -2x, we get1-1-4x2x=k=01k+1(2kk)xk=k=0Ckxkand we are done.As a final observation, note that the recurrenceCn=i=0n-1CiCn-1-igiven in the parent (http://planetmath.org/CatalanNumbers) article can be easily derived from the functional equation for the generating function, C(x)=1+xC(x)2:kCkxk=1+x(kCkxk)2and the coefficient of xn on the right hand side is the coefficient of xn-1 in the sum, which is preciselyk=0n-1CkCn-1-kas desired.Titlegenerating function for the Catalan numbersCanonical nameGeneratingFunctionForTheCatalanNumbersDate of creation2013-03-22 17:38:47Last modified on2013-03-22 17:38:47Ownerrm50 (10146)Last modified byrm50 (10146)Numerical id9Authorrm50 (10146)Entry typeDerivationClassificationmsc 05A10Related topicDyckLanguageDefinesDyck paths
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 9:25:31