jeu de taquin
概要
jeu de taquin（ジュ・ド・タカン、jeu de taquin）とは、歪 Young 図形に数を書き込んだ盤で、空いた箱の右と下の数のうち小さい方をその箱へすべらせる操作をくり返し、左上に詰まった盤へ変える手続きである。すべらせは読み語の Knuth 同値類を保ち、一つの Knuth 同値類には直線形の盤がただ一つしかないので、最後にできる盤（整化）はすべらせる順番によらず、読み語を行挿入した盤に等しい（Schützenberger の定理）。標準化により同じ数を許す半標準盤にも広がり、Littlewood–Richardson 係数を整化の個数として数える記述を与える。
jeu de taquin（ジュ・ド・タカン、フランス語で「15 パズル」の意）は、歪 Young 図形に数を書き込んだ盤から、数を一つずつ左か上の空いた箱へすべらせて、左上に詰まった通常の盤へ変えていく操作である。M.-P. Schützenberger が導入した。空いた箱の右と下の数のうち小さい方を動かすという規則で、行と列の増加が保たれる。
すべらせる順番には多くの選び方があるが、最後にできる盤は順番によらない（Schützenberger の定理、thm-jdt-rect）。しかもそれは、もとの盤の数を下の行から順に読んだ語に Robinson–Schensted–Knuth対応 の行挿入を施して得られる盤 $P$ に一致する。この一致を支えるのは、すべらせが読み語の Knuth 同値類を変えないこと（thm-jdt-slide-knuth）と、一つの Knuth 同値類には左上に詰まった盤がちょうど一つしかないこと（thm-jdt-knuth-unique）である。
この記事では、数が相異なる盤についてこれら三つの定理を証明し、同じ数を許す半標準盤へ広げる。応用として、盤の積と、Littlewood–Richardson 係数を jeu de taquin で数える記述を述べる。
歪盤とすべらせ
分割、Young 図形、箱 $(i,j)$（第 $i$ 行・第 $j$ 列、行は上から下へ番号を付ける）、角は Young図形 の記事のとおりとする。分割 $\mu\subseteq\lambda$ に対し、$\lambda/\mu:=D(\lambda)\setminus D(\mu)$ を歪 Young 図形という（同記事の反例の表の段落）。歪 Young 図形の各行・各列の箱は、それぞれ連続した区間をなす。
相異なる整数を歪 Young 図形 $\lambda/\mu$ の各箱に一つずつ書き込んだもの $S$ で、各行で左から右へ、各列で上から下へ増加するものを、形 $\lambda/\mu$ の歪盤という。$\mu=\emptyset$ のとき直線形の盤という。$S$ の行を下の行から順に、各行を左から右へ読んだ語を $S$ の読み語 $\operatorname{rw}(S)$ という。
直線形の盤の読み語は Robinson–Schensted–Knuth対応 の定義「Knuth同値」の読み語と同じものである。
$\mu$ の角を $\lambda/\mu$ の内角という。内角 $c$ は $\mu$ の箱で、$\mu\setminus\{c\}$ はまた Young 図形である。
$S$ を形 $\lambda/\mu$ の歪盤、$c$ をその内角とする。$c$ を空き箱として、次の手順をくり返す。空き箱を $h=(i,j)$ とし、その右の箱 $(i,j+1)$ と下の箱 $(i+1,j)$ のうち $\lambda$ に入るものを見る。
- どちらも $\lambda$ に入らなければ終える。
- 片方だけが入れば、その箱の数を $h$ へ移し、その箱を新しい空き箱とする。
- 両方が入れば、二つの数のうち小さい方を $h$ へ移し、それがあった箱を新しい空き箱とする。
終わったときの空き箱を $e$ とし、得られた書き込みを $\mathrm{j}_c(S)$ と書く。$S$ から $\mathrm{j}_c(S)$ を作る操作を、$c$ へのすべらせ（jeu de taquin slide）という。下の数を上へ移す一歩を縦の一歩、右の数を左へ移す一歩を横の一歩という。
def-jdt-slide の記号で、$e$ は $\lambda$ の角であり、$\mathrm{j}_c(S)$ は形 $(\lambda\setminus\{e\})/(\mu\setminus\{c\})$ の歪盤である。
要点：空き箱の左右の数、上下の数がそれぞれ増加の向きに並ぶことが、一歩ごとに保たれる。
詳しい証明を開く
$\mu^\circ:=\mu\setminus\{c\}$ は分割なので、$R:=\lambda/\mu^\circ$ も歪 Young 図形で、手順の途中では $R$ の空き箱以外の箱がすべて埋まっている。空き箱 $h=(i,j)\in R$ について、$(i,j+1)$ と $(i+1,j)$ は $\mu^\circ$ に入らない（$\mu^\circ$ の第 $i$ 行の長さは $j$ 未満、第 $i+1$ 行の長さはそれ以下だから）。したがって手順の「$\lambda$ に入る」は「$R$ に入る」と同じである。
次の 2 条件を不変条件とする。(a) 埋まった箱のうち、同じ行で隣り合う 2 箱、同じ列で隣り合う 2 箱の数は、右・下の方が大きい。(b) 空き箱の左右の箱がともに埋まっていれば左の数が小さく、上下の箱がともに埋まっていれば上の数が小さい。最初は $S$ が歪盤なので (a) が成り立ち、$c$ の左と上の箱は $\mu^\circ$ に入るので (b) は条件がない。
空き箱 $h=(i,j)$ で縦の一歩を踏み、下の数 $d$ を $h$ へ移したとする（右の数 $r$ がないか、$d< r$）。$h$ に入った $d$ について、右の $r$ とは $d< r$、上の数 $u$ とは (b) から $u< d$ である。左の箱 $(i,j-1)$ が埋まっているとき、その数を $l$ とする。$(i,j-1)$ と $(i+1,j)$ が $R$ に入るので $(i+1,j-1)$ も $R$ に入り（歪 Young 図形の行は区間で、$\mu^\circ$ の第 $i+1$ 行は第 $i$ 行より長くない）、空き箱でないので埋まっている。その数を $l'$ とすると、(a) から $l< l'< d$ である。$d$ の下は新しい空き箱である。新しい空き箱 $(i+1,j)$ について、左右の数 $l'$ と $(i+1,j+1)$ の数はもとの行で $d$ をはさんで並んでいたので左が小さく、上の $d$ と下の $(i+2,j)$ の数はもとの列で隣り合っていたので上が小さい。横の一歩（右の数 $r$ を移す。$d$ がないか、$r< d$）も同様である。$h$ に入った $r$ について、左の数とは (b)、下の $d$ とは $r< d$、上の箱 $(i-1,j)$ が埋まっていれば $(i-1,j+1)$ も $R$ の埋まった箱で、その数 $u'$ と (a) から（上の数）$< u'< r$ である。新しい空き箱 $(i,j+1)$ では、左の $r$ と右の $(i,j+2)$ の数はもとの行で隣り合っていたので左が小さく、上の $(i-1,j+1)$ の数 $u'$ と下の $(i+1,j+1)$ の数は、もとの列で $r$ をはさんでいたので $u'< r<$（下の数）である。
手順が終わるとき、空き箱 $e=(i,j)$ の右と下の箱は $R$ に入らず、上で見たように $\mu^\circ$ にも入らないので $\lambda$ に入らない。よって $e$ は $\lambda$ の角であり、$\lambda\setminus\{e\}$ は分割である。$e$ の右と下は空なので、(a) から $\mathrm{j}_c(S)$ の隣り合う箱はすべて増加し、行と列は区間なので各行・各列で増加する。$\square$
すべらせは逆にたどれる。$e$ に空き箱を置き、左の箱と上の箱の数のうち大きい方を右・下へ移すことをくり返すと、手順の各歩が一つずつ取り消されて $c$ で止まり、$S$ に戻る。たとえば縦の一歩で $d$ を $(i,j)$ へ移した直後の空き箱 $(i+1,j)$ では、上の $d$ が左の数 $l'$ より大きいので $d$ が下へ戻る。この逆の操作を逆すべらせという。
形 $(3,2,2)/(2,1)$ の歪盤
$$
S=\begin{array}{ccc}\cdot&\cdot&3\\\cdot&1&\\2&4&\end{array}
$$
（$\cdot$ は $\mu=(2,1)$ の箱）を考える。$\operatorname{rw}(S)=2413$ である。内角は $(1,2)$ と $(2,1)$ の二つある。
$(2,1)$ へすべらせると、右の $1$ と下の $2$ のうち $1$ が左へ動き、次に空き箱 $(2,2)$ の下の $4$ が上へ動いて、$(3,2)$ で終わる。続いて $(1,2)$、$(1,1)$ の順にすべらせると
$$
\begin{array}{ccc}\cdot&\cdot&3\\1&4&\\2&&\end{array}
\ \to\
\begin{array}{cc}\cdot&3\\1&4\\2&\end{array}
\ \to\
\begin{array}{cc}1&3\\2&4\end{array}
$$
となる。最初に $(1,2)$ へすべらせると、$1$ が上へ、$4$ が上へ動いて $\begin{smallmatrix}\cdot&1&3\\\cdot&4&\\2&&\end{smallmatrix}$ となり、続けて $(2,1)$、$(1,1)$ へすべらせると、やはり $\begin{smallmatrix}1&3\\2&4\end{smallmatrix}$ になる。どちらの順でも、行挿入で作った盤 $P(2413)$ と一致する（$2$、$4$ を入れたあと $1$ が $2$ を、$3$ が $4$ を押し出す）。$(2,1)$ への最初のすべらせのあとの読み語 $2143$ は、$2413$ の連続する $413$ を Knuth の基本変形 (K2) で $143$ に替えたものである。
Knuth 同値類の中の盤
相異なる整数の語、Knuth の基本変形 (K1)・(K2)、Knuth 同値 $\equiv$、語 $w$ を行挿入して得る盤 $P(w)$ は Robinson–Schensted–Knuth対応 の節「Schensted の定理と Greene の定理」のとおりとする。同記事の補題「行挿入は Knuth 同値を保つ」により $w\equiv\operatorname{rw}(P(w))$ である。整数 $m$ と語 $w$ について、$m$ 以下の文字だけを順に残した語を $w|_{\le m}$ と書く。盤 $T$ についても、$m$ 以下の数が入った箱だけを残したものを $T|_{\le m}$ と書く。
- $w\equiv w'$ なら、すべての $m$ について $w|_{\le m}\equiv w'|_{\le m}$ である。
- $T$ が直線形の盤なら、$T|_{\le m}$ も直線形の盤で、$\operatorname{rw}(T|_{\le m})=\operatorname{rw}(T)|_{\le m}$ である。
1．基本変形 1 回の場合を示せばよい。(K1) $\cdots yzx\cdots\leftrightarrow\cdots yxz\cdots$（$x< y< z$）で、$m\ge z$ なら制限した語どうしも (K1) で移り合う。$y\le m< z$ なら両辺とも $\cdots yx\cdots$、$x\le m< y$ なら両辺とも $\cdots x\cdots$、$m< x$ なら同じ語になる。(K2) $\cdots xzy\cdots\leftrightarrow\cdots zxy\cdots$ も同様で、$y\le m< z$ なら両辺とも $\cdots xy\cdots$ になる。三文字の外の文字は変わらない。2．行と列が増加するので、$m$ 以下の数の箱は各行の左端からの区間をなし、行の長さは下へ行くほど長くならない。読み語の順序は制限しても変わらない。$\square$
$T$、$T'$ を直線形の盤とし、$\operatorname{rw}(T)\equiv\operatorname{rw}(T')$ とする。このとき $T=T'$ である。したがって、相異なる整数の語 $w$、$w'$ について、$w\equiv w'$ であることと $P(w)=P(w')$ であることは同値である（Knu70 Theorem 6、p. 723）。
要点：Greene の定理により、読み語の Knuth 同値類から盤の形が読める。小さい文字に制限して各段の形を読めば、盤の数の位置が決まる。
詳しい証明を開く
Knuth 同値な語は同じ文字の集合をもつので、$T$ と $T'$ の数の集合は等しい。それを $a_1<\cdots< a_N$ とする。$k=1,\dots,N$ について lem-jdt-restrict により $\operatorname{rw}(T|_{\le a_k})\equiv\operatorname{rw}(T'|_{\le a_k})$ である。Robinson–Schensted–Knuth対応 の補題「読み語の $I_k$ と $D_k$」により、直線形の盤 $U$ の形 $\nu$ は $I_l(\operatorname{rw}(U))=\nu_1+\cdots+\nu_l$（$l\ge1$）から決まり、同記事の補題「Knuth変形で $I_k$ と $D_k$ は変わらない」により $I_l$ は Knuth 同値類で決まる。よって $T|_{\le a_k}$ と $T'|_{\le a_k}$ は同じ形 $\nu^{(k)}$ をもつ。$a_k$ はどちらの盤でも $\nu^{(k)}\setminus\nu^{(k-1)}$ のただ一つの箱にあるので、$T=T'$ である。
後半：$P(w)=P(w')$ なら $w\equiv\operatorname{rw}(P(w))=\operatorname{rw}(P(w'))\equiv w'$ である。逆に $w\equiv w'$ なら $\operatorname{rw}(P(w))\equiv w\equiv w'\equiv\operatorname{rw}(P(w'))$ なので、前半から $P(w)=P(w')$ である。$\square$
とくに直線形の盤 $T$ について $P(\operatorname{rw}(T))=T$ である（$\operatorname{rw}(P(\operatorname{rw}(T)))\equiv\operatorname{rw}(T)$ に定理を当てる）。
すべらせは Knuth 同値類を保つ
すべらせの横の一歩は、行の中で数を一つ左へ詰めるだけなので読み語を変えない。縦の一歩では、空き箱のある行とその下の行だけが変わる。その 2 行の読み語の変化を、行挿入で計算する。
$0\le p\le r$、$0\le s\le q$ とし、相異なる整数
$$
u_1<\cdots< u_p,\qquad v_1<\cdots< v_q,\qquad x_1<\cdots< x_r< b< y_1<\cdots< y_s
$$
が、$u_{p-t}< x_{r-t}$（$0\le t< p$）、$v_t< y_t$（$1\le t\le s$）、$q\ge1$ なら $b< v_1$ を満たすとする。語を並べて書くと、
$$
P(x\,b\,y\,u\,v)=P(x\,y\,u\,b\,v),\qquad\text{したがって}\qquad x\,b\,y\,u\,v\equiv x\,y\,u\,b\,v
$$
である。ここで $x=x_1\cdots x_r$ などと書いた。
要点：どちらの語でも、$u$ は $x$ の数だけを押し出し、$v$ は $y$ の数だけを押し出す。押し出しの順序は違うが、最後に 2 行とも同じ盤になる。
詳しい証明を開く
$u$ の挿入。増加する行 $x\,b\,y$ に $u_1,\dots,u_p$ を順に行挿入する。$u_t$ が置かれる位置は、$u_{t-1}$ が置かれた位置より右で、$u_t$ より大きいいちばん左の数の位置である。$t$ についての帰納法で、$u_t$ は第 $r-p+t$ 番目以内に置かれ、押し出すのは $x$ の数であることを示す。$u_{t-1}$ が第 $r-p+t-1$ 番目以内に置かれたなら、第 $r-p+t$ 番目にはまだ $x_{r-p+t}$ があり、$u_t< x_{r-p+t}$ なので、$u_t$ はそこか、その左に置かれる。押し出された数は $x$ の数で、前に押し出された数より右にあったので大きい。よって第 1 行は $x'\,b\,y$（$x'$ は長さ $r$ の増加列で、その数は $x$ と $u$ の数でありすべて $b$ より小さい）、第 2 行は押し出された数の増加列 $z$（長さ $p$）になる。$x\,y$ に $u$ を挿入しても、置かれる位置と押し出される数は同じなので、第 1 行は $x'\,y$、第 2 行は $z$ になる。
左辺。$v_t$（$t\le s$）を挿入する直前の第 1 行は $x'\,b\,v_1\cdots v_{t-1}\,y_t\cdots y_s$ で、$b< v_t< y_t$ なので $v_t$ は $y_t$ を押し出す。$y_t$ は $z$ と $y_1,\dots,y_{t-1}$ より大きいので第 2 行の右端に付く。$t>s$ の $v_t$ は第 1 行の右端に付く。結果は第 1 行 $x'\,b\,v$、第 2 行 $z\,y$ である。
右辺。$s=0$ なら、$b$ と $v$ は第 1 行の右端に順に付き、結果は第 1 行 $x'\,b\,v$、第 2 行 $z$ である。$s\ge1$ なら、$b$ は $x'$ のどの数より大きく $y_1$ より小さいので $y_1$ を押し出し、第 1 行は $x'\,b\,y_2\cdots y_s$、第 2 行は $z\,y_1$ になる。$v_t$（$t\le s-1$）を挿入する直前の第 1 行は $x'\,b\,v_1\cdots v_{t-1}\,y_{t+1}\cdots y_s$ で、$v_t< y_t< y_{t+1}$ なので $v_t$ は $y_{t+1}$ を押し出し、$y_{t+1}$ は第 2 行の右端に付く。$t\ge s$ の $v_t$ は第 1 行の右端に付く。結果は左辺と同じく第 1 行 $x'\,b\,v$、第 2 行 $z\,y$ である。
最後に、thm-jdt-knuth-unique の後半（$P$ が等しい語は Knuth 同値）を使う。$\square$
歪盤 $S$ とその内角 $c$ について $\operatorname{rw}(\mathrm{j}_c(S))\equiv\operatorname{rw}(S)$ である。
手順の途中の書き込みについても、空き箱を飛ばして読み語を定める。各歩で読み語が Knuth 同値な語に替わることを示せばよい。横の一歩は読み語を変えない。空き箱 $(i,j)$ で縦の一歩を踏むとする。第 $i$ 行の空き箱の左の数を $u_1<\cdots< u_p$、右の数を $v_1<\cdots< v_q$、第 $i+1$ 行の第 $j$ 列より左の数を $x_1<\cdots< x_r$、第 $j$ 列の数を $b$、右の数を $y_1<\cdots< y_s$ とする。第 $i$ 行の左端の列は第 $i+1$ 行の左端の列より左にないので $p\le r$、右端についても同様に $s\le q$ である。$u_{p-t}$ と $x_{r-t}$ は同じ列（第 $j-1-t$ 列）で上下に並び、$v_t$ と $y_t$ も同じ列（第 $j+t$ 列）で上下に並ぶので、prf-jdt-slide-tableau の不変条件 (a) から $u_{p-t}< x_{r-t}$、$v_t< y_t$ である。縦の一歩を踏むのは $v_1$ がないか $b< v_1$ のときである。読み語は第 $i+1$ 行、第 $i$ 行の順に連続して読むので、一歩の前後で読み語の該当部分は $x\,b\,y\,u\,v$ から $x\,y\,u\,b\,v$ に替わり、ほかの部分は変わらない。lem-jdt-two-rows と、Knuth 同値が語の連結と両立することから結論を得る。$\square$
整化と Schützenberger の定理
歪盤 $S$ に、内角へのすべらせを内側の図形 $\mu$ が空になるまでくり返すと、$|\mu|$ 回で直線形の盤が得られる（lem-jdt-slide-tableau により各回で $\mu$ の箱が一つ減る）。これを $S$ の整化（rectification）という。各回にどの内角を選ぶかで、整化の手順は一般に複数ある。
歪盤 $S$ の整化は手順によらず、$P(\operatorname{rw}(S))$ に等しい。これを $\operatorname{Rect}(S)$ と書く。さらに、二つの歪盤 $S$、$S'$ について、$\operatorname{Rect}(S)=\operatorname{Rect}(S')$ であることと $\operatorname{rw}(S)\equiv\operatorname{rw}(S')$ であることは同値である。
整化の手順の一つで得られた直線形の盤を $R$ とする。thm-jdt-slide-knuth を各回に当てて $\operatorname{rw}(R)\equiv\operatorname{rw}(S)$ である。一方 $\operatorname{rw}(P(\operatorname{rw}(S)))\equiv\operatorname{rw}(S)$ なので、thm-jdt-knuth-unique により $R=P(\operatorname{rw}(S))$ である。後半は $\operatorname{Rect}(S)=P(\operatorname{rw}(S))$ と thm-jdt-knuth-unique の後半による。$\square$
ex-jdt-example の二つの手順が同じ盤になったのはこの定理の例である。定理の後半から、すべらせと逆すべらせで移り合う歪盤は読み語が Knuth 同値であり、逆に読み語が Knuth 同値な二つの歪盤は、整化と逆すべらせを組み合わせて互いに移り合う。
盤の積。 数の集合が交わらない直線形の盤 $T$、$U$ について、$T$ を左下に、$U$ をその右上に、行も列も共有しないように置いた歪盤を $T*U$ とする（行と列が増加する条件は $T$ と $U$ の中だけの条件になる）。$T*U$ の下の行はすべて $T$ の行なので $\operatorname{rw}(T*U)=\operatorname{rw}(T)\operatorname{rw}(U)$ であり、thm-jdt-rect から
$$
\operatorname{Rect}(T*U)=P(\operatorname{rw}(T)\operatorname{rw}(U))=\bigl(\cdots(T\leftarrow w_1)\leftarrow\cdots\bigr)\leftarrow w_k
$$
（$w=w_1\cdots w_k=\operatorname{rw}(U)$）を得る。最後の等号は $P(\operatorname{rw}(T))=T$ による。積 $T\cdot U:=\operatorname{Rect}(T*U)$ は結合的である。数の集合が交わらない三つの盤について、$\operatorname{rw}(T\cdot U)\equiv\operatorname{rw}(T)\operatorname{rw}(U)$ と Knuth 同値の連結との両立から、どちらの括弧の付け方でも $P(\operatorname{rw}(T)\operatorname{rw}(U)\operatorname{rw}(V))$ になるからである。同じ文字を許す語に広げた Knuth 同値類のモノイドは、Lascoux–Schützenberger のプラクティック・モノイドと呼ばれる。
半標準盤への拡張
同じ数を許す場合、歪半標準盤は、正の整数を書き込み、行で広義増加、列で狭義増加するものとする（直線形のものは Schur多項式 の定義「半標準盤と盤の重み」の半標準盤である）。すべらせの規則は、右の数 $r$ と下の数 $d$ が両方あるとき、$d\le r$ なら $d$ を、$d>r$ なら $r$ を動かすものとする。等しいときは下の数を動かす。
歪半標準盤 $S$ の箱を、数の小さい順に、数が等しい箱は列の左のものから順に並べ、$1,2,\dots$ と番号を書き込んだものを $S$ の標準化 $\operatorname{std}(S)$ という。数が等しい箱は列が異なり、同じ行では左から並ぶので、$\operatorname{std}(S)$ は歪盤である。$S$ は $\operatorname{std}(S)$ と各番号の数（もとの値）から復元できる。
歪半標準盤 $S$ とその内角 $c$ について、$\mathrm{j}_c(S)$ は歪半標準盤であり、$\operatorname{std}(\mathrm{j}_c(S))=\mathrm{j}_c(\operatorname{std}(S))$ である（右辺は番号を運んだすべらせ、左辺はもとの値を運んだすべらせ）。したがって $S$ の整化は手順によらず、$\operatorname{std}(\operatorname{Rect}(S))=\operatorname{Rect}(\operatorname{std}(S))$ である。
要点：同じ値の数の左右の順は、すべらせの間ずっと変わらず、同じ列にも並ばない。
詳しい証明を開く
$S$ の各箱にもとの値と番号の両方を書いておき、値のすべらせと番号のすべらせを並べて行う。一歩ごとに二つの規則が同じ箱を動かすことと、次の性質 (Q) が保たれることを、歩数についての帰納法で示す。(Q) 同じ値の数は同じ列になく、番号は値の小さい順、値が等しければ列の左から順に付いている。最初は標準化の定義から (Q) が成り立つ。空き箱の右の数 $r$ と下の数 $d$ の値が異なれば、(Q) から番号の大小は値の大小と一致し、二つの規則は同じ箱を動かす。値が等しければ、$d$ は第 $j$ 列、$r$ は第 $j+1$ 列にあるので $d$ の番号が小さく、どちらの規則も $d$ を動かす。縦の一歩は列を変えないので (Q) を保つ。横の一歩で $r$ が第 $j+1$ 列から第 $j$ 列へ移るとき、第 $j$ 列に値 $r$ の数がないことを示せば、同じ値の数の列の左右の順は変わらず (Q) が保たれる。第 $j$ 列の空き箱より下の数は $d$ 以上で、$d>r$（等しければ $d$ を動かしている）。空き箱より上の数は、すぐ上の数 $u$ 以下である。$u$ の右の箱 $(i-1,j+1)$ は（prf-jdt-slide-tableau と同じ理由で）埋まっていて、その数 $u'$ について、行の広義増加から $u\le u'$、$r$ の真上にあるので列の狭義増加から $u'< r$ である。よって第 $j$ 列に値 $r$ の数はない。この比較に使った、埋まった箱どうしの行の広義増加と列の狭義増加は、番号のすべらせが lem-jdt-slide-tableau により歪盤を保つことと (Q) から従う。番号は行で増加し、番号の順は値の順を細分するので値は行で広義増加し、列でも広義増加し、(Q) から同じ値が同じ列にないので列で狭義増加する。
終わったとき、(Q) は番号がもとの値の書き込みの標準化であることを意味するので、$\operatorname{std}(\mathrm{j}_c(S))=\mathrm{j}_c(\operatorname{std}(S))$ であり、上の議論から $\mathrm{j}_c(S)$ は歪半標準盤である。整化をくり返すと $\operatorname{std}$ 側は thm-jdt-rect により手順によらず、$S$ の整化はその番号ともとの値から復元されるので、手順によらない。$\square$
Littlewood–Richardson 係数
Schur 多項式の積の展開係数 $c^\nu_{\lambda\mu}$（Schur多項式 の定理「Littlewood–Richardson 規則」）は、jeu de taquin で数えることができる。分割 $\lambda$、$\mu$ に対し、$\lambda$ の Young 図形を左下に、$\mu$ の Young 図形をその右上に、行も列も共有しないように置いた歪 Young 図形を $\lambda*\mu$ と書く。
分割 $\lambda$、$\mu$、$\nu$ と、形 $\nu$ の半標準盤 $C$ を一つ固定する。$c^\nu_{\lambda\mu}$ は、形 $\lambda*\mu$ の歪半標準盤 $S$ で $\operatorname{Rect}(S)=C$ となるものの個数に等しい（vLe01 §1.3 の歪形の積の定義（p. 4）と Corollary 2.5.3（p. 14）。この記事では証明しない）。とくにこの個数は $C$ の選び方によらない。
$\lambda=\mu=(1)$ とする。$\lambda*\mu=(2,1)/(1)$ は箱 $(2,1)$ と $(1,2)$ からなる。$(2,1)$ に $a$、$(1,2)$ に $b$ を書いた歪半標準盤（条件はない）を内角 $(1,1)$ へすべらせると、$a\le b$ なら $a$ が上へ動いて 1 行の盤 $a\,b$ に、$a>b$ なら $b$ が左へ動いて $b$ の下に $a$ がある 1 列の盤になる。$\nu=(2)$、$C=1\,1$ とすると $\operatorname{Rect}(S)=C$ となるのは $a=b=1$ だけで、$\nu=(1,1)$、$C$ を $1$ の下に $2$ がある盤とすると $b=1$、$a=2$ だけである。よって $c^{(2)}_{(1)(1)}=c^{(1,1)}_{(1)(1)}=1$ で、$s_{(1)}^2=s_{(2)}+s_{(1,1)}$ と一致する。
反例の表
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 右と下の数の小さい方を動かす | 形 $(2,1)/(1)$ で $(1,2)$ に $1$、$(2,1)$ に $2$ を書いた歪盤で、大きい $2$ を上へ動かす | 結果が歪盤であること（lem-jdt-slide-tableau） |
| 数が等しいときは下の数を動かす | 形 $(2,2)/(1)$ で $(1,2)$ と $(2,1)$ に $1$、$(2,2)$ に $2$ を書いた歪半標準盤で、右の $1$ を左へ動かす | 結果が歪半標準盤であること（prop-jdt-std） |
| 盤が直線形である | 形 $(3,2,1)/(2,1)$ の二つの歪盤（下の注意） | 読み語が Knuth 同値なら盤が等しいこと（thm-jdt-knuth-unique） |
1 行目：$2$ を上へ動かすと第 1 行が $2\,1$ になり、行の増加が崩れる。規則どおりなら $1$ が左へ動いて、$1$ の下に $2$ がある盤になる。2 行目：右の $1$ を左へ動かすと、空き箱 $(1,2)$ の下の $2$ が上へ動き、第 1 行 $1\,2$、第 2 行 $1$ となって、第 1 列に $1$ が二つ縦に並ぶ。規則どおり下の $1$ を上へ動かすと、続いて $2$ が左へ動き、第 1 行 $1\,1$、第 2 行 $2$ の半標準盤になる。3 行目：形 $(3,2,1)/(2,1)$ の箱は $(1,3)$、$(2,2)$、$(3,1)$ で、どの二つも同じ行・列にない。$(1,3),(2,2),(3,1)$ に $1,3,2$ を書いた $S_1$ と $3,1,2$ を書いた $S_2$ はともに歪盤で、読み語は $231$ と $213$ である。これらは (K1)（$x=1$、$y=2$、$z=3$）で移り合うが、$S_1\ne S_2$ である。どちらの整化も $\begin{smallmatrix}1&3\\2&\end{smallmatrix}$ になる（thm-jdt-rect の後半）。
関連項目
- 前提: Young図形, Robinson–Schensted–Knuth対応
- 用いる記事: Schur多項式
- 比較: Murnaghan–中山の規則
- 発展: Schubert calculus
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
