慶應義塾普通部２００８年算数第７問（解答・解説）
この問題は、カタラン数という有名な問題で、灘中学校でも９０年あたりに全く同じ問題が出されています。
１と８は、常に同じ位置にあります。
１ Ａ Ｂ Ｃ
Ｄ Ｅ Ｆ ８
（Ａ＜Ｂ＜Ｃ、Ｄ＜Ｅ＜Ｆ、Ａ＜Ｅ、Ｂ＜Ｆ）
Ａ、Ｂ、Ｃが決まれば、Ｄ、Ｅ、Ｆは自動的に決まることに注目すれば、少し楽ですね。
２がＡに入るかＤに入るかで場合分けしても解けますが、ここでは３の入る位置で場合分けして解きます。
（あ）Ａ＝３の場合
Ｄ＝２と確定します。
１ ３ Ｂ Ｃ
２ Ｅ Ｆ ８
Ｂ、Ｃに入れる数字の組み合わせは
（４×３）/（２×１） ←４個のものから２個選ぶ組合せですね。
＝６通り
あります。
このうち６、７という組み合わせだけは、Ｆ＜Ｂとなってしまい、条件を満たしません。
したがって、この場合は
６−１
＝５通り
あります。
（い）Ｄ＝３の場合
Ａ＝２と確定します。
１ ２ Ｂ Ｃ
３ Ｅ Ｆ ８
（あ）の場合と条件的に同じ（２（２がないから３となりますね）＜Ｂ＜Ｃ、３＜Ｅ＜Ｆ、Ｂ＜Ｆ）だから、この場合も５通りあります。 ←条件の対等性を利用して、作業を減らす！
（う）Ｂ＝３の場合
Ａ＝２と確定します。
１ ２ ３ Ｃ
Ｄ Ｅ Ｆ ８
Ｃが４〜７の４通りあり、残りは自動的に確定します。
この場合は４通りあります。
（あ）〜（う）以外の場合は考えられないから、求める場合は
５＋５＋４
＝１４通り ←同時に起こらない⇒和の法則
あります。
（別解）
上の列と下の列に左から順に〇を８個つけていきます。その際、常に上の列の〇の個数が下の列の〇の個数を下回らないようにします。
このように考えても同じことです。
道順の最短距離の場合の数の解法（数字を書き込む解法）に持ち込んで解きます。
上の列の〇の個数が下の列の〇の個数を下回らないのは、赤斜線の下側だけですね。
上の図より、求める場合の数は１４通りとなります。
わかりにくいかもしれないので、具体例で確認しておきます。
左側が条件を満たさない場合で、右側が条件を満たす場合になります。
