カタラン数

4時ごろまで勉強に来る生徒が少なく、やっぱり夏休みまで塾に来たくないよな、などと思っていたら、今5時になって、急に人数が増えました。

ということは、暑いうちは外に出たくない、ということだったのでしょうか …

その辺のところは不明ですが、頑張ってほしいです。

今日はちょっと数学をしましょう。

原点から格子線上のみを通って ( 10, 5 ) に至る最短経路は15C5通りありますが、このうち原点を除いて y<x を満たす領域のみを通過していくものは何通りでしょうか？

こういった計算をする方法を「カタラン数」と言います。

通常のやり方は、15C5通りから不適な経路数を引くというものです。

すなわち、最初に ( 0, 1 ) に行く 14C4 通りは不適で、さらに ( 1, 0 ) から y=x 上の点を経て ( 10, 5 ) に行くものも不適です。

この後者の数え方が一つの技術になっていますが、最初に y=x 上にたどり着いた後を y=x に関して折り返すと ( 1, 0 ) から ( 5, 10 ) への最短経路を数えることになります。これも14C4 通りあるので、求める経路数は 15C5-2×14C4=1001 通りです。

おぉ、そうするのか！

この説明を初めて聞いた諸君は大体、このように反応します。

でも、今日、この1001通りを数え上げた生徒がいました。しかも答えは合っていました。

ちょっと驚きです。

まあ、数学はああでもないこうでもないと先人が試行錯誤した軌跡を辿るところから始まるので、さわやかな感動を伴いながら学びを進めてほしいものです。