問題ＰＤＦ
下の図のような道に沿って、地点Ａから地点Ｂまで進みます。
次の問いに答えなさい。
（１）
図Ⅰの道を、右、上のどちらかの方向に進むとき、行き方は全部で何通りありますか。
（２）
図Ⅱの道を、右、上、右ななめ上のどれかの方向に進むとき、行き方は全部で何通りありますか。
＠解説＠
（１）
左と下を合わせていく。
機械的に調べていくと42通り。
（２）
２つか３つを足していくと90通り。
＠カタラン数＠
【１・２・５・14・42・132・429…】
この数列はカタラン数といい、中学受験の世界にもたびたび登場する。
階段状の最短経路にはカタラン数があらわれる。
これを知っていると42通りとすぐだせる。
132くらいまで覚えておくと便利かも。
では、なぜ42になるのか？(´～`)
わかりやすいように、左上を足して全体を正方形にする。
Ｓ⇒Ｇは５つの→、５つの↑の並び替えで求められるから、
10Ｃ5＝252通り
全体の252通りから、少なくとも１つの★を通過する左上ルートを引けば、
カタラン数42がでてくるはず。
★のラインを対称の軸として線対称のルートを作成。
ＳとＳ’は対応するので、★までの場合の数がすべて等しい！
Ｓ’⇒Ｇは必ず１つの★を通り、６つの→、４つの↑だから、10Ｃ4＝210通り
階段上のＳ⇒Ｇは、252－210＝42通り
以上をまとめると、５番目のカタラン数は
10Ｃ5－10Ｃ4＝42で求められた。
カタラン数Ｃｎ＝2ｎＣｎ－2ｎＣｎ－1となり、
これを高校数学でチャッチャカチャーと処理すると、
となります。
６番目のカタラン数は、
Ｃ6＝12Ｃ6/７＝132
難関中（算数科）解説ページに戻る
コメント