京都府医大3番　問題　解答　　2001年入試に戻る

　この問題の f(n,k) はじつはカタラン数 で紹介した［96九州大学］の N(i,j) と同一である．
　なぜこれが同一なのかは，次の図を見れば分かる．

(0,0)から(6,4)への最短経路に対してつぎのように枠の上段下段に数字を入れる．

x軸方向への移動は上段，y軸方向への移動は下段に対応する．
方向を転換するまで進んだ区画の個数分1から順に数字を枠に入れる．

左の経路では
x軸方向2,y軸方向1,x軸方向1,y軸方向1,x軸方向2,y軸方向2,x軸方向1 なので
上段1,2，下段3，上段4，下段5，上段6,7，下段8,9，上段10

これが題意を満たしているのは，この経路が対角線とその下のみを進んでいるから，つねに上段の方に多くの数字が入るからである．
これが右のように対角線を横切って越えると，そこで下段の方が数字が大きくなる．

したがって題意を満たす数字の入れ方と，対角線とその下のみを進む経路とが1:1に対応する．