【３】制限のある格子

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

［Ａ］2nＣn通り

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

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

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

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

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

［Ｑ］ｎ×ｎ×ｎ格子の（０，０，０）から（ｎ，ｎ，ｎ）まで最短距離でいく行き方は何通りあるか？

［Ａ］3nＣn・2nＣn通り

［Ｑ］ｎ×ｎ×ｎ格子の（０，０，０）から（ｎ，ｎ，ｎ）まで最短距離でいく行き方は何通りあるか？　ただし，ｘ≧ｙ≧ｚ≧０内の領域を通るものとする．

［Ａ］3nＣn・2nＣn・nＣn／n+2Ｃ2・n+1Ｃ1・nＣ0通り（３次元カタラン数）

　同様に，ｍ次元カタラン数は

　　mnＣn・・・3nＣn・2nＣn・3nＣn／n+m-1Ｃm-1・・・n+2Ｃ2・n+1Ｃ1・nＣ0

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