カタラン数はもう語らん……！
カタラン数Cn は、縦横 n マスずつの格子において、対角線を跨がずに格子点を通って、向かい合った点を最短距離で繋ぐ道順の総数と説明できるせいで1次元の酔歩問題との関連が深い
証拠に上記格子を45°回転したら、たちまち縦軸が時刻、横軸が位置xの平面となり、カタラン数はx軸上を0から出発してマイナス側にはみ出ることなく2×n手かけてまた0に戻って来る経路の総数に他な
らない
このせいで、x=0から出発してx≦-1の領域に接触することなくx=0に戻ってきて、最後にx=-1に至る、長さ2*n+1手の経路の総数もまたCn であることは確定的に明らか、
検算
以下、経路としては途中でx≦-1の領域に接触せず、最後にx=-1に至るものだけを考える。
0から出て1手で-1に至る経路の数は[ - ]の1種類、C_0 = 1 （一致）
0から出て3手で-1に至る経路の数は[ +- - ] の1種類、C_1 = 1（一致）
0から出て5手で-1に至る経路の数は
[++ -- - ]
[+- +- - ] の2種類、C_2 = 2 （一致）
0から出て7手で-1に至る経路の数は
[++ +- -- - ]
[++ -+ -- - ]
[++ -- +- - ]
[+- ++ -- - ]
[+- +- +- - ] の5種類、C_3 = 5（一致）
以下略、
数学的帰納法か何かによる証明も略（ﾏﾃ
