■カタラン数(その3)

[Q]n×n格子の左下端から右上端まで最短距離でいく行き方は何通りあるか?

[A]2nCn通り

[Q]n×n格子の左下端から右上端まで最短距離でいく行き方は何通りあるか? ただし,対角線より上側は通らないものとする.

[A]2nCn/(n+1)通り

 すなわち,対角線を越えない最短経路は(n×n格子の左下端から右上端まで最短距離でいく行き方)÷(n+1)で与えられる.

 カタラン数の一般項は

  Cn=2nCn/(n+1)=(2n)!/n!(n+1)!,

  Cn=2n+1Cn/(2n+1)

あるいは

  Cn=2nCn−2nCn-1=1,2,5,14,42,・・・

と表される.

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

===================================

【1】オイラーの問題

 凸多角形(n+2角形)に対角線を描いて,それをいくつかの凸多角形に分けるのではなく,対角線を互いに交わらないように引いて三角形分割する問題を考えよう.

[Q]凸n+2角形に互いに交わらないn−1本の対角線を引いて三角形分割する仕方の数c(n)は?

[A]この問題はオイラーが提起した幾何学問題である(オイラーの問題).4角形では2通り,5角形では5通りあることは数えられても,6角形ではそう簡単にはいかない(6角形に対しては14通りある).

 6角形の場合,たとえばある対角線を引いて3角形と5角形,4角形と4角形,5角形と3角形に分割することができるが,そのような分割の仕方を場合分けすることで,積和型の漸化式

  c(n+1)=c(0)c(n)+c(1)c(n−1)+・・・+c(n)c(0)

が得られる.ただし,c(0)=c(1)=1とする.

 これはカタラン数の漸化式であって,カタラン数c(n)はnの増加に応じて急激に増加する.

  c(0)=1,c(1)=1,c(2)=2,c(3)=5,

  c(4)=14,c(5)=42,c(6)=132,

  c(7)=429,c(8)=1430,c(9)=4862,・・・

===================================