問題ＰＤＦ
下の図のような道に沿って、地点Ａから地点Ｂまで進みます。

次の問いに答えなさい。

（１）
図Ⅰの道を、右、上のどちらかの方向に進むとき、行き方は全部で何通りありますか。

（２）
図Ⅱの道を、右、上、右ななめ上のどれかの方向に進むとき、行き方は全部で何通りありますか。

＠解説＠
（１）

左と下を合わせていく。
機械的に調べていくと42通り。

（２）

２つか３つを足していくと90通り。

＠カタラン数＠

【１・２・５・14・42・132・429…】
この数列はカタラン数といい、中学受験でもたびたび登場する。
階段状の最短経路にはカタラン数があらわれる。
これを知っていると42通りとすぐでる。
132くらいまで覚えておくと便利かも。

では、なぜ42になるのか？？(´～`)

わかりやすいように、左上を足して全体を正方形にする。
Ｓ⇒Ｇは５つの→、５つの↑の並び替えで求められるから、
₁₀Ｃ₅＝252通り

全体の252通りから、少なくとも１つの★を通過する左上ルートを引けば、
カタラン数42がでてくるはず。

★のラインを対称の軸として線対称のルートを作成。
ＳとＳ’は対応するので、★までの場合の数がすべて等しい！
Ｓ’⇒Ｇは必ず１つの★を通り、６つの→、４つの↑だから、₁₀Ｃ₄＝210通り
階段上のＳ⇒Ｇは、252－210＝42通り

以上をまとめると、５番目のカタラン数は
₁₀Ｃ₅－₁₀Ｃ₄＝42で求められた。
カタラン数Ｃ_ｎ＝_2ｎＣ_ｎ－_2ｎＣ_ｎ－1となり、
これを高校数学でチャッチャカチャーと処理すると、、

となります。
６番目のカタラン数は、
Ｃ₆＝₁₂Ｃ₆/７＝132

（２）についてカタラン数で解けた方は、
ぜひ下のコメント欄かお問い合わせより教えてくださいませm(＿)m
公立高校入試解説ページに戻る