■カタラン数と漸化式(その4)

【3】制限のある格子

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

[A]2nCn通り

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

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

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

  2nCn/(n+1)=2nCn・nCn/n+1C1・nC0

と記述できることに注意.これを一般化すると

[Q]n×n×n格子の(0,0,0)から(n,n,n)まで最短距離でいく行き方は何通りあるか?

[A]3nCn・2nCn通り

[Q]n×n×n格子の(0,0,0)から(n,n,n)まで最短距離でいく行き方は何通りあるか? ただし,x≧y≧z≧0内の領域を通るものとする.

[A]3nCn・2nCn・nCn/n+2C2・n+1C1・nC0通り(3次元カタラン数)

 同様に,m次元カタラン数は

  mnCn・・・3nCn・2nCn・3nCn/n+m-1Cm-1・・・n+2C2・n+1C1・nC0

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