n を 2 以上の整数とする。1 から n までの数字が書かれた札が各 1 枚ずつ合計 n 枚あり，横一列におかれている。1 以上 (n-1) 以下の整数 i に対して，次の操作 (\mathrm{T}_i) を考える。
(\mathrm{T}_i) 左から i 番目の札の数字が，左から (i+1) 番目の札の数字よりも大きければ，これら 2 枚の札の位置を入れかえる。そうでなければ，札の位置をかえない。
最初の状態において札の数字は左から A_1, A_2, \ldots, A_n であったとする。この状態から (n-1) 回の操作 (\mathrm{T}_1), (\mathrm{T}_2), \ldots, (\mathrm{T}_{n-1}) を順に行った後，続けて (n-1) 回の操作 (\mathrm{T}_{n-1}), \ldots, (\mathrm{T}_2), (\mathrm{T}_1) を順に行ったところ，札の数字は左から 1, 2, \ldots, n と小さい順に並んだ。以下の問いに答えよ。
(1) A_1 と A_2 のうち少なくとも一方は 2 以下であることを示せ。
(2) 最初の状態としてありうる札の数字の並び方 A_1, A_2, \ldots, A_n の総数を c_n とする。n が 4 以上の整数であるとき，c_n を c_{n-1} と c_{n-2} を用いて表せ。
前向きの走査は、隣どうしを左から順に比べて、大きいほうを右へ送っていく動きです。1 回で最大の札が右端へ着きます。
後ろ向きの走査は、その逆です。小さいほうを左へ送っていくので、1 回で最小の札が左端へ着きます。
この 2 回だけで小さい順に並ぶ、というのが条件です。図で 1 手ずつ追ってみてください。
言いかえると、札は前向きの走査で左へ 1 つしか動けず、後ろ向きの走査で右へ 1 つしか動けません。遠くへ運ばれるのは、送られていく側になったときだけです。
前向きの走査で 1 番目の札に触るのは、最初の (\mathrm{T}_1) だけです。そこで小さいほうが 1 番目に残り、そのあと 1 番目は動きません。
つまり前向きの走査を終えた時点で、1 番目の札は A_1 と A_2 の小さいほうです。これを b_1 と書きます。
後ろ向きの走査で 1 番目に触るのも、最後の (\mathrm{T}_1) だけです。その直前までに、2 番目以降だけの走査が済んでいます。
2 番目以降だけの走査は、その中の最小値を 2 番目へ運びます。だから最後の (\mathrm{T}_1) の直前は、1 番目が b_1、2 番目が「残り全部の最小値」m という形です。
最後の (\mathrm{T}_1) は、b_1 と m を比べて小さいほうを 1 番目に置きます。終わったあとの先頭 2 枚は、b_1 と m を小さい順に並べたものです。
並び終わりは 1, 2, \ldots ですから、2 番目は 2 です。つまり b_1 と m のうち大きいほうが 2 で、両方とも 2 以下ということになります。
とくに b_1 \leqq 2 です。b_1 は A_1 と A_2 の小さいほうでしたから、A_1 と A_2 のうち少なくとも一方は 2 以下です。
これで (1) が示せました。ここで出てきた「先頭の 2 枚から小さいほうが抜ける」という形が、そのまま (2) の数え方になります。
最初の (\mathrm{T}_1) のあと、残りの前向きの走査は「y = \max(A_1,\ A_2), A_3, \ldots, A_n」という n-1 枚に対する同じ走査です。後ろ向きも、n-1 枚の走査を済ませてから最後に (\mathrm{T}_1) を行う形です。
b_1 = 1 のとき。最後の (\mathrm{T}_1) では入れかわらないので、n-1 枚がそのまま小さい順に並ぶことが条件です。つまり「y, A_3, \ldots, A_n」が n-1 枚の条件を満たす並びであればよく、1 と y の左右で 2 通りずつ。2c_{n-1} 通りです。
b_1 = 2 のとき。1 は 3 番目以降のどこかにいるので m = 1 となり、最後の (\mathrm{T}_1) で入れかわって先頭が 1, 2 とそろいます。3 番目以降がそろう条件は、やはり「y, A_3, \ldots, A_n」が n-1 枚の条件を満たすことです。
ただしこの場合は y > 2、つまり y は n-1 枚の中の最小ではありません。先頭が最小になる並びは、同じ議論から c_{n-2} 通りありますから、使えるのは c_{n-1}-c_{n-2} 通り。左右で 2 倍して 2(c_{n-1}-c_{n-2}) 通りです。
2 つの場合は重なりません。b_1 が 1 か 2 かで分かれており、(1) よりそれ以外は起こらないからです。
たして c_n = 2c_{n-1} + 2(c_{n-1}-c_{n-2}) = 4c_{n-1}-2c_{n-2} となります。これが答えです。
出発点は c_2 = 2、c_3 = 6 です。2 枚と 3 枚では、どの並びも 2 回の走査で小さい順に並びます。
漸化式を回すと c_4 = 20、c_5 = 68、c_6 = 232 と続きます。n! に比べるとずっとゆっくりで、条件がかなりきついことが分かります。