問題
を2以上の整数とする。1からまでの数字が書かれた札が各1枚ずつ合計枚あり，横一列におかれている。1以上以下の整数に対して，次の操作を考える。
左から番目の札の数字が，左から番目の札の数字よりも大きければ，これら2枚の札の位置を入れかえる。そうでなければ，札の位置をかえない。
最初の状態において札の数字は左からであったとする。この状態から回の操作を順に行った後，続けて回の操作を順に行ったところ，札の数字は左からと小さい順に並んだ。以下の問いに答えよ。
(1) とのうち少なくとも一方は2以下であることを示せ。
(2) 最初の状態としてありうる札の数字の並び方の総数をとする。が4以上の整数であるとき，をとを用いて表せ。
方針
操作は隣り合う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つの場合は互いに重ならず，すべてのよい並びを尽くしている。したがって
である。