数学I・Aチェック＆リピート　第7章　§2順列・組合せ　10.最短経路

数学I・Aチェック＆リピート
隣り合う順列，隣り合わない順列 ← 最短経路 → 第8章　確率 ：同様に確からしい

問題文をクリックすると解答をみることができます．

最短経路 †

類題演習 †

最短経路は→と↑の同じものを含む順列に言い換えられます．

最短経路の典型問題です．

最短の道順は→と↑の順列に対応します．
(3)ではC，EをFに至る関所と考えましょう．

(ア)進む方法は2つです．
(イ)進む方向は3つです．3種類のものの順列を数えることになります．
P，Qの少なくとも一方を通る最短経路を除きましょう．

最短経路のとり方は→9個と↑6個の並べ方に対応します．

SからGの間の適切な場所に関所を設けて道順を場合分けしましょう．

「表，裏」を「→，↑」に換えると，裏表の出方の総数は最短経路の総数に一致します．

カタラン数 †

3つの条件を満たす書き込み方はある条件を満たす最短経路に置き換えられます．
カタラン数についての代表例として知られた問題です．