東京大学の理系数学第5問は場合の数に関する出題でした。本問は「シェーカーソート」という効率の良いソート法が背景になっています。漸化式の立式までという少し珍しい出題です。
\( n \) を 2 以上の整数とする。1 から \( n \) までの数字が書かれた札が各 1 枚ずつ合計 \( n \) 枚あり、横一列におかれている。1 以上 \( (n-1) \) 以下の整数 \( i \) に対して、次の操作 \( (T_i) \) を考える。
\( (T_i) \) 左から \( i \) 番目の札の数字が、左から \( (i+1) \) 番目の札の数字よりも大きければ、これら 2 枚の札の位置を入れかえる。そうでなければ、札の位置をかえない。
最初の状態において札の数字は左から \( A_1, A_2, \dots, A_n \) であったとする。この状態から \( (n-1) \) 回の操作 \( (T_1), (T_2), \dots, (T_{n-1}) \) を順に行った後、続けて \( (n-1) \) 回の操作 \( (T_{n-1}), \dots, (T_2), (T_1) \) を順に行ったところ、札の数字は左から \( 1, 2, \dots, n \) と小さい順に並んだ。以下の問いに答えよ。
（１）\( A_1 \) と \( A_2 \) のうち少なくとも一方は 2 以下であることを示せ。
（２）最初の状態としてありうる札の数字の並び方 \( A_1, A_2, \dots, A_n \) の総数を \( c_n \) とする。\( n \) が 4 以上の整数であるとき、\( c_n \) を \( c_{n-1} \) と \( c_{n-2} \) を用いて表せ。
（2025年 東京大学 理科前期第5問）
（１）
\( A_1<A_2\) のとき、操作\( (T_1) \)で左端の2枚は入れ替わらない。このとき最終的に操作\( (T_{1}) \)が終わるまで左端の数字は\( A_1 \)である。問題文より、札の数字は左から \( 1, 2, \dots, n \) と小さい順に並んだとあるから\( A_1 \) と \( A_2 \) のうち少なくとも一方は 2 以下である。
\( A_1>A_2\) のとき、最初の操作\( (T_1) \)で左端の2枚は入れ替わり、\( A_2 \)が書かれた札が左端に来る。よって同様に\( A_1 \) と \( A_2 \) のうち少なくとも一方は 2 以下である。
よって、\( A_1 \) と \( A_2 \) のうち少なくとも一方は 2 以下である。
（２）
\(n \ge 4\) のとき，(1) の結果から，初期配置において左端の2枚については必ず以下のいずれかの状況となる：
-
- 場合 (I)： \( A_1 \in \{1,2\} \)
- 場合 (II)： \( A_2 \in \{1,2\} \)（このとき \( A_1 \notin \{1,2\} \)）
場合 (Ⅰ) のとき、さらに以下の場合に分けられる。
-
- 場合 (Ⅰ-a)： \( A_1 =1 \) のとき
1回目の操作\( (T_1) \)を行った後、左端の数字は入れ替わらず \( A_1 \) または \( A_2 \) であり、これは2回目の操作\( (T_1) \)を行った後も変わることはない。
左から \( 2 \) 番目の札以降の並び方は、数字の \( 2 \) から \( n \) を \( 1 \) から \( n-1 \) に読み替えてやれば、全部で \( c_{n-1} \) 通りと分かる。
-
- 場合 (Ⅰ-b)： \( A_2 =1 \) のとき
1回目の操作\( (T_1) \)を行った後、\( A_1 \) と \( A_2 \) の札は入れ替わる。これは2回目の操作\( (T_1) \)を行った後も変わることはない。
場合 (Ⅰ-a) と同様に、左から \( 2 \) 番目の札以降の数字を読み替えてやれば、並び方は全部で \( c_{n-1} \) 通りと分かる。
場合 (Ⅱ) のとき、さらに以下の場合に分けられる。
-
- 場合 (Ⅱ-a)： \( A_1 =2 \) のとき
- 場合 (Ⅱ-a)： \( A_1 =2 \) のとき
このとき、\( A_2 =1 \) または \( A_2 \ge 3 \) のいずれかである。
\( A_2 =1 \) のときは1回目の操作\( (T_1) \)を行った後に\( A_1 \) と \( A_2 \) の札が入れ替わるから、一連の操作\( (T_2) \)、…、 \( (T_2) \) の後に $1,2,3,…,n$ の並びになればよい。
\( A_2 \ge 3 \) のときは最後の操作\( (T_1) \)を行った後に\( A_1 \) と \( A_2 \) の札が入れ替わるから、一連の操作\( (T_2) \)、…、 \( (T_2) \) の後に $2,1,3,…,n$ の並びになればよい。
よって、 \( A_2 \) の値によらずに \( 1 \)、\( 3 \)、…、 \( n \) を \( 1 \) から \( n-1 \) に読み替えてやればよく、数字の並び方は全部で \( c_{n-1} \) 通りと分かる。
-
- 場合 (Ⅱ-b)： \( A_2 =2 \) のとき
このとき、\( A_1 =1 \) または \( A_1 \ge 3 \) のいずれかである。
\( A_1 =1 \) のときは1回目の操作\( (T_1) \)、2回目の操作\( (T_1) \) のいずれでも札は入れ替わらない。
\( A_1 \ge 3 \) のときは1回目の操作\( (T_1) \)、2回目の操作\( (T_1) \) のいずれでも\( A_1 \) と \( A_2 \) の札が入れ替わるから、一連の操作\( (T_2) \)、…、 \( (T_2) \) の後に $2,1,3,…,n$ の並びになればよい。
よって、場合 (Ⅱ-a)と同様に \( A_2 \) の値によらずに \( 1 \)、\( 3 \)、…、 \( n \) を \( 1 \) から \( n-1 \) に読み替えてやればよく、数字の並び方は全部で \( c_{n-1} \) 通りと分かる。
上記の場合分けのうち、場合 (Ⅰ-a)と場合 (Ⅱ-b)では \( A_1 =1 \) かつ \( A_2 =2 \) の場合を、場合 (Ⅰ-b)と場合 (Ⅱ-a)では \( A_1 =2 \) かつ \( A_2 =1 \) の場合を重複して数えている。このような数字の並び方は\( 3 \)、…、 \( n \) を \( 1 \) から \( n-2 \) に読み替えてやればよく、数字の並び方は全部で \( c_{n-2} \) 通りと分かる。
以上より、求める並び方の総数は全部で \( 4c_{n-1}-2c_{n-2} \) 通りと分かる。よって\[ \boxed{c_n=4c_{n-1}-2c_{n-2}} \] と表せる。
文字がごちゃごちゃしているので題意を正確に把握するところから始めます。「操作」の内容は単純で、順方向にソートするのが \( (T_1), (T_2), \dots, (T_{n-1}) \) で、折り返して逆方向にソートするのが \( (T_{n-1}), \dots, (T_2), (T_1) \) と定義され、仮定として「最終的な数字の列は \( 1, 2, \dots, n \) と小さい順に並んだ」というのが問題の設定です。つまり、１往復分のシェーカーソートでソートが完了したという状況です。そのような状況が実現される数字の並び方を求めたい、というのが本問の目的です。
シェーカーソートの例
（Wikipediaより引用）
（１）が（２）での考え方のヒントになっているので有効利用しましょう。重複を考慮して \( 4c_{n-1} \) から \(2c_{n-2}\) の分を引くのを忘れないようにしたいですね。
漸化式を $c_1=1$、$c_2=2$ の条件の下で解くと\[
c_n=\dfrac{1}{2\sqrt{2}}\left\{(\sqrt{2}-1)(2 + \sqrt{2})^n+(\sqrt{2}+1)(2- \sqrt{2})^n\right\}
\]となり、小さい順に 1, 2, 6, 20, 68, 232, 792, 2704, 9232, 31520,… となります。これはOEIS（オンライン整数列大辞典）のA006012として登録されています。
因みに、2025年3月現在、本問はChatGPTのo1 proを含むどのモデルでも正答が得られませんでした。DeepSeekのDeepThink機能でも正答が得られていません。現時点でのモデルは場合の数に関する推論が苦手なのかもしれません。