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

［Ａ］2nＣn通り

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

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

　これを一般化すると

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

［Ａ］m+nＣm＝m+nＣn通り

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

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

　まず，

　　Ｃ（ｍ，ｎ）＝Ｃ（ｎ，ｍ），Ｃ（ｎ，ｎ）＝Ｃn

は自然に浮かぶところであるが，

　　Ｃ（ｋｎ，ｎ）＝(k+1)nＣn／（ｋｎ＋１）

が成り立つことが知られている．

　２ｎ＋２角形は四角形分割，ｋｎ＋２角形はｋ＋２角形分割できるのであるが，この式は凸ｋｎ＋２角形に互いに交わらない対角線を引いて（ｋ＋２）角形分割する仕方の数が，

　　Ｃ（ｋｎ，ｎ）＝(k+1)nＣn／（ｋｎ＋１）

で与えられることを示している．

　ｍとｎが互いに素のとき，

　　Ｃ（ｍ，ｎ）＝m+nＣn／（ｍ＋ｎ）

しかし，互いに素でない場合を求めるのは容易ではない．

　　［参］枡田幹也，福川由貴子「格子から見える数学」日本評論社

を参照して欲しい．

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