［Ｑ］ｎ×ｎ格子の左下端から右上端まで最短距離でいく行き方は何通りあるか？

［Ａ］2nＣn通り

［Ｑ］ｎ×ｎ格子の左下端から右上端まで最短距離でいく行き方は何通りあるか？　ただし，対角線より上側は通らないものとする．

［Ａ］2nＣn／（ｎ＋１）通り

　すなわち，対角線を越えない最短経路は（ｎ×ｎ格子の左下端から右上端まで最短距離でいく行き方）÷（ｎ＋１）で与えられる．

　カタラン数の一般項は

　　Ｃn＝2nＣn／（ｎ＋１）＝（２ｎ）！／ｎ！（ｎ＋１）！，

　　Ｃn＝2n+1Ｃn／（２ｎ＋１）

あるいは

　　Ｃn＝2nＣn−2nＣn-1＝１，２，５，１４，４２，・・・

と表される．

　カタラン数はいろいろなシーンで登場し，２００を超える応用問題があるという．そのひとつがオイラーの問題である．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】オイラーの問題

　凸多角形（ｎ＋２角形）に対角線を描いて，それをいくつかの凸多角形に分けるのではなく，対角線を互いに交わらないように引いて三角形分割する問題を考えよう．

［Ｑ］凸ｎ＋２角形に互いに交わらないｎ−１本の対角線を引いて三角形分割する仕方の数ｃ（ｎ）は？

［Ａ］この問題はオイラーが提起した幾何学問題である（オイラーの問題）．４角形では２通り，５角形では５通りあることは数えられても，６角形ではそう簡単にはいかない（６角形に対しては１４通りある）．

　６角形の場合，たとえばある対角線を引いて３角形と５角形，４角形と４角形，５角形と３角形に分割することができるが，そのような分割の仕方を場合分けすることで，積和型の漸化式

　　ｃ（ｎ＋１）＝ｃ（０）ｃ（ｎ）＋ｃ（１）ｃ（ｎ−１）＋・・・＋ｃ（ｎ）ｃ（０）

が得られる．ただし，ｃ（０）＝ｃ（１）＝１とする．

　これはカタラン数の漸化式であって，カタラン数ｃ（ｎ）はｎの増加に応じて急激に増加する．

　　ｃ（０）＝１，ｃ（１）＝１，ｃ（２）＝２，ｃ（３）＝５，

　　ｃ（４）＝１４，ｃ（５）＝４２，ｃ（６）＝１３２，

　　ｃ（７）＝４２９，ｃ（８）＝１４３０，ｃ（９）＝４８６２，・・・

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

　カタラン数の一般項は

　　ｃ（ｎ）＝2nＣn／（ｎ＋１）＝（２ｎ）！／（ｎ＋１）！ｎ！

であるが，この公式は母関数を用いると簡明に得ることができる．

　カタラン数の母関数を

　　Ｃ（ｘ）＝ｃ（０）＋ｃ（１）ｘ＋ｃ（２）ｘ^2＋・・・＋ｃ（ｎ）ｘ^n＋・・・

とおく．これを２乗すると

　　Ｃ（ｘ）^2＝ｃ（０）ｃ（０）＋（ｃ（０）ｃ（１）＋ｃ（１）ｃ（０））ｘ＋ （ｃ（０）ｃ（２）＋ｃ（１）ｃ（１）＋ｃ（２）ｃ（０））ｘ^2＋・・・

　ここで，

　　ｃ（０）ｃ（０）＝ｃ（１）

　　ｃ（０）ｃ（１）＋ｃ（１）ｃ（０）＝ｃ（２）

　　ｃ（０）ｃ（２）＋ｃ（１）ｃ（１）＋ｃ（２）ｃ（０）＝ｃ（３）

であるから，

　　Ｃ（ｘ）^2＝ｃ（１）＋ｃ（２）ｘ＋ ｃ（３）ｘ^2＋・・・

次数を揃えるために，両辺にｘをかけて

　　ｘＣ（ｘ）^2＝ｃ（１）ｘ＋ｃ（２）ｘ^2＋ ｃ（３）ｘ^3＋・・・

　　ｘＣ（ｘ）^2＝Ｃ（ｘ）−ｃ（０）＝Ｃ（ｘ）−１

　Ｃ（ｘ）に関する２次方程式を解いて，母関数は

　　Ｃ（ｘ）＝｛１−（１−４ｘ）^1/2｝／２ｘ

ここでニュートンの二項展開により，一般項

　　ｃ（ｎ）＝2nＣn／（ｎ＋１）＝（２ｎ）！／（ｎ＋１）！ｎ！

が得られる．

　なお，凸ｎ角形を対角線で三角形分割する仕方は何通りあるかという問題は，回転や反転で同型になるものを同じと数えると，

　　１，１，１，３，４，１２，２７，８２，２２８，７３３，２２８２，７５２８，・・・

となることを付記しておく．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】カタラン数

　カタラン数

　　｛Ｃn｝＝｛１，２，５，１４，４２，１３２，４２９，１４３０，４８６２，１６７９６，・・・｝

は，凸ｎ角形を対角線で三角形分割する仕方は何通りあるかとか，ｎ対のかみ合い括弧の種類数などいろいろな場面で登場する数なのですが，

　　Ｃn＝2nＣn／（ｎ＋１）＝（２ｎ）！／ｎ！（ｎ＋１）！，

　　Ｃn＝2n+1Ｃn／（２ｎ＋１），

あるいは

　　Ｃn＝2nＣn−2nＣn-1＝１，２，５，１４，４２，・・・

と表されます．

　カタラン数から一般項が何かを予想するのは難しいのですが，ここでは

　　Ｃn＝2nＣn／（ｎ＋１）　　　（Ｃ0＝１）

がわかっているものとして，母関数

　　Ｆ（ｔ）＝ΣＣnｔ^n

を求めてみます．

　この級数は，第０項：Ｃ0＝１から始まるので，そのまま項比をとると

　　ａn+1ｘn+1/ａnｘn=(n+1/2)(n+1)/(n+2)*4x/(n+1)

したがって，

　　Ｆ（ｘ）＝2Ｆ1(1/2,1,2,4x)=2/{1+(1-4x)^(1/2)}

　　　　　　＝{1-(1-4x)^(1/2)}/2x

　　(1-4x)^(1/2)＝Σ(-4)^k1/2Ck･ｘ^k

より

　　Ｃn＝-1/2(-4)^(n+1)1/2C(n+1)

これをさらに式変形すれば，

　　Ｃn＝2nＣn／（ｎ＋１）

になる．この結果，二項展開を丹念に使えば

　　{1-(1-4x)^(1/2)}/2x=Σ2nCnx^n/(n+1)

が得られるはず・・・．

　この方法は試してはいないのですが，かなり面倒そうです．実はカタラン数に対しては，漸化式

　　Ｃn＝ΣＣkＣn-k-1＝Ｃ0Ｃn-1＋Ｃ1Ｃn-2＋・・・＋Ｃn-1Ｃ0

が成り立つので，母関数は

　　Ｆ（ｔ）＝ΣＣnｔ^n＝ΣＣkｔ^kΣＣn-k-1ｔ^n-k＋１

　　　　　　＝Ｆ（ｔ）・ｔＦ（ｔ）＋１

すなわち，

　　ｔＦ（ｔ）^2−Ｆ（ｔ）−１＝０

なる２次方程式を満たすことが知られています．

　Ｃ0＝１を満足させなければならないので，複号は負号をとると，

　　Ｆ（ｔ）＝{1-(1-4x)^(1/2)}/2x

がでてきます．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝