Evolton
方針
操作は隣り合う2枚を昇順にするだけなので，最小の札1がどのように左へ移動するかを追う。(1)では，1が最初から左2枚にないと仮定し，最後の の直前に左端が2でなければならないことを使う。(2)では，よい並びを左2枚の中の1または2の位置で4つに分ける。， はそれぞれ 通り。残りは と で，2を除くと「左端が1でない」 枚のよい並びに対応する。
解答
この操作は，隣り合う2枚を見て，左が右より大きいときだけ入れかえる操作である。したがって，数字1は隣の札と比べられるたびに，右から左へは動くが，左から右へ動くことはない。
(1)
数字1が最初に左から 番目にあるとする。 または なら， のうち少なくとも一方は1であり，主張は明らかである。
以下， とする。このとき最初の操作 では数字1は関係しない。前半の操作 では，数字1は操作 のときにだけ1つ左へ移る。その後の前半の操作は，数字1より右側の比較なので，数字1をさらに左へ動かさない。
後半の操作 では，数字1は右側から順に比較される中で，1つずつ左へ移る。最終的に並びが になるためには，最後の操作 の直前に，左から1番目と2番目が の順に並んでいなければならない。最後の でこの2枚が入れかわり，左端から となるからである。
ここで，最初の が終わった後から最後の の直前まで，左端の札は操作に関係しない。実際，その間に行われる操作は 以上だけであり，左端を動かさない。したがって，最初の の直後の左端の札は，最後の の直前の左端の札と同じであり，それは2である。
いま なので，最初の左2枚に数字1はない。最初の の直後の左端は， の小さい方である。これが2であるから， と の少なくとも一方は2である。
以上より，いずれの場合も である。
(2)
条件を満たす初期配置を「よい並び」と呼ぶ。 とする。(1)より，よい並びでは左2枚のうち少なくとも一方が1または2である。これを次の4つの場合に分ける。 の場合を考える。数字1は最小なので，左端にある限りどの操作でも右へ動かない。したがって残りの 枚が，数字を1ずつ小さく読み替えたときによい並びになればよい。つまり を に読み替えることで， 枚のよい並びと一対一に対応する。よってこの場合は 通りである。 の場合を考える。このとき最初の操作 で数字1は左端へ移る。その後は左端の1は動かず，残りの 枚に対して，同じ形の前半・後半の操作が行われる。したがって，1を取り除き，残りを1ずつ小さく読み替えることで，やはり 枚のよい並びと一対一に対応する。よってこの場合も 通りである。
次に，左2枚に1がない場合を考える。(1)より，左2枚のうち一方は2である。 の場合，最初の では入れかわりは起こらず，左端の2は最後の の直前まで左端に残る。ここで左端の2を取り除き，残りの数字のうち3以上を1ずつ小さく読み替えると， 枚のよい並びが得られる。このとき，もとの は3以上なので，読み替え後の左端は1ではない。
逆に，左端が1でない 枚のよい並びがあれば，先頭に2を挿入し，もとの数字1はそのまま，2以上の数字を1ずつ大きくすれば， のよい並びが得られる。したがってこの場合の個数は， 枚のよい並びのうち左端が1でないものの個数である。 枚のよい並びのうち左端が1であるものは，その1を取り除いて残りを1ずつ小さく読み替えると， 枚のよい並びと一対一に対応する。よって左端が1でないものは 通りである。 の場合も同様である。最初の で2が左端へ移り，その後は直前の場合と同じ構造になる。したがってこの場合も 通りである。
対応の小さい場合の確認として、直接列挙するとであり、 と一致する。
以上の4つの場合は互いに重ならず，すべてのよい並びを尽くしている。したがってである。
総評
難度7，計算量5。想定時間は25分前後。操作列そのものはバブルソートに似ているが，ここでは全体の整列過程を追うより，最小の札1と次に小さい札2の位置を追うのが有効である。(1)で左2枚に1または2が必要だと絞り込めると，(2)は4つの初期配置の場合分けになる。難所は「取り除いて読み替える」対応が本当に一対一であることの説明で，特に が左端1でない並びを数えていることを明記したい。 全順列列挙による の検算も行い、漸化式の符号と係数を確認した。