0

2025年 東京大学 理系 第5問

3
0
$$$$
2025年 東京大学 理系 第5問

$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.1 記法と操作の定式化

以下,記事全体を通じて次の記法を用いる。

  • 実数列 $X=(X_1,\ldots,X_m)$ に対し,$(\mathrm{T}_i)$ を「第 $i$ 項と第 $i+1$ 項の組 $(x,y)$ を $(\min\lbrace x,y\rbrace,\max\lbrace x,y\rbrace)$ に置き換える操作」と読む。これは $x > y$ のときに限り交換するという問題文の規則と一致する($x=y$ の場合も含む)。
  • $(\mathrm{T}_1),\ldots,(\mathrm{T}_{m-1})$ を順に行う操作を往路,$(\mathrm{T}_{m-1}),\ldots,(\mathrm{T}_1)$ を順に行う操作を復路とよび,往路に続けて復路を行う操作全体を $F$ と書く($m=1$ では $F$ は恒等写像とする)。
  • $F(X)$ が広義単調増加であるとき,$X$ は整列可能であるという。$1,\ldots,n$ の順列 $A$ については,これは $F(A)=(1,2,\ldots,n)$ を意味する。
  • $1,\ldots,n$ の順列全体を $\mathfrak{S}_n$,そのうち整列可能なもの全体を $\mathcal{C}_n$ とし,$c_n=\lvert\mathcal{C}_n\rvert$ とおく。問題の $c_n$ はこれと一致し,$c_1=1$ である。参考解1では便宜上 $c_0=1$ とおく。
  • 順列 $A$ を置換 $\pi(i)=A_i$ と同一視することがある。
  • 相異なる実数から成る列 $X$ の各項を,その列における小さい方からの順位で置き換えた順列を $\operatorname{st}(X)$ と書く(標準化)。
  • 順列 $A$ から値 $v$ の札を取り除き,残りの順序を保った長さ $n-1$ の列を $A\setminus v$ と書く。
単調写像との可換性

$\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.2 番兵:第1位置は最初と最後の $(\mathrm{T}_1)$ でしか動かない

第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) の計数の双方を支配している。

1.3 走査の累積表示と整列可能性の大域的特徴付け

番兵補題は先頭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$ のみ)。ここから次が直ちに従う。

  • $n\leqq 3$ ではすべての順列が整列可能であり,$c_2=2$,$c_3=6$。
  • $k=2$ の条件 $d_2(A)\leqq 1$ は (1) の主張にほかならない。(1) は大域的条件 (P) の最も小さい断面である。
  • $n=4$ で実質的な条件は $d_2\leqq 1$ のみであり,整列不能な順列は先頭2項が $\lbrace 3,4\rbrace$ の4個である。ゆえに $c_4=24-4=20$。

1.4 作問意図と設計原理

  • 操作の正体:$(\mathrm{T}_i)$ は隣接比較交換であり,往路と復路の一往復は双方向バブルソート(シェーカーソート,cocktail shaker sort)の1ラウンドにほかならない。往路で最大値 $n$ が右端へ,復路で最小値 $1$ が左端へ運ばれるが,$n\geqq 4$ では一往復で整列しない順列が存在する。例えば $A=(3,4,1,2)$ では $F(A)=(1,3,2,4)$ である。本問は一往復で整列する順列の個数を問うている。
  • (1) の役割:第1位置に触れる操作は最初と最後の $(\mathrm{T}_1)$ だけであり,全操作はこの2回に挟まれている。(1) はこの番兵構造を引き出す誘導であり,同時に (2) の場合分けの軸を与える。
  • $\min\lbrace A_1,A_2\rbrace$ という形:最初の $(\mathrm{T}_1)$ は第1・第2位置の情報を一つに統合するため,制約は「どちらか一方」という形でしか現れない。$A_1$ 単独には制約がない(例:$(4,1,2,3)$ は往路だけで整列する)。
  • (2) の設計:一般項ではなく隣接3項間漸化式を問うことは,札を1枚除いて規模を1下げる全単射が想定されていることを示唆する。係数 $4$ は「除く札の値が $1$ か $2$」と「その位置が第1か第2」の $2\times 2$ 通りに,補正 $-2c_{n-2}$ は札 $2$ を除いたときに残る制約(あるいは包除の重複)に対応する。
  • $n\geqq 4$ の意味:$c_{n-2}$ が問題の定義域 $n-2\geqq 2$ に入るための条件であり,本解では削除を2回続ける箇所でこの条件を用いる。$c_0=c_1=1$ と約束すれば漸化式は $n\geqq 2$ で成り立つ( 3.5 節 )。
  • 背後の大域構造:整列可能性は全閾値の条件 (P) で特徴付けられ( 定理5 ),置換のサイクル構造に読み替えると,分割できない成分が長さ $\ell$ ごとに $3^{\ell-2}$ 個あるという構造が現れる。漸化式の特性根 $2\pm\sqrt2$ はここに由来する。本問はこの構造の最も局所的な断面だけを切り出し,場合分け・全単射・漸化式という高校数学の道具で完結するように設計されていると読める。

1.5 構造から導かれる解法の分岐

着目する構造数学的翻訳対応する解法
第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 節

2. 本解

2.1 方針

  1. は番兵構造( 補題3 )から直ちに従う。(2) では番兵 $r=\min\lbrace A_1,A_2\rbrace$ が $1$ か $2$ かで排反に分け,札 $r$ を取り除いて標準化し,$\mathcal{C}_{n-1}$ との全単射を作る。$r=2$ の場合には取り除いた後の列の先頭が $1$ でないという制約が残り,その補正が $c_{n-2}$ で数えられる。

2.2 解答

(1)

$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$ 以下である。

(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). $$

2.3 検証

  • 小さい $n$:$c_2=2$,$c_3=6$ より $c_4=4\cdot 6-2\cdot 2=20$,$c_5=4\cdot 20-2\cdot 6=68$。$c_4=20$ は 1.3 節の直接計数 $24-4$ と一致する。$c_5$ は 定理5 から独立に検算できる。$n=5$ で実質的な条件は $d_2\leqq 1$,$d_3\leqq 1$ であり,$d_2\geqq 2$(先頭2項がともに $3$ 以上)は $3\cdot 2\cdot 3!=36$ 個,$d_3\geqq 2$($4,5$ がともに先頭3項にある)は $3\cdot 2\cdot 3!=36$ 個,両方を満たすものは先頭2項が $\lbrace 4,5\rbrace$ の $12$ 個と,$\lbrace 3,4\rbrace$ または $\lbrace 3,5\rbrace$ で第3項が残りの大きい値である $4+4$ 個の計 $20$ 個。よって $c_5=120-(36+36-20)=68$。
  • 内訳:$n=4$ では $N_1=2c_3=12$(札 $1$ が先頭2位置にある $12$ 個はすべて整列可能),$N_2=2(c_3-c_2)=8$(札 $2$ が先頭2位置にあり札 $1$ がない $2\cdot 2\cdot 2=8$ 個)。整列不能な4個は札 $1,2$ がともに後半2位置にあるものであり,整合する。
  • 補正項の意味:$r=2$ で制約 $B_1\neq 1$ を落とすと,逆写像が先頭2項 $\lbrace 1,2\rbrace$ の順列を作り,それらは場合 $r=1$ ですでに数えられている。過大計数はちょうど $2c_{n-2}$ であり,補正項と一致する。
  • 全数検査:$n\leqq 9$ の全順列について操作を直接実行すると,$c_n$ は $2,6,20,68,232,792,2704,9232$ となり,漸化式と一致する。
  • 増加率:$c_9/c_8=9232/2704\approx 3.414$ は特性根 $2+\sqrt2$ に近い(5.6 節)。

3. 別解と参考解

3.1 (1) の別証:移動限界

着想・方針

往路では,ある札が左へ動くのは $(\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$ は右端まで一度に動く)。方向を取り違えると論証は成立しない。

3.2 (2) の他の導出:4集合の包除原理

着想・方針

  1. より $A\in\mathcal{C}_n$ では値 $1$ または $2$ の札が先頭2位置にある。値($1$ か $2$)と位置(第1か第2)の4通りの事象を考え,重複を包除原理で除く。本解の排反な分類に代えて対称な4集合を用いる。

解答

$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$ である。

3.3 定理5の他の導出:累積最大値・最小値

着想・方針

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$ である。

  • $U_i\leqq i$ のとき:$U_1,\ldots,U_i$ は $i$ 以下の相異なる $i$ 個の値,すなわち $1,\ldots,i$ の並べ替えであるから $\mu_{i+1}=i+1$,$V_{i+1}=\max\lbrace U_i,i+1\rbrace=i+1$。
  • $U_i=i+1$ のとき:$U_1,\ldots,U_{i-1}$ は $\lbrace 1,\ldots,i\rbrace$ の $i-1$ 個であり,残る1個の値 $t\ (\leqq i)$ は $U_{i+1},\ldots,U_n$ に現れる。よって $\mu_{i+1}\leqq i$,$V_{i+1}=i+1$。
    ゆえに $V=(1,\ldots,n)$。段階2:$U_i\leqq i+1\ (\forall i)\iff\text{(P)}$ ある $i$ で $U_i > i+1$ ならば $M_i > i+1$ かつ $A_{i+1} > i+1$ であり(このとき $i+1\leqq n-1$),$d_{i+1}(A)\geqq 2$。逆に,ある $k$ で $d_k(A)\geqq 2$ とし,先頭 $k$ 個の中で $k$ を超える値のうち左から2番目のものの位置を $q$ とすると,$2\leqq q\leqq k$,$M_{q-1} > k$,$A_q > k$ であるから
    $$ U_{q-1}=\min\lbrace M_{q-1},A_q\rbrace > k\geqq q=(q-1)+1. $$
    以上より $A\in\mathcal{C}_n\iff\text{(P)}$。

検証・検算

  • $A=(3,4,1,2)$ では $U=(3,1,2,4)$,$U_1=3 > 2$ で整列不能であり,実際 $F(A)=(1,3,2,4)$。
  • 段階2は「すべての $i$」についての同値であり,各 $i$ ごとに $U_i\leqq i+1\iff d_{i+1}(A)\leqq 1$ が成り立つわけではない。例えば $A=(4,5,1,2,3)$ では $U=(4,1,2,3,5)$,$U_2=1\leqq 3$ であるが $d_3(A)=2$ である(違反は $U_1=4 > 2$ が検出する)。2番目に現れる大きい値の位置 $q$ に注目する議論は,この点を正しく処理している。

3.4 別解1:静的特徴付け・閾値シフト・1と2の交換

着想・方針

定理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 $$
に分ける。

  • $\lvert X\rvert=2c_{n-1}$:札 $1$ の位置 $p\in\lbrace 1,2\rbrace$ を固定すると, 補題6 ($v=1$)より $A\mapsto\operatorname{st}(A\setminus 1)$ は $\mathcal{C}_{n-1}$ への全単射である。
  • 値の交換:値 $1,2$ を入れ替える写像を $\tau$ とする。$k\geqq 2$ では $1,2\leqq k$ であるから $d_k(\tau A)=d_k(A)$ であり,$d_1\leqq 1$ は常に成り立つから, 定理5 より $\tau$ は $\mathcal{C}_n$ を保つ。(1) より $Y$ の元では札 $2$ が先頭2位置にあるから,$\tau$ は $Y$ を
    $$ Z=\lbrace A\in\mathcal{C}_n\mid 1\in\lbrace A_1,A_2\rbrace,\ 2\notin\lbrace A_1,A_2\rbrace\rbrace $$
    へ全単射に写す。
  • $\lvert Z\rvert$ の計算:$Z=X\setminus\lbrace A\in\mathcal{C}_n\mid\lbrace A_1,A_2\rbrace=\lbrace 1,2\rbrace\rbrace$ である。先頭が $(1,2)$ または $(2,1)$ の順列 $A$ について, 補題6 を2回($v=1$ を除き,標準化後の先頭の $1$ をさらに除く)用いると,$A\in\mathcal{C}_n\iff\operatorname{st}(A_3,\ldots,A_n)\in\mathcal{C}_{n-2}$ である(2回目の適用に $n-1\geqq 3$ を用いた)。よって各並びについて $c_{n-2}$ 個であり,$\lvert Z\rvert=2c_{n-1}-2c_{n-2}$。
    以上より
    $$ c_n=\lvert X\rvert+\lvert Y\rvert=2c_{n-1}+2(c_{n-1}-c_{n-2})=4c_{n-1}-2c_{n-2}. $$

検証・検算

  • $n=4$ では $Y$ は札 $2$ が先頭2位置にあり札 $1$ がない順列で $2\cdot 2\cdot 2=8$ 個,その像 $Z$ も8個である。
  • $\tau$ が $\mathcal{C}_n$ を保つことは,操作の追跡からは自明でない。例えば $(1,3,2,4)$ は往路の1回の交換で,$(2,3,1,4)=\tau(1,3,2,4)$ は往路と復路の計2回の交換で整列し,交換の起こり方は異なるが,ともに整列可能である。
  • 補題6 は $v\neq\min\lbrace A_1,A_2\rbrace$ の場合(先頭 $(2,1)$ から $2$ を除く場合)も含んでおり,3.2 節の (R) を一行で与える。

3.5 参考解1:サイクル分解・直和分解・母関数

着想・方針

$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$ とサイクルを閉じる。

解答

段階1

  定理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$。

検証・検算

  • $\ell=3,4$ の既約成分:三値符号 $0,\mathrm{L},\mathrm{R}$ から $(3,2,1)$,$(3,1,2)$,$(2,3,1)$ を得る。$\ell=4$ の9個は $2341$,$2413$,$2431$,$3142$,$3241$,$4123$,$4132$,$4213$,$4231$ である(一行表示)。
  • $c_4$ の組成展開:組成 $4$;$3+1$,$1+3$;$2+2$;$2+1+1$,$1+2+1$,$1+1+2$;$1+1+1+1$ の重みは順に $9,3,3,1,1,1,1,1$ で,和は $20$。
  • 符号化の例:$\ell=5$,符号 $(\mathrm{R},0,\mathrm{L})$(値 $2,3,4$ に対応)では $w=(1)\to(1,2)\to(1,2)\to(4,1,2)$,サイクル $5\to 4\to 1\to 2\to 5$,固定点 $3$ より $\beta=(2,5,3,1,4)$。$d_1=d_2=d_3=d_4=1$ であり,直接の操作でも $F(\beta)=(1,2,3,4,5)$。
  • 付加の順序:内部の値は小さい順に付加しなければならない。弧条件は値の小さい側から作る集合 $\lbrace s_1,\ldots,s_j\rbrace$ に関するものだからである。例えば $\lbrace 1,4\rbrace$ から出発して $3,2$ を大きい順に付加する構成は $(4,3,1,2)$ のような $d_2=2$ の置換を生み,誤りである。
  • 差分の取り方:(B) の重み $3^{\ell-2}$ は定数でないため,単純に $c_n-c_{n-1}$ を作っても閉じない。$3$ 倍してずらす段階4の処理が必要であり,これを誤ると例えば $c_n=2c_{n-1}+2c_{n-2}$($c_4=16$)のような誤った式に至る。
  • 分母の読み方:$1-4x+2x^2=(1-x)(1-3x)-x^2$ は,固定点の成分($1-x$)と既約成分の幾何級数($1-3x$)から長さ2の成分 $x^2$ を除いた形をしており,係数 $4$ と $-2$ の組合せ的由来を示す。

3.6 同じ系列に属する変形

以下は,上記のいずれかと発想の核を共有するか,表現の置き換えにとどまるため,独立の解法として扱わない。

本解の系列(番兵と削除)

  • 逆向きの考察:最終状態から操作を逆にたどり,最後の $(\mathrm{T}_1)$ の直前の先頭2項が $\lbrace 1,2\rbrace$ であることから出発する議論。本解 (1) と同一である。
  • 全単射の圧縮表示:$\mathcal{C}_n\cong(\lbrace 1,2\rbrace\times\mathcal{C}_{n-1})\sqcup(\lbrace 1,2\rbrace\times\mathcal{C}_{n-1}^{+})$,$\lvert\mathcal{C}_{n-1}^{+}\rvert=c_{n-1}-c_{n-2}$。
  • 重複のない別分類:先頭2項が $\lbrace 1,2\rbrace$ のもの $2c_{n-2}$ 個と,$1,2$ の一方だけを先頭2項に含むもの $4(c_{n-1}-c_{n-2})$ 個に分ける。3.2 節の包除を排反和に書き直したものである。
  • 移動限界(3.1 節):番兵構造を移動距離で言い換えたもの。

別解1 の系列(静的条件)

  • 0-1 化と累積最大値・最小値: 定理5 の証明と 3.3 節は,同じ条件 (P) の二つの導出である。
  • 置換行列による図示:点 $(i,A_i)$ を描くと,(P) は「正方形 $\lbrack 1,k\rbrack\times\lbrack 1,k\rbrack$ に点が $k-1$ 個以上ある」ことと同値である。(P) の視覚的言い換えであり,新たな計数原理は生まない。
  • パターン回避( 定理9 ):(P) と同値な禁止配置による表示。

参考解1 の系列(成分構造)

  • 差分と母関数:段階4と段階4'は同じ畳み込み (B) の処理である。
  • 重み付き整数組成・形式言語:整列可能な順列を「固定点」と三値語 $\lbrace 0,\mathrm{L},\mathrm{R}\rbrace^{\ell-2}$ の有限列として符号化する表示。(B) の言い換えである。
  • 有限状態の見方:境界の状態 $d_k\in\lbrace 0,1\rbrace$ を左から順に追跡する見方。直和分解の動的な読み方である。
  • $a_\ell=3^{\ell-2}$ の別導出:既約成分に最大値を挿入する生成規則による方法(5.7 節の文献)。数える対象は同じである。

独立の解法として採用しなかった方向

  • 転倒数:交換1回で転倒数は1減るが,交換が起こる位置の情報を持たない。例えば $(3,4,1,2)$ と $(4,1,3,2)$ はともに転倒数 $4$ であるが,前者は整列不能,後者は整列可能である。
  • 最大値 $n$ の位置による場合分け: 定理10 の逆補対称により本解の鏡像として実行できるが,操作の追跡としては見通しが悪く,新しい構造を与えない。
  • 確率・期待値:一様な順列で $\mathbb{E}[d_k]=k(n-k)/n$ は計算できるが,全境界での同時条件を扱えない。
  • 微積分・座標・ベクトル・複素数・三角関数:本問には連続量や計量構造がなく,導入の必然性がない。

3.7 解法の比較

解法主に利用する構造対象範囲長所注意点
本解番兵(第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}$ から生じることを明らかにする。

4. 汎用的な探索手順

本問から抽出される手順を,操作で定義された対象を数える問題一般に適用できる形で述べる。

4.1 意思決定の流れ

  1. 操作を代数化する:比較交換は $(x,y)\mapsto(\min\lbrace x,y\rbrace,\max\lbrace x,y\rbrace)$ である。比較だけで決まる操作は値の大小関係にのみ依存し,標準化や 0-1 化と可換である( 補題2 )。
  2. 各位置に触れる操作を数える:触れる操作が少ない位置,特に同じ位置に作用する最初と最後の操作の間で凍結される位置(番兵)を探す。
  3. 最終状態から逆算する:番兵に入りうる値を,最終状態の要請から絞り込む。最小・最大などの極端な値が候補になる。
  4. 番兵を除いて規模を下げる:除去後の列が同型の小問題になるかを,標準化写像を明示して確かめ,逆写像(挿入)で全単射を完成させる。
  5. 残る制約と重複を処理する:排反な分類(本問では $\min\lbrace A_1,A_2\rbrace$)を選ぶか,対称な分類と包除原理を用いる。除去後に残る制約($B_1\neq 1$)を落とさない。
  6. 局所条件を大域化する:見つけた局所条件が,閾値を動かした条件族の一断面でないかを疑う。0-1 化により全閾値の条件が得られれば,動的な操作が静的な条件に置き換わる。
  7. 静的条件を構造化する:境界を横切る量の有界性から直和分解へ,既約成分の分類へ,そして母関数へと進む。
  8. 検算する:小さい $n$ の全列挙,補集合の包除,計算機による全数検査,特性根と増加率,異なる解法の一致を確かめる。

4.2 症状と有効な道具

症状検討する道具本問での例
比較交換だけから成る操作標準化不変性,0-1 化補題2,定理5
ある位置に触れる操作が少ない番兵(凍結される位置)補題3
一方向の走査で移動に偏りがある移動限界3.1 節
走査の結果を式で書きたい累積最大値・最小値補題4
特定の札の除去で規模が1下がる全単射と漸化式本解
場合分けが重複する包除原理3.2 節
条件がいくつかの値を区別しない値の交換による全単射別解1
全閾値で境界を横切る量が有界直和分解,サイクル構造,母関数参考解1

5. 発展事項

5.1 高校数学と一般理論の境界

事項高校数学での扱い一般理論
比較交換$\min$,$\max$ と場合分け比較交換ネットワーク,0-1 原理
整列可能性(1) の局所条件,番兵閾値条件 (P),パターン回避
計数全単射,場合分け,包除原理置換のサイクル分解,直和分解,母関数
漸化式の解隣接3項間漸化式と特性方程式有理母関数,漸近評価
対称性扱わない逆置換・逆補置換,往路と復路の順序交換
統計量扱わない固定点の分布と Pell 数

本解,3.1 節,3.2 節は左欄で完結する。 定理5 と別解1は抽象度が高いが証明は初等的である。参考解1と以下の各節は右欄に属する。

5.2 比較交換ネットワークと 0-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$ の個数の条件に落ちる。

5.3 パターン回避による特徴付け

パターン回避による特徴付け

$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$ の位置)にあたる。

5.4 対称性

対称性

$\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$ 以上」を得る。

5.5 往復1回と一方向2回

比較交換の回数はともに $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 節)のに対し,一往復は移動距離ではなく「境界を横切る札の数」を制限する。この制約の型の違いが増加率の差に現れている。

5.6 一般項・漸近・固定点の分布

高校数学の範囲

 特性方程式 $\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)$ に戻る。

5.7 文献と背景

  • 双方向バブルソート(cocktail shaker sort)は,Knuth『The Art of Computer Programming』第3巻でバブルソートの改良の一つとして扱われている。
  • 一往復で整列する順列の全体が $\mathrm{Av}(3412,3421,4312,4321)$ であること,その既約成分(文献では connected permutation)の個数が $3^{n-2}$ であること,母関数 $\frac{1-3x}{1-4x+2x^2}$,固定点をもたない元が Pell 数で数えられることは,M. Barnabei, F. Bonetti, M. Silimbani, Two permutation classes related to the Bubble Sort operator, Electron. J. Combin. 19(3) (2012), #P25 で示されている。そこでは,バブルソート演算子の逆像に関する既知の結果からパターン基底を導き,既約成分を最大値の挿入で生成している。本記事の 定理5 , 補題8 は,それぞれ閾値条件とサイクルの弧条件による独立な導出である。
  • 数列 $1,1,2,6,20,68,232,\ldots$ は OEIS A006012 である。Gao と Kitaev(Electron. J. Combin. 26(3) (2019), #P3.26, Theorem 12)は,第1項と第4項が第2・第3項より大きい配置(パターン $3124,3214,4123,4213$)を避ける順列も同じ数列で数えられることを,「$1$ または $2$ が両端にある」という条件の4事象の包除 $4a(n-1)-2a(n-2)$ によって示している。これは 3.2 節と同型の議論であるが,対象のクラスは異なる。反転(逆順)・補・逆置換とその合成は基底を基底に写し,単調パターンの集合 $\lbrace 1234,4321\rbrace$ を保つ。本問のクラスの基底は $4321$ を含み,Gao–Kitaev のクラスの基底は単調パターンを含まないから,両者はこれらの自明な対称性では移り合わない。

6. 最終整理

6.1 構造マップ

  • 一往復の比較交換 $F$($(\mathrm{T}_i)$ は $(x,y)\mapsto(\min,\max)$,値の大小関係のみに依存)
    • 局所構造:第1位置に触れるのは最初と最後の $(\mathrm{T}_1)$ のみ
      • 番兵 $r=\min\lbrace A_1,A_2\rbrace\in\lbrace 1,2\rbrace$ → (1)(本解,別証:移動限界)
      • 番兵の削除と標準化 → $r=1$:$2c_{n-1}$,$r=2$:$2(c_{n-1}-c_{n-2})$ → 本解
      • 値と位置の4事象 → 包除 $4c_{n-1}-2c_{n-2}$ → 3.2 節
    • 大域構造:0-1 化または累積最大値・最小値 → 条件 (P):$d_k\leqq 1$
      • $k=2$ → (1);閾値シフトと値 $1,2$ の交換 → 別解1
      • 境界を横切る矢印 → 直和分解 → 単一サイクルと三値符号 $3^{\ell-2}$ → 母関数 $\frac{1-3x}{1-4x+2x^2}$ → 参考解1
      • パターン基底 $\lbrace 3412,3421,4312,4321\rbrace$,逆置換・逆補置換対称,固定点の分布 → 5 節
    • 結論:$c_n=4c_{n-1}-2c_{n-2}$,$c_n=\frac12\bigl\lbrace(2+\sqrt2)^{n-1}+(2-\sqrt2)^{n-1}\bigr\rbrace$

6.2 解答一覧

設問結論根拠
(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$

6.3 数学的教訓

  • 操作を追う前に,各位置に触れる操作を数える。最初と最後に同じ位置へ作用する操作は,その間の不変な対象(番兵)を生む。
  • 比較だけで決まる操作は値の大小関係にのみ依存する。標準化により,札を除いた列は同型の小問題になる。
  • 規模を下げる全単射では,除去後に残る制約(本問の $B_1\neq 1$)と,逆写像が分類の外へはみ出さないこと($r=2$ が保たれること)を必ず確かめる。補正項は過大計数の正確な大きさである。
  • 排反な分類($\min$ による)と対称な分類(包除)は同じ構造の二つの表現であり,係数の意味を相互に照らし合う。
  • 局所条件は大域条件の一断面であることが多い。閾値による 0-1 化は,動的な操作を静的な条件に置き換える標準的な手段である。
  • 「境界を横切る量が有界」という条件は,直和分解と既約成分の分類を導き,有理母関数と線形漸化式の起源を説明する。
  • 各 $i$ ごとの同値と「すべての $i$」についての同値を区別する。局所的に偽の主張が,全体としては正しい同値の一部をなすことがある。
  • 検算は,小さい $n$ の全列挙,補集合の包除,計算機による全数検査,特性根と増加率,異なる解法の一致によって多重に行う。
投稿日:1日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

医学部・難関大受験生の指導を行っています。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中