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

［Ａ］2nＣn通り

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

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

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

　カタラン数の一般項は

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

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

あるいは

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

と表される．

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

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

【１】オイラーの問題

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

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

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

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

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

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

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

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

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

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

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