$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}$ を用いて表せ。
以下,記事全体を通じて次の記法を用いる。
$\varphi$ を単調非減少な実関数とし,列 $X$ に対して $\varphi(X)=(\varphi(X_1),\ldots,\varphi(X_m))$ と書く。このとき
$$
F(\varphi(X))=\varphi(F(X)).
$$
特に,相異なる実数から成る列 $X$ が整列可能であることは,$\operatorname{st}(X)\in\mathcal{C}_m$ と同値である。
$\varphi$ は単調非減少であるから $\varphi(\min\lbrace x,y\rbrace)=\min\lbrace\varphi(x),\varphi(y)\rbrace$,$\varphi(\max\lbrace x,y\rbrace)=\max\lbrace\varphi(x),\varphi(y)\rbrace$ であり,各 $(\mathrm{T}_i)$ は $\varphi$ と可換である。$F$ はそれらの合成であるから前半が従う。
後半について,$\psi(x)=\lvert\lbrace j\mid X_j\leqq x\rbrace\rvert$ とおくと,$\psi$ は単調非減少で $\operatorname{st}(X)=\psi(X)$ である。よって $F(\operatorname{st}(X))=\psi(F(X))$ であり,$\psi$ は $X$ の項の上で狭義単調増加であるから,$F(X)$ が増加列であることと $F(\operatorname{st}(X))=(1,\ldots,m)$ は同値である。
札の数字そのものではなく大小関係だけが本質であり,札を取り除いた列は標準化によって同型な小問題とみなせる。以下の削除・挿入の議論はすべてこの補題に依拠する。
第1位置に触れる操作は $(\mathrm{T}_1)$ だけであり,それは操作列の最初と最後にのみ現れる。したがって最初の $(\mathrm{T}_1)$ で第1位置に置かれた札は最後の $(\mathrm{T}_1)$ の直前まで動かず,その間の $2(n-2)$ 回の操作は第2位置以降に対する長さ $n-1$ の一往復そのものである。この凍結された札を番兵とよぶ。
$n\geqq 3$,$A\in\mathfrak{S}_n$ とし,$r=\min\lbrace A_1,A_2\rbrace$,$A^{\flat}=A\setminus r=(\max\lbrace A_1,A_2\rbrace,A_3,\ldots,A_n)$ とおく。
(a) $F(A)$ は,長さ $n$ の列 $(r,F(A^{\flat}))$ に $(\mathrm{T}_1)$ を1回施したものに等しい。
(b) $A\in\mathcal{C}_n\iff r\leqq 2\ \text{かつ}\ \operatorname{st}(A^{\flat})\in\mathcal{C}_{n-1}.$
(a) 最初の $(\mathrm{T}_1)$ の後の列は $(r,A^{\flat})$ である。続く $(\mathrm{T}_2),\ldots,(\mathrm{T}_{n-1}),(\mathrm{T}_{n-1}),\ldots,(\mathrm{T}_2)$ は第2位置以降だけに作用し,第2〜第 $n$ 位置を改めて第1〜第 $n-1$ 位置とみれば,長さ $n-1$ の列 $A^{\flat}$ に対する往路と復路にほかならない。よって最後の $(\mathrm{T}_1)$ の直前の列は $(r,F(A^{\flat}))$ である。
(b) $F(A^{\flat})$ の第1項を $y$ とすると,(a) より
$$
F(A)=\bigl(\min\lbrace r,y\rbrace,\ \max\lbrace r,y\rbrace,\ F(A^{\flat})_2,\ \ldots,\ F(A^{\flat})_{n-1}\bigr).
$$
($\Rightarrow$) $F(A)=(1,\ldots,n)$ ならば $\lbrace r,y\rbrace=\lbrace 1,2\rbrace$ ゆえ $r\leqq 2$ であり,$F(A^{\flat})=(3-r,3,4,\ldots,n)$ となる。これは $A^{\flat}$ の項の集合 $\lbrace 1,\ldots,n\rbrace\setminus\lbrace r\rbrace$ の昇順の並びであるから $A^{\flat}$ は整列可能であり,
補題2
より $\operatorname{st}(A^{\flat})\in\mathcal{C}_{n-1}$。
($\Leftarrow$) $r\in\lbrace 1,2\rbrace$ かつ $F(A^{\flat})$ が $\lbrace 1,\ldots,n\rbrace\setminus\lbrace r\rbrace$ の昇順の並びであるとする。$r=1$ なら $y=2$ で最後の $(\mathrm{T}_1)$ は交換せず,$r=2$ なら $y=1$ で交換する。いずれの場合も $F(A)=(1,2,\ldots,n)$。
(b) の右辺の $r\leqq 2$ が (1) の主張そのものであり,$\operatorname{st}(A^{\flat})\in\mathcal{C}_{n-1}$ が (2) の再帰を生む。局所的な観察が,(1) の証明と (2) の計数の双方を支配している。
番兵補題は先頭2位置の情報しか用いない。一方,往路・復路は累積最大値・最小値によって閉じた形に書け,これを閾値で 0-1 化すると,整列可能性は操作を含まない静的条件に帰着する。
実数列 $X=(X_1,\ldots,X_m)$($m\geqq 2$)に往路を施した列を $U$,さらに復路を施した列を $V=F(X)$ とし,
$$
M_i=\max\lbrace X_1,\ldots,X_i\rbrace,\qquad \mu_i=\min\lbrace U_i,\ldots,U_m\rbrace
$$
とおく。このとき $1\leqq i\leqq m-1$ に対して
$$
U_i=\min\lbrace M_i,X_{i+1}\rbrace,\quad U_m=M_m,\qquad V_1=\mu_1,\quad V_{i+1}=\max\lbrace U_i,\mu_{i+1}\rbrace.
$$
往路において,$(\mathrm{T}_i)$ の直前の列は $(U_1,\ldots,U_{i-1},M_i,X_{i+1},\ldots,X_m)$ である。実際 $i=1$ では明らかであり,$(\mathrm{T}_i)$ は $(M_i,X_{i+1})$ を $(\min\lbrace M_i,X_{i+1}\rbrace,M_{i+1})$ に置き換え,以後の往路は第 $i$ 位置に触れない。
復路において,$(\mathrm{T}_i)$ の直前の列は $(U_1,\ldots,U_i,\mu_{i+1},V_{i+2},\ldots,V_m)$ である。実際 $i=m-1$ では $\mu_m=U_m$ より成り立ち,$(\mathrm{T}_i)$ は $(U_i,\mu_{i+1})$ を $(\mu_i,\max\lbrace U_i,\mu_{i+1}\rbrace)$ に置き換え,以後の復路は第 $i+1$ 位置に触れない。
順列 $A\in\mathfrak{S}_n$ と $1\leqq k\leqq n-1$ に対して
$$
d_k(A)=\bigl\lvert\lbrace i\mid 1\leqq i\leqq k,\ A_i > k\rbrace\bigr\rvert
$$
とおく。先頭 $k$ 個の位置にある値のうち $d_k$ 個が $k$ を超えるから,$1,\ldots,k$ のうちちょうど $d_k$ 個が第 $k+1$ 位置以降にある。すなわち
$$
d_k(A)=\bigl\lvert\lbrace i\mid k < i\leqq n,\ A_i\leqq k\rbrace\bigr\rvert. \tag{D}
$$
$n\geqq 2$,$A\in\mathfrak{S}_n$ とする。
$$
A\in\mathcal{C}_n\iff d_k(A)\leqq 1\quad(1\leqq k\leqq n-1). \tag{P}
$$
すなわち,任意の $k$ について,先頭 $k$ 個の値のうち $k$ を超えるものは高々1個である。
$1\leqq k\leqq n-1$ に対し,$\varphi_k(x)=0\ (x\leqq k)$,$\varphi_k(x)=1\ (x > k)$ とおく。
0-1 化 順列 $Y$ が昇順であることは,すべての $k$ について $\varphi_k(Y)$ が広義単調増加であることと同値である。実際,$Y_i > Y_{i+1}$ となる $i$ があれば,$k=Y_{i+1}\ (\leqq n-1)$ に対して $\varphi_k(Y_i)=1 > 0=\varphi_k(Y_{i+1})$ となる。
補題2
より $\varphi_k(F(A))=F(\varphi_k(A))$ であるから,
$$
A\in\mathcal{C}_n\iff\text{すべての }k\text{ について }F(\varphi_k(A))\text{ が広義単調増加}.
$$
0-1 列の解析 $k$ を固定して $x=\varphi_k(A)$ とおく。$x$ は $0$ をちょうど $k$ 個含む。$x$ に
補題4
を適用し,往路後の列を $u$,復路後の列を $v$ とする。$v$ も $0$ をちょうど $k$ 個含むから,$v$ が広義単調増加であることは $v_1=\cdots=v_k=0$ と同値であり,$u$ は $0$ を含むから $v_1=\mu_1=0$ は常に成り立つ。
$u_1=\cdots=u_{k-1}=0$ ならば,残る $0$ が $u_k,\ldots,u_n$ の中にあるから $1\leqq i\leqq k-1$ で $\mu_{i+1}=0$,ゆえに $v_{i+1}=\max\lbrace u_i,\mu_{i+1}\rbrace=0$。逆に $v_{i+1}=0$ ならば $u_i=0$。よって
$$
v\ \text{が広義単調増加}\iff u_1=\cdots=u_{k-1}=0.
$$
一方 $u_i=\min\lbrace M_i,x_{i+1}\rbrace=1$ は「$x_{i+1}=1$ かつ $x_1,\ldots,x_i$ に $1$ がある」と同値であるから,$u_1=\cdots=u_{k-1}=0$ は「$x_1,\ldots,x_k$ に含まれる $1$ が高々1個」,すなわち $d_k(A)\leqq 1$ と同値である。
条件 (P) は $k=1$ と $k=n-1$ では自明に成り立つ($k=n-1$ で $n-1$ を超える値は $n$ のみ)。ここから次が直ちに従う。
| 着目する構造 | 数学的翻訳 | 対応する解法 |
|---|---|---|
| 第1位置に触れるのは最初と最後の $(\mathrm{T}_1)$ のみ | 番兵補題(補題3) | 本解 |
| 一方向の走査では逆行が高々1 | 移動限界 | 3.1 節 |
| 「値 $1,2$」と「位置 $1,2$」の組合せ | 4集合の包除 | 3.2 節 |
| 走査の累積構造 | 累積最大値・最小値(補題4) | 3.3 節 |
| 比較だけで決まる操作 | 0-1 化と条件 (P)(定理5) | 別解1 |
| (P) は値 $1,2$ を区別しない | 値の交換による全単射 | 別解1 |
| 境界を横切る矢印が各向き高々1本 | 直和分解,単一サイクル,三値符号 | 参考解1 |
| 禁止される局所配置 | パターン $3412,3421,4312,4321$ | 5.3 節 |
$n=2$ では $\lbrace A_1,A_2\rbrace=\lbrace 1,2\rbrace$ であり明らか。$n\geqq 3$ とする。最初の $(\mathrm{T}_1)$ により,第1位置には $r=\min\lbrace A_1,A_2\rbrace$ が置かれる。以後,最後の $(\mathrm{T}_1)$ までの操作 $(\mathrm{T}_2),\ldots,(\mathrm{T}_{n-1}),(\mathrm{T}_{n-1}),\ldots,(\mathrm{T}_2)$ はいずれも第1位置に触れないから,最後の $(\mathrm{T}_1)$ の直前の第1項は $r$ である。最後の $(\mathrm{T}_1)$ は第1項と第2項を小さい順に並べ替えるだけであり,その結果が $(1,2)$ であるから,直前の第1項と第2項は $\lbrace 1,2\rbrace$ を成す。したがって $r\in\lbrace 1,2\rbrace$,すなわち $A_1$ と $A_2$ のうち少なくとも一方は $2$ 以下である。
$n\geqq 4$ とする。$A\in\mathcal{C}_n$ に対し,$r=\min\lbrace A_1,A_2\rbrace$,札 $r$ の位置を $p\in\lbrace 1,2\rbrace$,$B=\operatorname{st}(A\setminus r)$ とおく。(1) より $r\in\lbrace 1,2\rbrace$ である。$r=1$,$r=2$ である $A\in\mathcal{C}_n$ の個数をそれぞれ $N_1,N_2$ とすると $c_n=N_1+N_2$。
場合 $r=1$ 対応 $A\mapsto(p,B)$ は $\lbrace A\in\mathcal{C}_n\mid r=1\rbrace$ から $\lbrace 1,2\rbrace\times\mathcal{C}_{n-1}$ への全単射である。実際,
補題3
(b) より $B\in\mathcal{C}_{n-1}$。逆に $(p,B)$ が与えられたとき,$B$ の各項に $1$ を加えた列に,値 $1$ の札が第 $p$ 位置に来るよう挿入した順列を $A$ とすれば,$\min\lbrace A_1,A_2\rbrace=1$ かつ $\operatorname{st}(A\setminus 1)=B\in\mathcal{C}_{n-1}$ であるから,
補題3
(b) より $A\in\mathcal{C}_n$ である。二つの対応は互いに逆である。よって
$$
N_1=2c_{n-1}.
$$
場合 $r=2$ このとき $1\notin\lbrace A_1,A_2\rbrace$ であるから,$A\setminus 2$ の第1項 $\max\lbrace A_1,A_2\rbrace$ は $3$ 以上であり,標準化($1\mapsto 1$,$j\mapsto j-1\ (j\geqq 3)$)の後も $B_1\geqq 2$ である。そこで
$$
\mathcal{C}_{n-1}^{+}=\lbrace B\in\mathcal{C}_{n-1}\mid B_1\neq 1\rbrace
$$
とおくと,$A\mapsto(p,B)$ は $\lbrace A\in\mathcal{C}_n\mid r=2\rbrace$ から $\lbrace 1,2\rbrace\times\mathcal{C}_{n-1}^{+}$ への全単射である。実際,逆に $(p,B)$ が与えられたとき,$B$ の $2$ 以上の項に $1$ を加えた列に,値 $2$ の札が第 $p$ 位置に来るよう挿入した順列を $A$ とすれば,先頭2項は $2$ と $B_1+1\ (\geqq 3)$ であるから $r=2$ であり,$\operatorname{st}(A\setminus 2)=B\in\mathcal{C}_{n-1}$ と
補題3
(b) より $A\in\mathcal{C}_n$ である。よって $N_2=2\lvert\mathcal{C}_{n-1}^{+}\rvert$。
先頭が $1$ の整列可能な列 $m=n-1\ (\geqq 3)$ とし,$B_1=1$ である $B\in\mathfrak{S}_m$ を考える。$\min\lbrace B_1,B_2\rbrace=1$,$B\setminus 1=(B_2,\ldots,B_m)$ であるから,
補題3
(b) より
$$
B\in\mathcal{C}_m\iff\operatorname{st}(B_2,\ldots,B_m)\in\mathcal{C}_{m-1}.
$$
$B\mapsto\operatorname{st}(B_2,\ldots,B_m)$ は先頭が $1$ の順列全体から $\mathfrak{S}_{m-1}$ への全単射であるから,$\lvert\lbrace B\in\mathcal{C}_{m}\mid B_1=1\rbrace\rvert=c_{m-1}=c_{n-2}$ である。ここで $m-1=n-2\geqq 2$ に $n\geqq 4$ を用いた。ゆえに
$$
\lvert\mathcal{C}_{n-1}^{+}\rvert=c_{n-1}-c_{n-2},\qquad N_2=2(c_{n-1}-c_{n-2}).
$$
結論
$$
c_n=N_1+N_2=2c_{n-1}+2(c_{n-1}-c_{n-2})=4c_{n-1}-2c_{n-2}\qquad(n\geqq 4).
$$
往路では,ある札が左へ動くのは $(\mathrm{T}_i)$ で第 $i+1$ 位置から第 $i$ 位置へ移るときに限り,以後の往路は第 $i$ 位置に触れない。したがって往路の間に各札が左へ動く距離は高々 $1$ である。同様に,復路の間に各札が右へ動く距離は高々 $1$ である。
$A_1\geqq 3$ かつ $A_2\geqq 3$ と仮定する。札 $1,2$ は初め第3位置以降にあり,往路で左へ高々1つしか動かないから,往路後も第2位置以降にある。よって往路後の第1位置の札 $x$ は $3$ 以上である。復路で $x$ は右へ高々1つしか動かないから,最終的に第1位置または第2位置にある。これは最終状態の先頭2枚が $1,2$ であることに反する。
補題4 より往路後の第1項は $U_1=\min\lbrace A_1,A_2\rbrace=r$ であり,「最終的に第1・第2位置に残る」という結論は 補題3 の番兵構造を移動距離の言葉で述べたものである。移動限界は往路の右向き・復路の左向きの移動を制限しない(往路で最大値 $n$ は右端まで一度に動く)。方向を取り違えると論証は成立しない。
$n\geqq 4$ とし,$\mathcal{C}_n$ の部分集合
$$
E_1=\lbrace A_1=1\rbrace,\quad E_2=\lbrace A_2=1\rbrace,\quad E_3=\lbrace A_1=2\rbrace,\quad E_4=\lbrace A_2=2\rbrace
$$
を考える。(1) より $\mathcal{C}_n=E_1\cup E_2\cup E_3\cup E_4$。
各集合の大きさ $v\in\lbrace 1,2\rbrace$ の札が第1位置または第2位置にある順列 $A$ について
$$
A\in\mathcal{C}_n\iff\operatorname{st}(A\setminus v)\in\mathcal{C}_{n-1} \tag{R}
$$
が成り立つ。$v=\min\lbrace A_1,A_2\rbrace$ のときは
補題3
(b) そのものである。そうでないのは $v=2$ かつ先頭2項が $\lbrace 1,2\rbrace$ のときに限り,このとき $A\setminus 1=(2,A_3,\ldots,A_n)$ と $A\setminus 2=(1,A_3,\ldots,A_n)$ は標準化すると一致するから,やはり (R) が成り立つ。値 $v$ の札が指定の位置にある順列全体から $\mathfrak{S}_{n-1}$ への写像 $A\mapsto\operatorname{st}(A\setminus v)$ は全単射(逆は値の復元と挿入)であり,(R) によりこれは $E_j$ を $\mathcal{C}_{n-1}$ の上へ1対1に写すから,
$$
\lvert E_j\rvert=c_{n-1}\qquad(j=1,2,3,4).
$$
共通部分 $E_1\cap E_2$,$E_3\cap E_4$,$E_1\cap E_3$,$E_2\cap E_4$ は空であり,空でないのは $E_1\cap E_4$(先頭が $(1,2)$)と $E_2\cap E_3$(先頭が $(2,1)$)のみで,3個以上の共通部分は空である。$E_1$ の対応で $E_1\cap E_4$ は $\lbrace B\in\mathcal{C}_{n-1}\mid B_1=1\rbrace$ に移り,$E_2$ の対応($A\setminus 1=(2,A_3,\ldots,A_n)$ を標準化すると先頭が $1$)で $E_2\cap E_3$ も同じ集合に移る。本解で示したとおり,いずれも $c_{n-2}$ 個である。
結論
$$
c_n=\sum_{j=1}^{4}\lvert E_j\rvert-\lvert E_1\cap E_4\rvert-\lvert E_2\cap E_3\rvert=4c_{n-1}-2c_{n-2}.
$$
$n=4$ では各 $E_j$ は6個(整列不能な4個は先頭2項が $\lbrace 3,4\rbrace$ であるから,先頭2位置に $1$ または $2$ がある順列はすべて整列可能),重複は各2個で,$4\cdot 6-2\cdot 2=20$。係数 $4$ と $-2$ は「4集合」と「2つの重複」として読める。本解の分類との関係は $N_1=\lvert E_1\cup E_2\rvert$,$N_2=\lvert(E_3\cup E_4)\setminus(E_1\cup E_2)\rvert$ である。
0-1 化を経ずに, 補題4 の閉じた式から直接 (P) を導く。往路後の列 $U$ に対する条件 $U_i\leqq i+1$ を中継点とする。
$A\in\mathfrak{S}_n$ とし,
補題4
の記号を $X=A$ として用いる。
段階1:$A\in\mathcal{C}_n\iff U_i\leqq i+1\ (1\leqq i\leqq n-1)$ 必要性は $i+1=V_{i+1}=\max\lbrace U_i,\mu_{i+1}\rbrace\geqq U_i$ による。十分性を示す。$V_1=\mu_1=1$ である。$1\leqq i\leqq n-1$ を固定すると,$j < i$ では $U_j\leqq j+1\leqq i$ である。
定理5 により,整列可能性は操作を含まない静的条件 (P) になる。小さい値の札を先頭付近から除くことは閾値を1つずらすだけであり,また (P) は値 $1$ と $2$ を区別しない。これらを用いると,操作を追跡せずに (1)(2) が得られる。
$n\geqq 3$,$A\in\mathfrak{S}_n$ とし,$v\in\lbrace 1,2\rbrace$ の札が第1位置または第2位置にあるとする。$A'=\operatorname{st}(A\setminus v)$ とおくと
$$
d_k(A')=d_{k+1}(A)\qquad(1\leqq k\leqq n-2).
$$
したがって $A\in\mathcal{C}_n\iff A'\in\mathcal{C}_{n-1}$。
$k+1\geqq 2$ であるから,$A$ の先頭 $k+1$ 個の位置は値 $v$ と $A\setminus v$ の先頭 $k$ 項から成り,$v\leqq 2\leqq k+1$ は数えられない。標準化は値 $w\neq v$ を $\sigma(w)=w-[\,w > v\,]$ に写す($[\,\cdot\,]$ は条件が真なら $1$,偽なら $0$)。$w > v$ なら $\sigma(w)=w-1$ であり,$w < v$ なら $w=1=\sigma(w)$ であるから,いずれの場合も $w > k+1\iff\sigma(w) > k$ が成り立つ。よって $d_{k+1}(A)=d_k(A')$。$d_1(A)\leqq 1$ は常に成り立つから, 定理5 より後半が従う。
(1):
定理5
で $k=2$ とすれば $d_2(A)\leqq 1$,すなわち $A_1$ と $A_2$ のうち少なくとも一方は $2$ 以下である。
(2):$n\geqq 4$ とし,$\mathcal{C}_n$ を札 $1$ の位置で
$$
X=\lbrace A\in\mathcal{C}_n\mid 1\in\lbrace A_1,A_2\rbrace\rbrace,\qquad Y=\lbrace A\in\mathcal{C}_n\mid 1\notin\lbrace A_1,A_2\rbrace\rbrace
$$
に分ける。
$A$ を置換 $\pi(i)=A_i$ とみて,数直線上の各 $i$ から $\pi(i)$ へ矢印を引く。$d_k$ は境界 $k+\frac12$ を右向きに横切る矢印の本数であり,(D) より左向きの本数でもある。(P) は「どの境界も各向きに高々1本の矢印しか横切らない」ことを意味する。矢印が横切らない境界で置換を分割し(直和分解),分割できない成分を単一のサイクルとして符号化して数える。
長さ $\ell$ の順列 $\beta$ が既約であるとは,$d_t(\beta)=1\ (1\leqq t\leqq\ell-1)$ が成り立つこととする($\ell=1$ では $\beta=(1)$)。長さ $\ell$ の既約な順列の個数を $a_\ell$ とする。
$\pi\in\mathfrak{S}_n$ に対し,$d_k(\pi)=0$ となる $k$ に $0,n$ を加えて $0=k_0 < k_1 < \cdots < k_s=n$ とし,$I_j=\lbrace k_{j-1}+1,\ldots,k_j\rbrace$,$\ell_j=k_j-k_{j-1}$ とおく($d_0=d_n=0$ と約束する)。
(a) $\pi(I_j)=I_j$ であり,$\pi$ の $I_j$ への制限を標準化した順列を $\beta_j\in\mathfrak{S}_{\ell_j}$ とすると,$k_{j-1}\leqq k\leqq k_j$ に対して $d_k(\pi)=d_{k-k_{j-1}}(\beta_j)$。
(b) $\pi\in\mathcal{C}_n$ であるための必要十分条件は,すべての $\beta_j$ が既約であることである。
(c) 逆に,$n$ の組成 $\ell_1+\cdots+\ell_s=n\ (\ell_j\geqq 1)$ と既約な $\beta_j\in\mathfrak{S}_{\ell_j}$ を任意に与え,$\beta_j$ を区間 $I_j$ 上に平行移動して並べた置換を $\pi$ とすると,$\pi\in\mathcal{C}_n$ であり,(a) の分解で $(\beta_1,\ldots,\beta_s)$ が復元される。
(a) $d_k(\pi)=0\iff\pi(\lbrace 1,\ldots,k\rbrace)=\lbrace 1,\ldots,k\rbrace$ であるから,$\pi$ は $\lbrace 1,\ldots,k_{j-1}\rbrace$ と $\lbrace 1,\ldots,k_j\rbrace$ を保ち,したがって $I_j$ を保つ。$k_{j-1}\leqq k\leqq k_j$ のとき,位置 $i\leqq k_{j-1}$ の値は $k_{j-1}$ 以下で数えられず,位置 $k_{j-1} < i\leqq k$ の値は $I_j$ に属して $\pi(i) > k\iff\beta_j(i-k_{j-1}) > k-k_{j-1}$ である。
(b) $k_{j-1} < k < k_j$ では定義より $d_k(\pi)\geqq 1$ であるから,これらの $k$ で (P) は $d_k(\pi)=1$,すなわち (a) より $d_t(\beta_j)=1\ (1\leqq t\leqq\ell_j-1)$ と同値である。分点では $d_k=0$ である。
定理5
より従う。
(c) 構成した $\pi$ は各 $I_j$ を保つから,(a) と同じ計算により分点では $d_k(\pi)=0$,$I_j$ の内部の境界では $d_k(\pi)=d_t(\beta_j)=1$ である。よって $d_k(\pi)=0$ となる $k$ はちょうど分点であり,(P) が成り立つ。
$\ell\geqq 2$ とする。
(a) $\beta\in\mathfrak{S}_\ell$ が既約であることは,$\beta$ が固定点と長さ2以上の1個のサイクル $C$ から成り,$1,\ell\in C$ であって,各 $t\ (1\leqq t\leqq\ell-1)$ について $C\cap\lbrace 1,\ldots,t\rbrace$ が $C$ の巡回順序で連続した1つの弧を成すことと同値である。
(b) $a_\ell=3^{\ell-2}$。
サイクル $C$ が境界 $t$ を跨ぐとは,$C$ が $t$ 以下の点と $t$ を超える点の両方を含むことをいう。矢印に沿って $C$ を一周すると,$C\cap\lbrace 1,\ldots,t\rbrace$ は巡回順序でいくつかの極大な弧に分かれ,各弧からはちょうど1本の矢印が $t$ を超える点へ出る。よって $d_t(\beta)$ は,$t$ を跨ぐ各サイクルにおける弧の個数の総和である。
(a) ($\Rightarrow$) 各 $t$ で $d_t=1$ であるから,$t$ を跨ぐサイクルはちょうど1個で,その中で $\lbrace 1,\ldots,t\rbrace$ に属する点は1つの弧を成す。$1$ を含むサイクルを $C$ とすると,$d_1=1$ より $\beta(1)\neq 1$ で $C$ は長さ2以上である。$M=\max C < \ell$ と仮定する。境界 $M$ を跨ぐサイクル $C'$ は $C$ と異なり,$M\in C$ より $\min C' < M$ である。すると境界 $\min C'$ を $C$ と $C'$ がともに跨ぎ,矛盾する。ゆえに $\ell\in C$ であり,$C$ はすべての境界を跨ぐ。$C$ 以外に長さ2以上のサイクル $C''$ があれば,境界 $\min C''$ を $C$ とともに跨ぐから,$C$ 以外はすべて固定点である。($\Leftarrow$) 固定点は寄与せず,$C$ は各境界を跨いで寄与 $1$ を与えるから $d_t=1$。
(b) $C$ の点を $1=s_1 < s_2 < \cdots < s_m=\ell$ とする。$s_j\leqq t < s_{j+1}$ のとき $C\cap\lbrace 1,\ldots,t\rbrace=\lbrace s_1,\ldots,s_j\rbrace$ であるから,(a) の弧条件は「各 $j\ (1\leqq j\leqq m-1)$ について $\lbrace s_1,\ldots,s_j\rbrace$ が弧を成す」ことである。$C$ を
$$
\ell\to w_1\to w_2\to\cdots\to w_{m-1}\to\ell
$$
と書くと,点集合 $\lbrace s_1,\ldots,s_m\rbrace$ 上の有向サイクルと,$s_1,\ldots,s_{m-1}$ の並べ方 $w=(w_1,\ldots,w_{m-1})$ は1対1に対応し,$\ell$ を含まない弧は $w$ の連続部分にほかならない。したがって条件は「各 $j$ について $\lbrace s_1,\ldots,s_j\rbrace$ が $w$ の連続部分を成す」ことである。$\lbrace s_1,\ldots,s_{j-1}\rbrace$ と $\lbrace s_1,\ldots,s_j\rbrace$ がともに連続部分であるのは,$s_j$ が前者の左端または右端に隣接するときに限るから,これは $w$ が $(s_1)$ から出発して $s_2,\ldots,s_{m-1}$ を順に左端または右端へ付け加えて得られることと同値であり,その個数は $2^{m-2}$ である。内部の値 $2,\ldots,\ell-1$ のうち $C$ に属する $m-2$ 個の選び方と合わせて
$$
a_\ell=\sum_{m=2}^{\ell}\binom{\ell-2}{m-2}2^{m-2}=3^{\ell-2}.
$$
(b) の数え方は次の三値符号と同じである:内部の値 $t=2,3,\ldots,\ell-1$ を小さい順に処理し,各 $t$ に $0$(固定点),$\mathrm{L}$(列 $w$ の左端に付加),$\mathrm{R}$(右端に付加)のいずれかを独立に割り当てる。$w=(1)$ から始めて列を作り,最後に $\ell\to w_1\to\cdots\to\ell$ とサイクルを閉じる。
定理5
により $\mathcal{C}_n$ は条件 (P) で特徴付けられる。
段階2
補題7
により,$\mathcal{C}_n$ の元は既約な順列の直和として一意に表される。最初の成分の長さ $\ell$ で分類して
$$
c_n=\sum_{\ell=1}^{n}a_\ell\,c_{n-\ell}\qquad(n\geqq 1,\ c_0=1). \tag{B}
$$
段階3
補題8
により $a_1=1$,$a_\ell=3^{\ell-2}\ (\ell\geqq 2)$。
段階4(差分による消去) $n\geqq 3$ とする。(B) を $n$ と $n-1$ について書き,後者を用いると
$$
\begin{aligned}
c_n&=c_{n-1}+c_{n-2}+\sum_{\ell=3}^{n}3^{\ell-2}c_{n-\ell}
=c_{n-1}+c_{n-2}+3\sum_{\ell=2}^{n-1}3^{\ell-2}c_{(n-1)-\ell}\\
&=c_{n-1}+c_{n-2}+3(c_{n-1}-c_{n-2})=4c_{n-1}-2c_{n-2}.
\end{aligned}
$$
特に $n\geqq 4$ で求める漸化式が成り立つ。
段階4'(母関数) 形式的べき級数 $G(x)=\sum_{n\geqq 0}c_nx^n$,$W(x)=\sum_{\ell\geqq 1}a_\ell x^\ell=x+\dfrac{x^2}{1-3x}$ を用いると,(B) は $G=1+WG$ と同値であり,
$$
G(x)=\frac{1}{1-W(x)}=\frac{1-3x}{(1-x)(1-3x)-x^2}=\frac{1-3x}{1-4x+2x^2}.
$$
$(1-4x+2x^2)G(x)=1-3x$ の $x^n$ の係数を比べて,$n\geqq 2$ で $c_n-4c_{n-1}+2c_{n-2}=0$。
以下は,上記のいずれかと発想の核を共有するか,表現の置き換えにとどまるため,独立の解法として扱わない。
| 解法 | 主に利用する構造 | 対象 | 範囲 | 長所 | 注意点 |
|---|---|---|---|---|---|
| 本解 | 番兵(第1位置の凍結) | (1)(2) | 高校 | (1) と (2) が同じ補題から出る | $r=2$ での制約 $B_1\neq 1$ |
| 3.1 移動限界 | 一方向走査での逆行は高々1 | (1) | 高校 | 操作の局所性を一般的な形で表す | 移動方向の取り違え |
| 3.2 包除原理 | 値と位置の4事象 | (2) | 高校 | 係数 $4,-2$ が対称に現れる | $E_3,E_4$ で先頭が $\lbrace 1,2\rbrace$ の場合 |
| 3.3 累積表示 | 累積最大値・最小値 | 定理5 | 高校 | 操作を式で追跡する | 各 $i$ ごとの同値は偽 |
| 別解1 | 静的条件 (P),閾値シフト,値の交換 | (1)(2) | 高校〜発展 | 削除補題が一行になる | 定理5の証明が前提 |
| 参考解1 | 直和分解,単一サイクル,母関数 | (2),一般項 | 大学 | 係数と特性根の由来が分かる | 付加の順序,既約性の確認 |
試験場での第一選択は本解である。(1) の観察がそのまま (2) の分類軸になり,必要な道具は場合分け・全単射・漸化式に限られ,補正項の意味($B_1\neq 1$)も論証の中に明示的に現れる。3.2 節の包除は係数 $4$,$-2$ を対称な形で説明し,別解1は (P) を一度確立すれば削除の議論が閾値のずれだけで済むことを示す。参考解1は答案としては過剰であるが,漸化式の係数と特性根 $2\pm\sqrt2$ が既約成分の個数 $3^{\ell-2}$ から生じることを明らかにする。
本問から抽出される手順を,操作で定義された対象を数える問題一般に適用できる形で述べる。
| 症状 | 検討する道具 | 本問での例 |
|---|---|---|
| 比較交換だけから成る操作 | 標準化不変性,0-1 化 | 補題2,定理5 |
| ある位置に触れる操作が少ない | 番兵(凍結される位置) | 補題3 |
| 一方向の走査で移動に偏りがある | 移動限界 | 3.1 節 |
| 走査の結果を式で書きたい | 累積最大値・最小値 | 補題4 |
| 特定の札の除去で規模が1下がる | 全単射と漸化式 | 本解 |
| 場合分けが重複する | 包除原理 | 3.2 節 |
| 条件がいくつかの値を区別しない | 値の交換による全単射 | 別解1 |
| 全閾値で境界を横切る量が有界 | 直和分解,サイクル構造,母関数 | 参考解1 |
| 事項 | 高校数学での扱い | 一般理論 |
|---|---|---|
| 比較交換 | $\min$,$\max$ と場合分け | 比較交換ネットワーク,0-1 原理 |
| 整列可能性 | (1) の局所条件,番兵 | 閾値条件 (P),パターン回避 |
| 計数 | 全単射,場合分け,包除原理 | 置換のサイクル分解,直和分解,母関数 |
| 漸化式の解 | 隣接3項間漸化式と特性方程式 | 有理母関数,漸近評価 |
| 対称性 | 扱わない | 逆置換・逆補置換,往路と復路の順序交換 |
| 統計量 | 扱わない | 固定点の分布と Pell 数 |
本解,3.1 節,3.2 節は左欄で完結する。 定理5 と別解1は抽象度が高いが証明は初等的である。参考解1と以下の各節は右欄に属する。
補題2
の可換性は $\min,\max$ の単調性だけから従う。
発展 固定された比較交換の列(比較交換ネットワーク)について,すべての 0-1 列を整列するならば任意の入力を整列する,という 0-1 原理が知られている(Knuth『The Art of Computer Programming』第3巻 5.3.4 節)。
定理5
の証明はこれを入力ごとに精密化したものであり,順列 $A$ が整列されることは,$n-1$ 個の閾値像 $\varphi_k(A)$ がすべて整列されることと同値である。閾値 $k$ の 0-1 列では $0$ の個数 $k$ が保存されるため,整列条件は先頭 $k$ 項に含まれる $1$ の個数の条件に落ちる。
$A\in\mathfrak{S}_n$ について,$A\in\mathcal{C}_n$ であるための必要十分条件は,
$$
i_1 < i_2 < i_3 < i_4,\qquad\min\lbrace A_{i_1},A_{i_2}\rbrace > \max\lbrace A_{i_3},A_{i_4}\rbrace
$$
を満たす添字が存在しないこと,すなわち $A$ がパターン $3412,\ 3421,\ 4312,\ 4321$ のいずれも含まないことである。
(P) が成り立たず $d_t(A)\geqq 2$ とする。位置 $i_1 < i_2\leqq t$ の値が $t$ を超え,(D) より位置 $t < i_3 < i_4$ の値が $t$ 以下であるから,$\min\lbrace A_{i_1},A_{i_2}\rbrace > t\geqq\max\lbrace A_{i_3},A_{i_4}\rbrace$。
逆に,そのような $i_1 < i_2 < i_3 < i_4$ があるとし,$u=\min\lbrace A_{i_1},A_{i_2}\rbrace$,$w=\max\lbrace A_{i_3},A_{i_4}\rbrace\ (w < u)$ とおく。$i_2\leqq u-1$ ならば $t=i_2$ とすると,位置 $i_1,i_2\leqq t$ の値は $u > t$ 以上であるから $d_t(A)\geqq 2$。$i_2\geqq u$ ならば $w < u\leqq i_2 < i_3$ であり,$t=w$ とすると位置 $i_3,i_4 > t$ の値は $t$ 以下であるから,(D) より $d_t(A)\geqq 2$。いずれの $t$ も $1\leqq t\leqq n-1$ を満たす。
定理5
より従う。
したがって $\bigcup_n\mathcal{C}_n$ は「部分列をとって標準化する」操作で閉じた順列のクラスであり,その基底(極小な禁止パターン)は長さ4の上記4個である。4パターンはいずれも「大きい2個が小さい2個に先行する」配置であり,(1) はその最も端的な場合($i_1,i_2=1,2$ で,$i_3,i_4$ が札 $1,2$ の位置)にあたる。
$\mathcal{C}_n$ は逆置換 $\pi\mapsto\pi^{-1}$ と逆補置換 $\pi\mapsto\rho\pi$,$(\rho\pi)(i)=n+1-\pi(n+1-i)$ で閉じている。さらに,復路を先に,往路を後に行う操作を $F'$ とすると,$F'$ で整列する順列全体も $\mathcal{C}_n$ に一致する。
(D) より
$$
d_k(\pi^{-1})=\bigl\lvert\lbrace j\leqq k\mid\pi^{-1}(j) > k\rbrace\bigr\rvert=\bigl\lvert\lbrace i > k\mid\pi(i)\leqq k\rbrace\bigr\rvert=d_k(\pi),
$$
$$
d_k(\rho\pi)=\bigl\lvert\lbrace i\leqq k\mid\pi(n+1-i) < n+1-k\rbrace\bigr\rvert=\bigl\lvert\lbrace i' > n-k\mid\pi(i')\leqq n-k\rbrace\bigr\rvert=d_{n-k}(\pi)
$$
であるから,いずれも (P) を保つ。次に,列に対しても $(\rho X)_j=n+1-X_{n+1-j}$ と定めると,$(\mathrm{T}_i)$ が第 $i,i+1$ 項に施す $(\min,\max)$ は,$\rho X$ の第 $n-i,n+1-i$ 項に対する $(\min,\max)$ に対応する。すなわち $\rho\circ\mathrm{T}_i=\mathrm{T}_{n-i}\circ\rho$ である。$F$ は $(\mathrm{T}_1),\ldots,(\mathrm{T}_{n-1}),(\mathrm{T}_{n-1}),\ldots,(\mathrm{T}_1)$ の順に施す操作であるから $\rho\circ F=F'\circ\rho$ となり,$\rho(1,\ldots,n)=(1,\ldots,n)$ より $F(\pi)=(1,\ldots,n)\iff F'(\rho\pi)=(1,\ldots,n)$。よって $F'$ で整列する順列全体は $\rho(\mathcal{C}_n)=\mathcal{C}_n$。
操作の上では,$F$ は先に最大値を右端へ,$F'$ は先に最小値を左端へ運ぶため挙動が異なり,両者の整列可能集合の一致は (P) を経由しなければ見えにくい。また (1) を $\rho A$ に適用すると,鏡像の主張「$A_{n-1}$ と $A_n$ のうち少なくとも一方は $n-1$ 以上」を得る。
比較交換の回数はともに $2(n-1)$ であるが,往路を2回行う操作と,往路・復路を1回ずつ行う本問の操作とでは,整列できる順列の個数が異なる。一方向の走査を $k$ 回行って整列する順列は,各値の左にあるそれより大きい値が高々 $k$ 個であるものに限られ,その個数は $k!\,(k+1)^{n-k}\ (n\geqq k)$ である(Knuth,同書 5.2.2 節)。
| $n$ | $4$ | $5$ | $6$ | $7$ | $8$ |
|---|---|---|---|---|---|
| 往路1回 $2^{n-1}$ | $8$ | $16$ | $32$ | $64$ | $128$ |
| 往路2回 $2\cdot 3^{n-2}$ | $18$ | $54$ | $162$ | $486$ | $1458$ |
| 往路と復路 $c_n$ | $20$ | $68$ | $232$ | $792$ | $2704$ |
増加率は往路2回の $3$ に対し,一往復では $2+\sqrt2\approx 3.414$ である。一方向の走査は逆向きの移動を1回あたり高々1に制限する(3.1 節)のに対し,一往復は移動距離ではなく「境界を横切る札の数」を制限する。この制約の型の違いが増加率の差に現れている。
特性方程式 $\lambda^2-4\lambda+2=0$ の解は $\lambda=2\pm\sqrt2$ である。漸化式は $n=3$ でも $c_3=6=4c_2-2c_1$ として成り立つ(参考解1の段階4)から,$c_1=1$,$c_2=2$ を初期値として,$n\geqq 1$ で
$$
c_n=\frac{(2+\sqrt2)^{n-1}+(2-\sqrt2)^{n-1}}{2}=\sum_{j\geqq 0}\binom{n-1}{2j}2^{\,n-1-j}.
$$
右辺は $n=1,2$ で $1,2$ を与え,同じ漸化式を満たす。$0 < 2-\sqrt2 < 1$ より $c_n\sim\frac12(2+\sqrt2)^{n-1}$ である。
発展:固定点の分布 $\pi$ に固定点 $p$ を挿入した順列を $\pi'$ とすると,$d_k(\pi')=d_k(\pi)\ (k < p)$,$d_k(\pi')=d_{k-1}(\pi)\ (k\geqq p,\ d_0=0)$ が成り立ち,(P) は保たれる。逆に固定点の削除でも (P) は保たれ,削除によって新たな固定点は生じない。したがって固定点をちょうど $h$ 個もつ $\mathcal{C}_n$ の元の個数を $f_{n,h}$ とすると $f_{n,h}=\binom{n}{h}f_{n-h,0}$ である。固定点をもたない元は,三値符号で $0$ を用いず長さ1の成分も含まないものであるから,その母関数は
$$
\frac{1}{1-\frac{x^2}{1-2x}}=\frac{1-2x}{1-2x-x^2}
$$
となり,$f_{m,0}=P_{m-1}$(Pell 数:$P_0=0$,$P_1=1$,$P_j=2P_{j-1}+P_{j-2}$)を得る。固定点を変数 $z$ で数える二変数母関数は
$$
\sum_{n,h}f_{n,h}\,x^nz^h=\frac{1}{1-xz-\dfrac{x^2}{1-(2+z)x}}
$$
であり,$z=1$ で $G(x)$ に戻る。
| 設問 | 結論 | 根拠 |
|---|---|---|
| (1) | $A_1$ と $A_2$ のうち少なくとも一方は $2$ 以下 | 番兵 $\min\lbrace A_1,A_2\rbrace$ は最後の $(\mathrm{T}_1)$ まで第1位置に留まる |
| (2) | $c_n=4c_{n-1}-2c_{n-2}\ (n\geqq 4)$ | $r=1$ が $2c_{n-1}$ 個,$r=2$ が $2(c_{n-1}-c_{n-2})$ 個 |
| 参考 | $c_2=2,\ c_3=6,\ c_4=20,\ c_5=68$ | 定理5による直接計数 |
| 参考 | $c_n=\dfrac{(2+\sqrt2)^{n-1}+(2-\sqrt2)^{n-1}}{2}$ | 特性方程式 $\lambda^2-4\lambda+2=0$ |