数学A / 場合の数

山型に並ぶ順列

最難関編1対1対応順列

問題

1から8までの数を1つずつ使って一列に並べる。並びが、ある位置まで増加し、その位置から後は減少する「山型」になるものは何通りあるか。ただし、増加する部分と減少する部分は、頂上以外にそれぞれ1個以上の数を含むものとする。

ヒントを見る

山の頂上に来られる数は決まっていないか。頂上が決まれば、残りの数について決めるべきことは「どちら側に置くか」だけにならないか — 置く側さえ決まれば順番は勝手に決まる、という構造が見えるか。

解答・解説

並べ方を直接数えず、「各数を頂上の左右どちらに置くか」の振り分けに翻訳する。頂上は必ず8で、左に振り分けた数は増加順・右は減少順に並ぶしかないので、振り分けを決めると並びが1通りに確定する。

⓪ 発想 — どう考え始めるか。 「増えてから減る」並びを先頭から作ると、場合分けが絡まる。並びそのものではなく、各数の行き先を決めると考え直す。

まず頂上。増加から減少に切り替わる位置には、全体の最大値8しか来られない(8より大きい数はないから、8の左隣では増加が、右隣では減少が強制される)。

すると残りの $1$ 〜 $7$ は、「8の左側に入るか、右側に入るか」だけが自由だ。左側に入った数たちは増加順、右側は減少順と、並び方が1通りに確定する。並べ方と振り分け方の1対1対応だ。

重要並びが「選び方から一意に復元できる」とき、(並びの数)=(選び方の数)。復元の一意性が、数え漏れと二重数えのない理由になる

① 頂上は8。 山型の頂上(そこまで増加・そこから減少)より大きい数は左右のどちらにも置けない。だから頂上は最大の8に限る。

② 残り7個を左右に振り分ける。 $1$ 〜 $7$ の各数について「8の左側/右側」の2択で $2^{7} = 128$ 通り。左側に入った数の並びは増加順の1通り、右側は減少順の1通りに決まるから、振り分け1つにつき山型の並びがちょうど1つ対応する。

③ 両側1個以上の条件。 全部を左側に入れる(増加だけの並び)と、全部を右側に入れる(減少だけの並び)は山型にならないので除く:

$2^{7} - 2 = 128 - 2 = 126 通り$

まとめ: 「振り分けを決めると並びが勝手に決まる」構造を見抜くのが急所。数える対象を並びから部分集合の選び方に翻訳すると、一気に $2^{7}$ の世界に落ちる。

発展 — 一歩先へ。 一般の $n$ 個なら $2^{n - 1} - 2$ 通り。また「減ってから増える谷型」も、まったく同じ対応で同数になる(最小値1が谷底)。山と谷、答えまで対称だ。

答

$126$ 通り

頂上の位置ごとに数える(分布まで見える別集計)。 同じ答えを、頂上が左から何番目かで場合分けして数えることもできる。

頂上(=8)が左から $i$ 番目( $i = 2, \dots, 7$ )にあるとする。左側に入る $i - 1$ 個の数を $1$ 〜 $7$ から選べば( $_{7} C_{i - 1}$ 通り)、左は増加順・右は減少順で並びが確定する。よって

$i = 2 \sum 7_{7} C_{i - 1} =_{7} C_{1} +_{7} C_{2} + \dots +_{7} C_{6} = 2^{7} -_{7} C_{0} -_{7} C_{7} = 126$

答えは本解と同じだが、この集計はおまけの情報をくれる。頂上の位置ごとの内訳は $7, 21, 35, 35, 21, 7$ 。山の頂上は真ん中(4番目・5番目)に来やすく、その理由は二項係数の山型そのものだ。

数え方を変えると、答えだけでなく「分布」が見える。集計の切り口は情報量で選べる、という見本になっている。