Robinson–Schensted–Knuth対応
概要
Robinson–Schensted–Knuth対応（Robinson–Schensted–Knuth correspondence）とは、非負整数を成分とする行列の成分から作った数の列を行挿入で盤に入れ、挿入盤 $P$ と記録盤 $Q$ を作ることで、行列と、同じ形の半標準盤の組とを一対一に対応させる構成であり、$P$ の内容は列の和、$Q$ の内容は行の和に等しい。置換行列に限ると $n$ 次の置換と同じ形の標準盤の組の全単射になって $\sum_\lambda(f^\lambda)^2=n!$ が従い、一般の行列では Schur 多項式の Cauchy の恒等式が数え上げで示される。また、置換の最長の増加部分列の長さは盤の第 1 行の長さに、最長の減少部分列の長さは行の個数に等しい（Schensted の定理。Greene の定理の特別な場合）。
Robinson–Schensted–Knuth対応（RSK 対応）は、非負整数を成分とする行列と、同じ形の半標準盤の組とを一対一に対応させる組合せ的な構成である。行列の成分を並べた数の列を、盤の「行挿入」で一つずつ盤に入れていき、入れた数でできる盤 $P$ と、各段階で増えた箱の位置を記録した盤 $Q$ の組を作る。置換行列に限ると、$n$ 次の置換 $\sigma$ と、同じ形 $\lambda\vdash n$ の標準盤の組 $(P,Q)$ との全単射になり（Robinson–Schensted 対応）、そこから
$$
\sum_{\lambda\vdash n}(f^\lambda)^2=n!
$$
が表現論を使わずに従う。一般の行列では、Schur 多項式についての Cauchy の恒等式の数え上げによる証明になる。
盤の形は置換の性質を反映する。$\sigma$ の最長の増加部分列の長さは第 1 行の長さ $\lambda_1$ に、最長の減少部分列の長さは行の個数に等しい（Schensted の定理）。さらに、交わらない $k$ 個の増加部分列の和集合の大きさの最大値は $\lambda_1+\cdots+\lambda_k$ に等しい（Greene の定理）。
この記事では、行挿入とその逆の操作を定義して基本的な性質を示し、RSK 対応が全単射であること、Robinson–Schensted 対応と $\sum(f^\lambda)^2=n!$、Cauchy の恒等式、Greene の定理（したがって Schensted の定理）を証明する。
定義
分割 $\lambda$、Young 図形、箱 $(i,j)$（第 $i$ 行・第 $j$ 列）、共役分割 $\lambda'$、角（右にも下にも箱がない箱）、標準盤と個数 $f^\lambda$ は Young図形 の記事のとおりとする。Young 図形の角を取り除くとまた Young 図形が残り、Young 図形 $\lambda$ に箱を一つ加えて Young 図形 $\mu$ ができるとき、加えた箱は $\mu$ の角である。
形 $\lambda$ の半標準盤とは、$\lambda$ の各箱に正の整数を一つずつ書き込んだもの $T$ で、各行で左から右へ広義増加、各列で上から下へ狭義増加するものをいう（Schur多項式 の定義「半標準盤と盤の重み」は書き込む数を $\{1,\dots,n\}$ に限った場合である）。$T(i,j)$ で箱 $(i,j)$ の数を表し、$T$ の形を $\operatorname{sh}(T)$ と書く。数 $k$ が書かれた箱の個数を並べた列を $T$ の内容という。空の図形の上の盤を $\emptyset$ と書く。$1,\dots,n$ を一度ずつ書き込んだ半標準盤が標準盤である。
半標準盤 $T$ と正の整数 $x$ に対し、盤 $T\leftarrow x$ を次の手順で定める。$x_1:=x$ とし、$r=1,2,\dots$ の順に次を行う。
- 第 $r$ 行に $x_r$ より真に大きい数がなければ、$x_r$ を第 $r$ 行の右端の次の箱に置いて終える（第 $r$ 行が空なら、第 $r$ 行の最初の箱になる）。
- そうでなければ、第 $r$ 行で $x_r$ より真に大きい数のうちいちばん左のものを $x_{r+1}$ とし、それがあった箱に $x_r$ を置き、$x_{r+1}$ を第 $r+1$ 行へ送る。
これを $T$ への $x$ の行挿入（row insertion）という。$x_r$ を置いた箱を $(r,c_r)$ と書き、箱の列 $(1,c_1),\dots,(s,c_s)$ を押し出しの経路、最後の箱 $B=(s,c_s)$ を新しい箱という。
押し出す数を「$x_r$ 以上の数」ではなく「$x_r$ より真に大きい数」から選ぶことが、列の狭義増加を保つために要る（rem-rsk-counterexamples の 1 行目）。
$T$ を形 $\lambda$ の半標準盤、$x$ を正の整数とする。
- 押し出しの経路は $c_1\ge c_2\ge\cdots\ge c_s$ を満たし、$x_1< x_2<\cdots< x_s$ である。
- $T\leftarrow x$ は半標準盤で、その形は $\lambda$ に新しい箱 $B$ を加えた Young 図形であり、$B$ はその角である。
要点：第 $r$ 行で $x_r$ を置く位置は、第 $r-1$ 行で $x_r$ があった位置より右にならない。
詳しい証明を開く
$x_{r+1}$ は第 $r$ 行で $x_r$ より真に大きいので $x_r< x_{r+1}$ である。第 $r$ 行に $x_r$ を置くと、その左の数は $x_r$ 以下（いちばん左の「$x_r$ より大きい数」を選んだから）、右の数は $x_{r+1}$ 以上で $x_r$ より大きいので、行の広義増加は保たれる。
$r\ge2$ とする。$x_r$ は第 $r-1$ 行の箱 $(r-1,c_{r-1})$ にあった数である。$\lambda_r\ge c_{r-1}$ なら、列の狭義増加から $T(r,c_{r-1})>T(r-1,c_{r-1})=x_r$ なので、第 $r$ 行で $x_r$ より大きいいちばん左の数は第 $c_{r-1}$ 列かその左にあり、$c_r\le c_{r-1}$ である。$\lambda_r< c_{r-1}$ なら、$x_r$ を右端の次に置くとしても $c_r\le\lambda_r+1\le c_{r-1}$ である。これで 1 が示された。
列の条件を見る。挿入の後、$x_r$ の上の箱 $(r-1,c_r)$ の数は、$c_r=c_{r-1}$ なら $x_{r-1}< x_r$、$c_r< c_{r-1}$ なら変わらない $T(r-1,c_r)$ で、これは $x_{r-1}$ を置いた位置より左の数なので $x_{r-1}$ 以下であり、$x_r$ より小さい。$x_r$ の下の箱 $(r+1,c_r)$ は、$x_r$ が $x_{r+1}$ と取り替わった場合は $T(r+1,c_r)>T(r,c_r)=x_{r+1}>x_r$ であり（第 $r+1$ 行の挿入でこの箱が変わるなら、そこに置かれるのは $x_{r+1}>x_r$ である）、$x_r$ を右端の次に置いた場合は $c_r=\lambda_r+1>\lambda_{r+1}$ なので箱がない。よって $T\leftarrow x$ は半標準盤である。最後の行 $s$ では $c_s=\lambda_s+1$ であり、$s\ge2$ なら $c_s\le c_{s-1}\le\lambda_{s-1}$ なので、加えた後の形も分割で、$B$ の右と下に箱はない。$\square$
$U$ を半標準盤、$B=(s,c)$ を $\operatorname{sh}(U)$ の角とする。$y_s:=U(s,c)$ とし、箱 $B$ を取り除く。$r=s-1,s-2,\dots,1$ の順に、第 $r$ 行で $y_{r+1}$ より真に小さい数のうちいちばん右のものを $y_r$ とし、その箱に $y_{r+1}$ を置く。最後に第 1 行から取り出された $y_1$ を $x$ とし、残った盤を $T$ とする。このとき次が成り立つ。
- $T$ は半標準盤で、$T\leftarrow x=U$ であり、その新しい箱は $B$ である。
- 逆に、半標準盤 $T$ と正の整数 $x$ について、$U:=T\leftarrow x$ と新しい箱 $B$ に上の手順を当てると、$(T,x)$ に戻る。
したがって $(T,x)\mapsto(T\leftarrow x,B)$ は、半標準盤と正の整数の組の全体から、半標準盤とその形の角の組の全体への全単射である。
要点：各行で、行挿入は「より大きいもののうち最も左」を、逆の手順は「より小さいもののうち最も右」を選ぶので、互いに相手の選んだ箱を選ぶ。
詳しい証明を開く
$y_r$ は存在する：$U(r,c_{r+1})< U(r+1,c_{r+1})=y_{r+1}$ である（$y_{r+1}$ を取り出した箱を $(r+1,c_{r+1})$ とする）。その位置を $c_r$ とすると $c_r\ge c_{r+1}$ である。第 $r$ 行で $y_r$ を $y_{r+1}$ に置き換えると、左の数は $y_r$ 以下、右の数は $y_{r+1}$ 以上（いちばん右を選んだから）なので行は広義増加のままである。$T$ の箱 $(r,c_r)$ の数 $y_{r+1}$ の下の箱 $(r+1,c_r)$ は、$c_r=c_{r+1}$ なら数 $y_{r+2}>y_{r+1}$ をもつか（$r+1=s$ なら箱がない）、$c_r>c_{r+1}$ なら変わらない $U(r+1,c_r)$ で、これは $y_{r+1}$ を取り出した位置より右の数なので $y_{r+2}$ 以上、したがって $y_{r+1}$ より大きい（$r+1=s$ なら $c_r>c=\lambda_s$ で箱がない）。上の箱 $(r-1,c_r)$ は、$c_{r-1}=c_r$ なら $y_r< y_{r+1}$ をもち、$c_{r-1}>c_r$ なら変わらない $U(r-1,c_r)< U(r,c_r)=y_r< y_{r+1}$ である。よって $T$ は半標準盤である。
$T$ に $x=y_1$ を行挿入する。第 $r$ 行（$r< s$）の $T$ では、位置 $c_r$ に $y_{r+1}>y_r$ があり、その左の数は $y_r$ 以下なので、$y_r$ はちょうど $y_{r+1}$ を押し出し、もとの $U$ の第 $r$ 行に戻る。第 $s$ 行の $T$ は $U$ の第 $s$ 行から右端の $y_s$ を除いたもので、数はすべて $y_s$ 以下なので、$y_s$ は右端の次、すなわち $B$ に置かれる。これが 1 である。
2：$U=T\leftarrow x$ の経路を $(r,c_r)$、押し出された数を $x_r$ とする。$U$ の第 $r$ 行（$r< s$）では位置 $c_r$ に $x_r< x_{r+1}$ があり、その右の数は $T$ で $x_{r+1}$ の右にあった数なので $x_{r+1}$ 以上である。よって $x_{r+1}$ より小さいいちばん右の数は位置 $c_r$ の $x_r$ であり、逆の手順は経路を下から逆にたどって $T$ と $x$ を復元する。$\square$
$T$ を半標準盤、$x,x'$ を正の整数とし、$T\leftarrow x$ の新しい箱を $B$、$(T\leftarrow x)\leftarrow x'$ の新しい箱を $B'$ とする。
- $x\le x'$ なら、$B'$ は $B$ より真に右の列にあり、$B$ と同じ行かそれより上の行にある。
- $x>x'$ なら、$B'$ は $B$ と同じ列かそれより左の列にあり、$B$ より真に下の行にある。
要点：$x\le x'$ なら 2 回目の経路は各行で 1 回目の経路の真に右を通り、$x>x'$ なら同じ列か左を通って 1 回目より長く続く。
詳しい証明を開く
1 回目の経路を $(r,c_r)$（$r\le s$）、行 $r$ へ送られる数を $x_r$、2 回目を $(r,c'_r)$（$r\le s'$）、$x'_r$ とする。
1．$x_r\le x'_r$ で第 $r$ 行に 1 回目の数 $x_r$ が位置 $c_r$ にあるとする（$r=1$ では $x_1=x\le x'=x'_1$）。$T\leftarrow x$ の第 $r$ 行で位置 $c_r$ 以下の数は $x_r$ 以下、したがって $x'_r$ 以下なので、$x'_r$ を置く位置は $c'_r>c_r$ である。$r< s$ のとき、$x'_r$ が右端の次に置かれれば 2 回目はここで終わる。そうでなければ $x'_{r+1}$ は位置 $c'_r>c_r$ にある数で、そこは 1 回目の挿入で変わっていないから、行の広義増加により $x'_{r+1}\ge x_{r+1}$ である。$r=s$ のとき、$x_s$ は第 $s$ 行の右端にあり、$x'_s\ge x_s$ より大きい数は第 $s$ 行にないので、2 回目も第 $s$ 行の右端の次で終わる。帰納的に、2 回目の経路は $s$ 行目までに終わり、各行で 1 回目の真に右を通る。$B'=(s',c'_{s'})$ について $s'\le s$、$c'_{s'}>c_{s'}\ge c_s$ である。
2．$x'_r< x_r$ で第 $r$ 行の位置 $c_r$ に $x_r$ があるとする（$r=1$ では $x'=x'_1< x_1=x$）。$x'_r$ より大きい数 $x_r$ が位置 $c_r$ にあるので $c'_r\le c_r$ で、$x'_r$ は必ず数を押し出す。押し出される数 $x'_{r+1}$ は、$c'_r=c_r$ なら $x_r$、$c'_r< c_r$ なら $T$ の第 $r$ 行で $x_r$ を置いた位置より左の数なので $x_r$ 以下である。いずれにしても $x'_{r+1}\le x_r< x_{r+1}$ である。$r< s$ なら第 $r+1$ 行で同じことを繰り返す。$r=s$ なら $x'_{s+1}$ が第 $s+1$ 行へ送られるので、2 回目の経路は第 $s+1$ 行以下まで続く。よって $s'>s$ であり、経路は列について広義減少なので（lem-rsk-insertion の 1）$c'_{s'}\le c'_s\le c_s$ である。$\square$
RSK 対応
$A=(a_{ij})$ を成分が非負整数の $m\times n$ 行列とし、$N:=\sum_{i,j}a_{ij}$ とする。上の段に $i$、下の段に $j$ を書いた列 $\binom{i}{j}$ を $a_{ij}$ 個ずつ用意し、上の段について広義増加、上の段が等しいところでは下の段について広義増加になるように並べた配列
$$
w_A=\begin{pmatrix}i_1&i_2&\cdots&i_N\\ j_1&j_2&\cdots&j_N\end{pmatrix}
$$
を $A$ の二行配列という。$(P_0,Q_0):=(\emptyset,\emptyset)$ とし、$t=1,\dots,N$ について $P_t:=P_{t-1}\leftarrow j_t$ とし、$Q_t$ は $Q_{t-1}$ に $P_t$ の新しい箱を加えてそこに $i_t$ を書いたものとする。$(P,Q):=(P_N,Q_N)$ を $A$ に対応させる写像 $A\mapsto(P,Q)$ を RSK 対応といい、$P$ を挿入盤、$Q$ を記録盤という。
$w_A$ は $A$ から一意に決まり、逆に、上の段が $\{1,\dots,m\}$、下の段が $\{1,\dots,n\}$ に値をもち上の規則で並んだ配列は、列 $\binom ij$ の個数を数えることで一つの行列を定める。$A$ の第 $i$ 行の和を $r_i$、第 $j$ 列の和を $c_j$ と書く。
RSK 対応 $A\mapsto(P,Q)$ は、成分が非負整数の $m\times n$ 行列の全体から、同じ形の半標準盤の組 $(P,Q)$ で、$P$ の数が $\{1,\dots,n\}$ に、$Q$ の数が $\{1,\dots,m\}$ に属するものの全体への全単射である。このとき、$P$ に数 $j$ はちょうど $c_j$ 回、$Q$ に数 $i$ はちょうど $r_i$ 回現れる。
この形の主張と構成は Knu70 の §2・§3 にあり、Theorem 2（p. 715）がこの全単射である。
$P$ が半標準盤であることは lem-rsk-insertion の 2 から、$P$ と $Q$ の形が等しいことと内容についての主張は構成から従う。
要点：同じ数 $i$ を書いた記録盤の箱は、行の押し出しの補題により左から右へ相異なる列に並ぶので、最大の数のいちばん右の箱から逆挿入をくり返すと行列が復元される。
記録盤と逆写像の証明を開く
$Q$ は半標準盤である。 $Q_t$ は $Q_{t-1}$ に角を一つ加えて $i_t$ を書いたもので、$i_t$ はそれまでに書いた数以上なので、$Q_t$ の各行・各列は広義増加である。列の狭義増加を示すには、同じ数 $i$ を書いた箱が同じ列にないことを示せばよい。$i_t=i_{t+1}$ なら $j_t\le j_{t+1}$ なので、lem-rsk-bumping の 1 により、時刻 $t+1$ の新しい箱は時刻 $t$ の新しい箱より真に右の列にある。よって数 $i$ の箱は、加えられた順に左から右へ、相異なる列に並ぶ。
逆写像。 同じ形の半標準盤の組 $(P,Q)$ が与えられたとする。$Q$ の最大の数 $i$ を書いた箱は相異なる列にあり（列の狭義増加）、そのうちいちばん右の箱 $B$ は角である。実際、$B$ の右の箱があればその数は $i$ 以上で $i$ に等しくなり、$B$ がいちばん右であることに反し、下の箱があればその数は $i$ より大きくなる。$P$ と $B$ に lem-rsk-reverse の逆挿入を当てて $(P',j)$ を得て、$Q$ から $B$ を除いた $Q'$ とともに $\binom ij$ を取り出す。これを繰り返して得た列を逆順に並べたものを $w$ とする。
$w$ が二行配列の並べ方の規則を満たすことを示す。上の段が広義増加であることは構成から明らかである。同じ $i$ が続いて取り出されるとき、先に右の箱 $B'$ から $j'$、次にその左の箱 $B$ から $j$ が取り出されたとする。lem-rsk-reverse により、取り出しの後に残った盤に $j$、続けて $j'$ を行挿入すると、新しい箱はそれぞれ $B$、$B'$ になる。$j>j'$ なら lem-rsk-bumping の 2 により $B'$ は $B$ と同じ列かその左にあることになり矛盾するので、$j\le j'$ である。
よって $w=w_A$ となる行列 $A$ がただ一つあり、lem-rsk-reverse の 1 により $A$ の RSK 対応は $(P,Q)$ である。逆に $A$ から作った $(P,Q)$ にこの手順を当てると、最後に加えた箱は最大の数 $i_N$ をもつ箱のうちいちばん右のものなので（上で示した並び方）、lem-rsk-reverse の 2 により $\binom{i_N}{j_N}$ が取り出され、帰納的に $w_A$ が復元される。$\square$
Robinson–Schensted 対応
$n$ 次の置換 $\sigma$ を、$\sigma(1),\dots,\sigma(n)$ の順に並べた語として扱う。置換行列（$a_{i\sigma(i)}=1$、ほかの成分は $0$）の二行配列は上の段が $1,2,\dots,n$、下の段が $\sigma(1),\dots,\sigma(n)$ であり、$P(\sigma)$ は $\emptyset$ に $\sigma(1),\dots,\sigma(n)$ を順に行挿入した盤、$Q(\sigma)$ は $k$ 回目の挿入で増えた箱に $k$ を書いた盤である。
$\sigma\mapsto(P(\sigma),Q(\sigma))$ は、$n$ 次の対称群 $S_n$ から、同じ形 $\lambda\vdash n$ の標準盤の組の全体への全単射である。特に
$$
\sum_{\lambda\vdash n}(f^\lambda)^2=n!
$$
が成り立つ。
Young図形 の記事は、$f^\lambda$ が $S_n$ の既約表現の次元であることと既約表現の次元の 2 乗の和が群の位数に等しいことから同じ等式を導いている。上の証明は表現論を使わない（Sta13 Theorem 8.13 とその直後の段落も、この全単射を Corollary 8.5 のこの等式の全単射による証明として述べている）。
Cauchy の恒等式
$x=(x_1,\dots,x_m)$、$y=(y_1,\dots,y_n)$ を変数とし、半標準盤 $T$ の内容が $(\mu_1,\mu_2,\dots)$ のとき $x^T:=x_1^{\mu_1}x_2^{\mu_2}\cdots$ と書く。分割 $\lambda$ について
$$
s_\lambda(x_1,\dots,x_m)=\sum_Tx^T
$$
（和は数が $\{1,\dots,m\}$ に属する形 $\lambda$ の半標準盤 $T$ にわたる）を用いる。これは Schur多項式 の定理「半標準盤による表示」により Schur 多項式に等しい（その記事では証明を文献に譲っている。双交代式との一致は、Lindström–Gessel–Viennotの補題 による格子路の数え上げでも示される）。$\lambda$ の長さが $m$ を超えるとき、列の狭義増加により右辺の和は空で $0$ になり、Schur 多項式の定義とも合う。
形式的冪級数環 $\mathbb{Z}[\![x_1,\dots,x_m,y_1,\dots,y_n]\!]$ において
$$
\prod_{i=1}^m\prod_{j=1}^n\frac{1}{1-x_iy_j}=\sum_\lambda s_\lambda(x_1,\dots,x_m)\,s_\lambda(y_1,\dots,y_n)
$$
が成り立つ。和はすべての分割 $\lambda$ にわたる。
左辺の各因子を $\sum_{a\ge0}(x_iy_j)^a$ と展開して掛けると、各 $(i,j)$ について指数 $a_{ij}\ge0$ を選ぶ項の和、すなわち
$$
\prod_{i,j}\frac{1}{1-x_iy_j}=\sum_A\prod_{i,j}(x_iy_j)^{a_{ij}}=\sum_Ax_1^{r_1}\cdots x_m^{r_m}\,y_1^{c_1}\cdots y_n^{c_n}
$$
になる（和は成分が非負整数の $m\times n$ 行列 $A$ にわたる。各単項式の係数は有限和である）。thm-rsk で $A\mapsto(P,Q)$ と置き換えると、$x_1^{r_1}\cdots x_m^{r_m}=x^Q$、$y_1^{c_1}\cdots y_n^{c_n}=y^P$ なので、右辺は $\sum_\lambda\sum_{P,Q}x^Qy^P=\sum_\lambda s_\lambda(x)s_\lambda(y)$ に等しい（内側の和は形 $\lambda$ の組にわたる）。$\square$
対称関数 の記事の定理「Cauchy の恒等式と直交性」は、$m=n$ の場合を Cauchy の行列式と双交代式の展開で証明している。上の証明はこの恒等式を数え上げの等式として示すもので、Knu70 §7（p. 726）は、RSK 対応がこの恒等式の構成的な証明になることを述べている。
例
以下、盤を行ごとに左から右へ読み、行の区切りをスラッシュで書く（$124/35/6$ は第 1 行が $1,2,4$、第 2 行が $3,5$、第 3 行が $6$ の盤）。
$\sigma=361524$（$\sigma(1)=3,\dots,\sigma(6)=4$）に行挿入を順に行うと、次のようになる。
| $k$ | 挿入する数 $\sigma(k)$ | $P_k$ | $Q_k$ |
|---|---|---|---|
| 1 | 3 | $3$ | $1$ |
| 2 | 6 | $36$ | $12$ |
| 3 | 1 | $16/3$ | $12/3$ |
| 4 | 5 | $15/36$ | $12/34$ |
| 5 | 2 | $12/35/6$ | $12/34/5$ |
| 6 | 4 | $124/35/6$ | $126/34/5$ |
5 回目の挿入では、$2$ が第 1 行の $5$ を押し出し、$5$ が第 2 行の $6$ を押し出し、$6$ が第 3 行の最初の箱に置かれる。押し出しの経路は $(1,2),(2,2),(3,1)$ で、列は広義減少である（lem-rsk-insertion）。
形は $\lambda=(3,2,1)$ である。最長の増加部分列は $1,2,4$ などで長さ $3=\lambda_1$、最長の減少部分列は $6,5,2$ などで長さ $3$ で、行の個数に等しい（cor-rsk-schensted）。交わらない 2 つの増加部分列 $3,6$ と $1,2,4$ の和集合は $5=\lambda_1+\lambda_2$ 個の項からなる（thm-rsk-greene）。
$S_3$ の 6 個の置換の $(P(\sigma),Q(\sigma))$ は次のとおりで、同じ形の標準盤の組が一度ずつ現れる。
| $\sigma$ | $P(\sigma)$ | $Q(\sigma)$ | 形 |
|---|---|---|---|
| $123$ | $123$ | $123$ | $(3)$ |
| $132$ | $12/3$ | $12/3$ | $(2,1)$ |
| $213$ | $13/2$ | $13/2$ | $(2,1)$ |
| $231$ | $13/2$ | $12/3$ | $(2,1)$ |
| $312$ | $12/3$ | $13/2$ | $(2,1)$ |
| $321$ | $1/2/3$ | $1/2/3$ | $(1,1,1)$ |
$f^{(3)}=f^{(1,1,1)}=1$、$f^{(2,1)}=2$ で、$1^2+2^2+1^2=6=3!$ である。
$$
A=\begin{pmatrix}1&0&2\\0&2&0\\1&1&0\end{pmatrix},\qquad w_A=\begin{pmatrix}1&1&1&2&2&3&3\\1&3&3&2&2&1&2\end{pmatrix}
$$
とする。下の段の $1,3,3,2,2,1,2$ を順に行挿入すると $P=1122/23/3$、記録盤は $Q=1113/22/3$ になる。$P$ の内容 $(2,3,2)$ は $A$ の列の和、$Q$ の内容 $(3,2,2)$ は行の和である。$Q$ の $1$ は第 1–3 列に、$2$ は第 1–2 列に、$3$ は第 4 列と第 1 列にあり、同じ数は同じ列にない（thm-rsk の証明）。
Schensted の定理と Greene の定理
この節では、相異なる整数の列 $w=w_1w_2\cdots w_N$（語という）を扱う。番号の集合 $S=\{p_1<\cdots< p_\ell\}\subseteq\{1,\dots,N\}$ が $w_{p_1}<\cdots< w_{p_\ell}$ を満たすとき $S$ を増加部分列、$w_{p_1}>\cdots>w_{p_\ell}$ を満たすとき減少部分列といい、$\ell$ をその長さという（空集合も両方に数える）。$k\ge1$ について
$$
I_k(w):=\max\bigl|S_1\cup\cdots\cup S_k\bigr|,\qquad D_k(w):=\max\bigl|S_1\cup\cdots\cup S_k\bigr|
$$
とおく。最大値は、$I_k$ では互いに交わらない $k$ 個の増加部分列、$D_k$ では互いに交わらない $k$ 個の減少部分列の組すべてにわたる。$I_1(w)$、$D_1(w)$ は最長の増加部分列、減少部分列の長さである。$P(w)$ を $\emptyset$ に $w_1,\dots,w_N$ を順に行挿入した盤とする（行挿入の定義と lem-rsk-insertion は、正の整数を整数に替えてもそのまま成り立つ）。数が相異なるので、$P(w)$ は行も列も狭義増加である。
Greene の定理（thm-rsk-greene）の証明には、語の次の変形を使う。
相異なる整数の語において、整数 $x< y< z$ が隣り合う 3 項として現れるとき、次の置き換えをKnuth の基本変形という。
$$
\text{(K1)}\quad\cdots yzx\cdots\ \longleftrightarrow\ \cdots yxz\cdots,\qquad\text{(K2)}\quad\cdots xzy\cdots\ \longleftrightarrow\ \cdots zxy\cdots
$$
基本変形の有限列で移り合う語を Knuth 同値といい、$w\equiv w'$ と書く。$u\equiv u'$、$v\equiv v'$ なら連結について $uv\equiv u'v'$ である。行も列も狭義増加の盤 $T$ の行を下の行から順に、各行を左から右へ読んだ語を $T$ の読み語 $\operatorname{rw}(T)$ という。
たとえば $\operatorname{rw}(124/35/6)=635124$ である。
$T$ を数が相異なる盤（行も列も狭義増加）、$x$ を $T$ に現れない整数とすると、$\operatorname{rw}(T)\,x\equiv\operatorname{rw}(T\leftarrow x)$ である。特に、相異なる整数の語 $w$ について $w\equiv\operatorname{rw}(P(w))$ である。
要点：行 $R$ に $x$ を挿入して $r_q$ が押し出されるとき、$x$ を (K1) で左へ、$r_q$ を (K2) で左端へ動かすと $Rx\equiv r_qR'$ となり、行ごとにこれを重ねる。
詳しい証明を開く
一行の場合。 行 $R=r_1\cdots r_p$（$r_1<\cdots< r_p$）に $x$ を挿入し、$r_q$ が押し出されたとする（$r_{q-1}< x< r_q$）。$k=p,p-1,\dots,q+1$ の順に、$x< r_{k-1}< r_k$ なので (K1) により $r_{k-1}r_kx$ を $r_{k-1}xr_k$ に替えると、$r_1\cdots r_qxr_{q+1}\cdots r_p$ を得る。次に、$q\ge2$ なら $r_{q-1}< x< r_q$ なので (K2) により $r_{q-1}r_qx$ を $r_qr_{q-1}x$ に替え、$k=q-2,\dots,1$ の順に $r_k< r_{k+1}< r_q$ なので (K2) により $r_kr_qr_{k+1}$ を $r_qr_kr_{k+1}$ に替える。結果は $r_q\,R'$（$R'$ は $r_q$ を $x$ に替えた行）で、$Rx\equiv r_qR'$ である。$x$ が押し出しをしないときは $Rx$ がそのまま新しい行である。
盤の場合。 行の個数についての帰納法による。$T$ の第 1 行を $R$、第 2 行以下の盤を $\bar T$ とすると $\operatorname{rw}(T)=\operatorname{rw}(\bar T)R$ である。$x$ が $R$ で $r_q$ を押し出すなら、一行の場合と帰納法の仮定により $$ \operatorname{rw}(T)\,x\equiv\operatorname{rw}(\bar T)\,r_q\,R'\equiv\operatorname{rw}(\bar T\leftarrow r_q)\,R'=\operatorname{rw}(T\leftarrow x) $$ である（$T\leftarrow x$ は第 1 行が $R'$、第 2 行以下が $\bar T\leftarrow r_q$ の盤）。押し出しがなければ $\operatorname{rw}(T)x=\operatorname{rw}(T\leftarrow x)$ である。後半は $w_1\cdots w_t\equiv\operatorname{rw}(P(w_1\cdots w_t))$ を $t$ についての帰納法で示せばよい。$\square$
$w\equiv w'$ ならすべての $k\ge1$ について $I_k(w)=I_k(w')$、$D_k(w)=D_k(w')$ である。
要点：(K1) で $I_k$ が変わらないことを直接示し、語の逆順と符号の反転で残りの場合に移す。
詳しい証明を開く
(K1) と $I_k$。 $w=u\,yzx\,v$、$w'=u\,yxz\,v$（$x< y< z$、$u,v$ は語）とし、項を値で同一視する。$w$ の増加部分列が $\{x,y,z\}$ と共有する部分は $\emptyset,\{x\},\{y\},\{z\},\{y,z\}$ のどれかで（$x$ は $y,z$ より後にあって小さい）、これらは $w'$ でも同じ順に並ぶので、$w$ の増加部分列は $w'$ でも増加部分列である。よって $I_k(w)\le I_k(w')$ である。逆に、$w'$ の交わらない増加部分列 $S_1,\dots,S_k$ のうち $x,z$ をともに含むもの $S$ がなければ、すべて $w$ でも増加部分列である。$S$ があるとき、$S=S_-\cup\{x,z\}\cup S_+$（$S_-$ は $u$ の、$S_+$ は $v$ の項）と書く。$y$ がどの $S_i$ にも属さなければ、$S$ の $x$ を $y$ に替える。$S_-$ の項は $x< y$ より小さいので、これは $w$ の増加部分列である。$y$ が別の $S_i=T_-\cup\{y\}\cup T_+$ に属するなら、$S$ と $S_i$ を $$ T_-\cup\{y,z\}\cup S_+,\qquad S_-\cup\{x\}\cup T_+ $$ に替える。前者は $T_-< y< z< S_+$、後者は $S_-< x< y< T_+$（不等号は項ごと）なので、どちらも $w$ の増加部分列で、互いに交わらず和集合は変わらない。よって $I_k(w')\le I_k(w)$ である。
対称性。 語 $w=w_1\cdots w_N$ に対し、$w^{\mathrm{rev}}:=w_N\cdots w_1$、$w^\sharp:=(-w_N)(-w_{N-1})\cdots(-w_1)$ とおく。番号を $p\mapsto N+1-p$ で移すと、$w$ の増加部分列は $w^\sharp$ の増加部分列に、$w$ の減少部分列は $w^{\mathrm{rev}}$ の増加部分列に一対一に移るので、$I_k(w^\sharp)=I_k(w)$、$D_k(w)=I_k(w^{\mathrm{rev}})$ である。$x< y< z$ について $yzx$、$yxz$ の逆順は $xzy$、$zxy$ で、これは (K2) の両辺である。$a:=-z< b:=-y< c:=-x$ とおくと $(yzx)^\sharp=cab$、$(yxz)^\sharp=acb$ で、これも (K2) の両辺である。$\mathrm{rev}$ と $\sharp$ はどちらも 2 回施すと元に戻るので、どちらも (K1) の変形と (K2) の変形を入れ替える。
(K2) で移り合う $w,w'$ については、$w^\sharp,w'^\sharp$ が (K1) で移り合うので $I_k(w)=I_k(w^\sharp)=I_k(w'^\sharp)=I_k(w')$ である。これで $I_k$ はどちらの基本変形でも変わらない。$w,w'$ が基本変形で移り合えば $w^{\mathrm{rev}},w'^{\mathrm{rev}}$ も基本変形で移り合うので、$D_k(w)=I_k(w^{\mathrm{rev}})=I_k(w'^{\mathrm{rev}})=D_k(w')$ である。$\square$
$T$ を数が相異なる形 $\lambda$ の盤（行も列も狭義増加）とすると、$I_k(\operatorname{rw}(T))=\lambda_1+\cdots+\lambda_k$、$D_k(\operatorname{rw}(T))=\lambda'_1+\cdots+\lambda'_k$ である。
要点：読み語の増加部分列は各列から、減少部分列は各行から高々 1 項しかとらない。
詳しい証明を開く
同じ列の 2 項 $a$（上）と $b$（下）では $a< b$ で、読み語では $b$ が先に現れるので、増加部分列は各列から高々 $1$ 項しかとらない。よって $k$ 個の増加部分列の和集合は第 $j$ 列から高々 $\min(k,\lambda'_j)$ 項をとり、$\sum_j\min(k,\lambda'_j)$ は第 $1$ 行から第 $k$ 行までの箱の個数 $\lambda_1+\cdots+\lambda_k$ に等しい（各列で上の $\min(k,\lambda'_j)$ 個の箱を数える）。等号は第 $1,\dots,k$ 行（各行は読み語の中で左から右へ増加する）で達成される。減少部分列は、行の中では数が増加するので各行から高々 $1$ 項しかとらず、同様に $k$ 個の和集合は高々 $\sum_i\min(k,\lambda_i)=\lambda'_1+\cdots+\lambda'_k$ 項である。第 $1,\dots,k$ 列を下から上へ読んだものは減少部分列なので等号が成り立つ。$\square$
$w$ を相異なる整数の語、$\lambda:=\operatorname{sh}(P(w))$ とする。すべての $k\ge1$ について
$$
I_k(w)=\lambda_1+\cdots+\lambda_k,\qquad D_k(w)=\lambda'_1+\cdots+\lambda'_k
$$
が成り立つ。
lem-rsk-knuth-insertion により $w\equiv\operatorname{rw}(P(w))$ なので、lem-rsk-knuth-invariant と lem-rsk-reading-word から $I_k(w)=I_k(\operatorname{rw}(P(w)))=\lambda_1+\cdots+\lambda_k$、$D_k(w)$ も同様である。$\square$
$\sigma\in S_n$ の Robinson–Schensted 対応の形を $\lambda$ とする。$\sigma(1),\dots,\sigma(n)$ の最長の増加部分列の長さは $\lambda_1$ に、最長の減少部分列の長さは $\lambda$ の行の個数 $\lambda'_1$ に等しい。
cor-rsk-schensted は thm-rsk-greene の $k=1$ の場合である。$\lambda_2$ そのものは、最長の増加部分列を一つ固定して残りから選べる増加部分列の長さとは限らない（rem-rsk-counterexamples の 4 行目）。$I_k$ は $k$ 個を同時に選んだときの値である。
$a,b\ge1$ とする。相異なる実数の長さ $ab+1$ の列は、長さ $a+1$ の増加部分列か長さ $b+1$ の減少部分列をもつ。
項を大小の順を保って $1,\dots,ab+1$ に取り替えても増加・減少部分列は変わらないので、置換 $\sigma\in S_{ab+1}$ としてよい。形を $\lambda$ とし、どちらもないとすると、cor-rsk-schensted により $\lambda_1\le a$、$\lambda'_1\le b$ である。Young 図形は $\lambda'_1$ 行からなり各行の箱は $\lambda_1$ 個以下なので、$ab+1=|\lambda|\le\lambda_1\lambda'_1\le ab$ となり矛盾する。$\square$
鳩の巣原理 の記事の定理「Erdős–Szekeres の定理」は $a=b$ の場合を鳩の巣原理で示している。
Knuth は、二つの語の $P$ が等しいことと Knuth 同値であることが同値であることを示した（Knu70 Theorem 6、p. 723。重複を許す語についての主張で、基本変形は Theorem 5（pp. 721–722）の形のもの）。また、行列 $A$ が $(P,Q)$ に対応するなら転置 $A^{\mathrm T}$ は $(Q,P)$ に対応し（同 Theorem 3、p. 719）、置換については $P(\sigma^{-1})=Q(\sigma)$ となる。これらはこの記事では証明しない。相異なる整数の語については、最初の主張を jeu de taquin の定理「直線形の盤は Knuth 同値類で決まる」が証明している。
反例の表
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 行挿入で押し出すのは $x_r$ より真に大きい数（「$x_r$ 以上」に替える） | 盤 $1$ に $1$ を挿入する | 挿入の結果が半標準盤であること（lem-rsk-insertion） |
| 二行配列で、上の段が等しいところは下の段を広義増加に並べる | $A=(1\ 1)$ の列を $\binom12,\binom11$ の順に挿入する | 記録盤 $Q$ が半標準盤であること（thm-rsk） |
| Robinson–Schensted 対応で $P$ と $Q$ の形が等しい | $n=3$ の、形を問わない標準盤の組全体 | 置換との一対一対応 |
| Greene の定理で $k$ 個の増加部分列を同時に選ぶ | $\sigma=236145$、$k=2$ | $I_2=\lambda_1+\lambda_2$ |
| Schensted の定理で語の項が相異なる | 語 $11$ | 最長の増加部分列の長さが $\lambda_1$ に等しいこと |
1 行目：「$1$ 以上」の数 $1$ を押し出すと、盤は第 1 列に $1,1$ が縦に並ぶ $1/1$ になり、列が狭義増加でない。
2 行目：$2$ を挿入して $1$ を挿入すると、$1$ が $2$ を押し出して $P=1/2$、記録盤は二つの箱にどちらも $1$ が書かれた $Q=1/1$ で、列が狭義増加でない。正しい順 $\binom11,\binom12$ では $P=12$、$Q=11$ である。
3 行目：$3$ 個の箱の標準盤は $f^{(3)}+f^{(2,1)}+f^{(1,1,1)}=4$ 個あり、組は $16$ 個だが、置換は $3!=6$ 個である。
4 行目：$P(236145)=1345/26$ で $\lambda_1+\lambda_2=6$ であり、交わらない増加部分列 $2,3,6$ と $1,4,5$ がこの値を与える。しかし長さ $4$ の増加部分列は $2,3,4,5$ だけで、残りの項 $6,1$ からとれる増加部分列の長さは $1$ なので、最長のものを先に固定すると和集合は $5$ 項にしかならない。
5 行目：$1$ に $1$ を挿入すると、第 1 行に $1$ より真に大きい数がないので右端の次に置かれ、$P=11$、$\lambda_1=2$ である。項が等しいので、狭義の増加部分列の長さは $1$ である。
関連項目
- 前提: Young図形, 対称群, Schur多項式
- 用いる記事: 鳩の巣原理, 対称関数
- 比較: Lindström–Gessel–Viennotの補題
- 発展: 群の表現, jeu de taquin
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
