今回は中学受験必須の道順問題について2つのアプローチを紹介できるように内容を確認しましょう。また最後には少し面白い練習問題と題材を用意しましたのでぜひ生徒さんに紹介してあげてください！
まず大きくわけて道順問題の解き方は
（1）"組合せ"を用いる
（2）地図に順番に数字を振っていく
の2通りがあります。まず（1）について振り返ってみましょう。下のような問題を考えます。
問題：A地点からB地点までの行き方は（最短経路で）何通りあるか？
この場合はAからBまで9個の辺を通過するわけですが、そのうち4回↑を選ぶという問題だと考えることができます。よって9個から4個選ぶ方法として9×8×7×6/(4×3×2×1)=126通りとなります。同じ問題で（2）の"数字を順に振る"方法を行うと下図のようになります。
Aから右と上にすべて1を記入しているのは当然そこに行く方法が1通りしかないからです。（下や左に行けないから）残りの頂点に関しては、その頂点の1個下の頂点と1個左の頂点から来る2つがあるので合計値を記入していきます。するとB地点ではきちんと（1）の方法で出したときと同じ解答が出てきました。一見（1）の解法の方が計算一回で出て便利そうに見えるのですが、難しい問題になっていけばいくほど（2）の解き方をせざるを得ない場合が増えてきます。絶対に両方の解き方を教えておきましょう！最後に1問面白い問題を紹介してみます。パッと見道順問題には見えない問題ですが、どうやって解くのか皆さんも考えてみてください。
問題：男子4人、女子4人の計8人を前から後ろに並べたとき、前から任意の人数（1～8までの数字）を選んでも男子の数が女子の数より少なくなることが無いように並べる方法は何通りか？（男子どうし、女子どうしは区別が無いものとする）
皆さんがこの問題の解き方が分かりますか？キーとなるのは"どのような道を想定するか"です。それでは解答です！
まずは何も制約なく8人を並べる方法は、男子どうし・女子どうしの区別がないことから先ほど紹介したような4×4の正方形のマス上で最短経路を選ぶのと変わらず8×7×6×5/(4×3×2×1）=70通りとなります。
上図のようなマスで男子と女子の人数について考えるとどうなるでしょうか？この時右に行くと男子を並べ、上に行くと女子を並べると考えましょう。例えば上「15」と書いてある頂点では、並び方は何であれ男子2人に対して女子が4人並んでいることになります。このような頂点は問題の条件から考えると通ってはいけない頂点ということになります！同様に考えると考えるべき道順は下図のようになり解答は下図のようになります。
解答はよって14通りということになります。上の道のりは、元々の4×4の正方形上でAからBまで対角線を引いたときそれより上にある頂点を消去することによって導出されます。なぜならこのような頂点こそ"女子の数が男子の数を上回ってしまう"瞬間を意味するからです。このような数はカタラン数と呼ばれています。興味のある方はぜひ調べてみてください！
運営部おすすめ記事
理系のあなたにこそ読んでほしい。国語の本質とは？
