数理解析研究所講究録1109 巻 1999 年 174-181

174

On the Robinson-Schensted correspondence
森田英章
北海道大学大学院理学研究科

平成 11 年 2 月 24 日

1Intorduction
Robinson-Schensted 対応 $RS$ [Rl[Sl(日本語の丁寧な解説記事として [T] を挙げておは, 対称群 $W=S_{n}$ と同じの間の哨然な’ 全単射$n$$\langle$)の分割を台にもつ Young 標準盤の対 $(P, Q)$ 全体のなす集合と$RS:Warrow \mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)\cross \mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)$

を台に持つ標準盤全体のなす集合を表す.
は, 分割を与える. ここで STabから直ちにこの全単射が存在すること自体は以下に述べるように対称群の表現論導かれることであるが, Robinson-Schensted 対応はその全単射を自然なかたちで具体的に与えたものである.
上での表現は完全可約であり, 任意の表現はその既約成分の直和に対称群の複素数体に $W$ の元を左から . $\sum_{v\in W}C_{v}v:=\sum v\in W$ cvwv
分解される. -方, 対称群の群生を表現空間とする $W$ の表現 (左正則表現) が得られる.
で作用させることによって,この表現を既約分解すると, その既約成分として全ての既約表現 (の同型類) が, それ自身の表現空間の次元を重複度として現れる. よく知られているように, 次対称群の既約表現のによって parametrize されているので, その既約表現をの分割\mbox{\boldmath $\lambda$}
同型類はで表すと次の式が得られる:$\lambda$$(\lambda)$$[\mathrm{I}][\mathrm{J}\mathrm{K}]$$\mathrm{C}$$\mathrm{C}[W]$

$w$

$w$

$\mathrm{C}[W]$

$n$

$n$

$=(\lambda_{1}, \ldots, \lambda_{d})$$\ovalbox{\tt\small REJECT}$$\mathrm{C}[W]=\bigoplus_{\lambda\vdash n}(\dim L_{\lambda})L_{\lambda}$の次元は Stabまた, これもよく知られているが次元を比較することにより次式を得る:$L_{\lambda}$.

$(\lambda)$.

$n!= \sum_{n\lambda\vdash}|\mathrm{s}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)|^{2}$の元の個数に等しいので, 両辺の175

これにより上記の全単射の存在のみは知れるが, Robinson-Schensted 対応はこの全単射を具体的かつ自然な形で実現するものである.
ところが, 哨然な形で’ とはいうもののその対応は $-$ 目で分かるというものではない. すなわち, あたえられた $w\in W$ に対応する $RS(w)=(P, Q)$ を構成するにはある程度の煩雑な操作を必要とし, 一般にはを見ただけでわかるといった類のものではないし, 逆に与えられたから $RS^{-1}(P, Q)$ を構成する場合も同様である. ところが, 与えられた $(P, Q)$ がある条件をみたすと, その場合は対応する $w=Rs^{-1}(P, Q)$ が– 目で見いだせることがある [Mo]. 本稿ではそのことに関して述べたいと思う.
$w$$(P, Q)\in \mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)\cross \mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)$

2

Robinson-Schensted 対応

ここでは, まず Robinson-Schensted 対応を概観し, 幾つかの具体例を計算してみたいと思う. 主定理を述べるために少々細かい記号も導入したため, いささか読み安さを欠くかもしれないので, その際は [T] を参照していただきたい. はじめに対称群 $W=\$ の元$w=(w(1)w(2)\cdots w(n))$ に対して如何に同じ台を持つ Young 標準盤の対 $RS(w)=(P, Q)$を対応させるか、 その手続きを紹介する. その前にいままでも用いてきた幾つかの基本的な概念を定義し直しておく. 用語は概ね [M] に従う.
を正整数とする.の分割 (partition) とは正整数列\mbox{\boldmath $\lambda$}
で次の二つの条件$n$$=(\lambda_{1}, \ldots , \lambda_{d})$$n$を満たすものとする:

1.

$\lambda_{1}\geq\cdots\geq\lambda_{d}$2.

$\lambda_{1}+\cdots+\lambda_{d}=n$,.

例えば $n=5$ の場合には(5) $(4, 1)$ , $(3, 2)$ , (3, 1, 1), (2, 2, 1), (2, 1, 1, 1), (1, 1, 1, 1, 1)$)$の七つである. また上の定義における旧よ分割 の長さ, あるいは深さと呼ばれる.の Young 図形 (Young diagram)
分割とは, 1 行目に個のハコ,2 行目に個のハコ,行目に個のハコを左側をそろえてならべたものである. す$\lambda$$\lambda=(\lambda_{1}, \ldots, \lambda_{d})$$\lambda_{2}$$\cdot$. .,$Y(\lambda)$$\mathrm{d}$$\lambda_{1}$$\lambda_{d}$なわち, $Y(\lambda)=\{(i,j)|1\leq i\leq d, 1\leq j\leq\lambda_{i}\}$ と置き, 各点 $(i,j)$ に一つずつハコが置かれてると理解する. そのとき, 座標は左から右へ, 上から下へ増えるものとする. 特に, 空集合
も ‘分割’(0) の Young 図形と思うことにする.
分割, あるいはその Young 図形
を台とする盤 (tableau) $T$ とは,単射 $T:Y(\lambda)arrow \mathrm{Z}_{>0}$ のことであり, これは Young 図形のハコの中に正整数をひと$T$つずつ書き込んだものと理解される. また が標準盤 (standard tableau) であるとは, $T$ には 1 からが– 回線つ書き込まれており, かつそれちは列方向, 行方向に関して狭義に増大していることを意味する. ここで, 標準盤は写像 $Y=Y(\lambda)arrow\{1,2, \ldots, n\}$ として見た場$\phi$$\lambda=(\lambda_{1}, \ldots, \lambda_{d})$$Y(\lambda)$$Y(\lambda)$

$n$

176

合, 全単射になっていることに注意する. よって, 標準盤 $T$ に対しては以下に $\lambda=(4,2,1)\vdash 7$ に対し, これらの例をあげておく$T^{-1}$:Young diagramが意味を持つ.

standard tableautableau

図 1: Yound 図形と盤

次に Robinson-Schensted 対応を記述する際に欠かせない ‘挿入 (insertion)’ という概念を説明する. $T$ は Young 図形 $Y=Y(\lambda)$ 上の盤とし, は $T$ にはまだ書かれていない正整数とする. このとき $T$ にを挿入するとは, 以下のようにしてサイズの–つ大きい盤 $‘ Tarrow a$ ’を構成する手続きのことをいう
$a$

$a$

:

$\bullet$$\bullet$

まず $\phiarrow a$ は盤回と定義する.の–行目は, $T$ の–行目においてそこに書かれている数字で より大きいもののうち–番左にあるもの を見つけ, それをと交換したものとする.

$Tarrow a$

$a$

$b$

$\bullet$$a$

次に $Tarrow a$ の二行目以降は, $T$ の二行目以降のなす盤になるとする.

$\overline{\mathrm{e}}-\zeta$$b$を挿入して得られる、盤より, 回侠 $W=(w(\perp)w(\Delta)\cdots w(n))\in W$ t-X 丁し -(. 保準盛 $F=P(w)\not\subset$$P(w)=((\cdots((\phiarrow w(1))arrow w(2))\cdotsarrow w(n-1))arrow w(n)$として定義する. すなわち, まず $P_{1}:=\phiarrow w(1)$ とおき, $k>1$ に対しては$:–$. $P_{k-1}arrow$の$w(k)$ とおく. そして $P(w):=$ 鑑と定義する. これを-symbol と呼ぶ. P-symbol$P_{k}$$w$$\mathrm{P}$

177

:

$\phi$$P$:$\phi$$Q$

図 2: P-symbol and Q-symbol$P(w)$は, その構成方法から標準盤となることに注意する. $P(w)$ が乗っている分割をとおく. -方, もう一つの標準盤 $Q=Q(w)$ は $w$ の -symbol と呼ばれ, $P(w)$ を構成する際にYoung 図形が からまで成長していく様子を記述したものである. すなわち Young 図のハコ $P_{k}\backslash P_{k-1}(k=1,2, \ldots n)$ にそれぞれ形を書き込んだものが -symbol $Q(w)$である. 図 2. にその–連の操作の例を $w=(31542)\in$ 亀の場合に挙げておく.
$\lambda$$\mathrm{Q}$$\lambda$$\phi$$Y(\lambda)$$k$$\mathrm{Q}$次に逆の操作 $RS^{-1}$ について触れておく. 基本的には上の操作の逆をたどれば良いのであるが, 後の都合上幾つか必要な記号も出てくるので, ぃささかくどくなるのを承知で論じておくことにする. 以下 Young 図形のハコ の座標を $(i(c), i(c))$ で表すことにする.
をの分割とし, $P,$ をともに STabの元とする. Young 図形 $Y=Y(\lambda)$ のハコ$(k=1, \ldots, n)$ を $\rho_{k}=Q^{-}1(k)$ により定義する. つまり,でが書き込まれている Y、のハコがである. そこでまず $k=n$ の場合に, Young 図形 $Y$ のハコ $\rho_{n}^{(k)}k=1,2,$を次のように帰納的に定義する :$c$$\lambda$

$Q$

$n$

$(\lambda)$$\rho_{k}$

$Q$

$k$

$\rho_{k}\in Y$$\ldots,$$\bullet\rho_{n}^{(1)}:=\rho n$$\bullet$’$k>1$ に対しては,る$P$$i(\rho_{n})$の数$P(\rho_{n}^{(k)})$$\rho_{n}^{(k)}$は $Y$ の $i(\rho_{n}^{()}-1)k-1$ 行目にあるハコで, そこに書き込まれていは $P(\rho_{n}^{(1)}k-)$する.

より小さいもののうち最大のものである, として定義

そして,とおく. また, $Y_{n}=Y,$ $P_{n}=P,$ $Q_{n}=Q$ とおく.
次に $k<n$ に対して Young 図形臨と, その上の盤,と琉のハコ$d_{n}:=\rho_{n^{i}}^{\langle(\rho))}n$$P_{k}$

うに帰納的に定義する :$\bullet T_{k}=\tau_{k1}+\backslash \rho k+1$$\bullet$$Q_{k}=Q_{k}+1|T_{k}$$P_{k}$

は$T_{k}$$d_{k}$

を以下のよ.

: $T_{k}arrow\{1,2, \ldots, k\}$ , すなわちの数字ごと取り去ってえられる$\bullet$$Q_{k}$

上の盤で$T_{k}$上の盤.

$Q_{k+1}$

から $k+1$ の書いてあるハコをそ178

1. $P_{k}--P_{k+}1$ on
2.

$T_{k}\backslash \{\rho_{k1}^{(1)}+’\ldots, \rho_{k+}^{(i(\rho k+}1\}1))$$P_{k}(\rho_{k+1}^{(t)})=P_{k+}1(\rho_{k}^{(-}+1)t1)$, for $t=2,$$\ldots,$.
$i(\rho_{k1}+)$を満たすもの.
$\bullet d_{k}:=\rho^{(i}k(\rho k))$.

こうして, $Q_{k}(k=n, n-1, \ldots, 1)$ を構或していくことが, $RS$ の逆操作になっており, かつ $w(P, Q):=(P_{1}(d_{1}), \ldots, P(nd_{n}))\in S_{n}$ が $w(P, Q)=RS^{-1}(P, Q)$ となっている
ことをみるのは既出の $w=$ (31542) の図を逆にたどれば容易であろう. しかしご覧のとおり, その対応自体はあまり自明なものではない. 次の節では主結果すなわち, あたえられたがどのような条件を満たせば, 対応する $w=Rs-1(P, Q)$ を得$P_{k}$$(P. ’ Q)\in \mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)\cross \mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)$

るための手続きが如何なる簡明さを得るかを述べる.

3

主結果を正整数とし,まず, 主結果を述べるために必要な概念を定義しておく.
を表す. また,をにより, の共役 (conjugate)の分割とする.
を次のように定義
この $T$ に対して$T$ は Young 図形 $Y=Y(\lambda)$ 上の盤とする.
, 及び$\lambda=(\lambda_{1}, \ldots, \lambda_{d})$$n$$([\mathrm{M}], \mathrm{p}.2)$$\lambda$$\lambda’=(\lambda_{1}’, \lambda_{2}’, \ldots)$$n$$\check{T}$する$\tilde{T}$:$\check{T}(i,j)=T(\lambda_{j}’-i+1,j)$

for $(i,j)\in Y$$\tilde{\tau}(i,j)=T(i-\lambda_{1^{+\lambda_{j},j)}}’’(1\leq i\leq d, 1\leq i\leq\lambda_{d-i+1})$

は $T$ に書き込まれている数字を, 各列ごとを上下にひつくり返して得られる $Y$
すなわち,は $T$ を列ごとに切り離し,上の盤である. これに対しては, もはや $Y$ 上の盤ではない.
それらの底辺をそろえて再びあわせて得られる ‘盤’ である.
主結果を述べる.
$\check{T}$$\tilde{T}$$\tilde{T}$

定義 1
対し,$(P, Q)\in \mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)\cross \mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)$

に対して, \Phi \in & を次で定義する$\check{w}(k):=P(\check{Q}^{-1}(k))$

つまり,対応させる$\check{w}$$n$は$k$を $‘ Q$ において$k$

: 各 $k=1,$$\ldots,$

$n$に

.

が書かれている $Y$ のハコ’ に書かれている $P$ の数字を次対称群の元である.

を正整数, は の分割, $Y$ はその Young 図形, $P$ と $Q$ は共に $Y$ 上の標定理 2準盤とする. このとき, 次の 1,2,3 は同値$([\mathrm{M}\mathrm{o}])n$$\lambda$

$n$:

179

1. 各 $k=1,2,$$\ldots,$に対して, $j(\rho_{k})=_{i}(d_{k})$ . すなわち, $Y$ のハコ$n$$\rho_{k}$と$d_{k}$は$\mathrm{Y}$において同じ列に属する.

2. 各 $k=1,2,$$\ldots,$$n$に対して, $j(\rho_{k})(r)=j(\rho_{k}(r+1))$ が任意の $r=1,2,$$\ldots,$$i(\rho k)-1$に対して成り立つ.

3. $\check{w}(P, Q)=w(P, Q)(=RS^{-1}(P, Q))$ .

$T$$\check{T}$$\tilde{T}$図 3:$\check{T}$and$\tilde{T}$$l|\ulcorner^{---}11^{-3}\ulcorner 3^{-\urcorner}|_{arrow 1|4^{-}}\mathrm{I}\vdash--+\ulcorner--\urcorner 1|--\urcorner--\lrcorner||_{arrow^{1}}1\ulcorner^{-}-\vdash--$$P=\vdash-- \mathfrak{l}^{--}l\vdash 2\square |14$$||211$$\phi$$\llcorner_{--}\lrcorner||5||$$15|\llcorner_{--}\lrcorner||$$P=\vdash--+-|l\ulcorner^{-}1^{-_{\tau_{3\mathrm{t}}}}1^{-}|-\urcorner-\dashv|_{arrow^{1}1}|5r--\urcorner^{-}||-- 3\iotaarrow^{\mathrm{I}^{--}}\}\urcorner|2\ulcorner 1|3^{-}\urcorner^{-}|-\urcorner \mathrm{t}1-arrow$$\phi$$41–\lrcorner--\dashv|$$\mathrm{t}|2||41|$

図 4: $w(P, Q)$ and $\tilde{w}(P, Q)$の叙述中, 各琉でが書かれているハコ’ をとし, その後の $P$ の情報を用いた–連の操作で臨から追い出されるハコをとしたのを思い出して頂きたい.
$P$
このこととが標準盤であることから, 条件 1. と条件 2. の同値性は理解できる. その他に関しては図 4. に挙げた実例をもって, その雰囲気をつかむ足しにして頂ければ幸いである.
$RS^{-1}$$‘ Q_{k}$

において

$k$

$\rho_{k}$$d_{k}$

1 3

1 3

この例では $n=.5,$ $P=2$$4,$ $Q=2$

54$5$ととってある.

180

ここで–つ注意を促しておきたいのは, この定理だけでは必ずしも $w(P, Q)=RS-1(P, Q)$は $P,$を $-$ 目で得るのは難しいことである. たしかに,を見ただけで計算出来るのであるが, 定理があたえるその同値条件は実際に Robinson-Schensted 対応を実行してみないと判定できないのである. よって, 実際上は次に述べる系がその役割を果たすことになる.
$Q$$\check{w}(P_{)}Q)$

系3を分割とし, $P$ と $Q$ は共に 上の標準盤とする. このとき, もし‘標準盤であれば, $w(P, Q)=\check{w}(P_{)}Q)$ が成り立つ.
$\lambda$$\lambda$$\tilde{P}$あるいは$\tilde{Q}$がやはすでに Young 図形上の盤ではないことである. よっ
ここで注意が必要なのはて, それらが ‘標準盤であるとはどういうことかとの疑問が生じるが, それは標準盤の定義と同様に P あるいはに書かれている数字が, 左から右に, かつ上から下に増大していることと定義する.
系の証明に関してであるが, が標準盤であれば定理の条件 1. あるいは条件 2. が成立することは, 比較的見やすいと思う. -方,が標準盤の場合であるが, その場合は次の補題と ‘Sch\"utzenberger の定理’$\tilde{P}$$\tilde{Q}$$\tilde{Q}$$\tilde{P}$$\tilde{Q}$$w(Q, P)=w(P, Q)^{-}1$ , for any $P,$

$Q\in \mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)$から従う.

補題 4 任意の $P,$

実際,$\tilde{Q}$$Q\in \mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)$に対して $\psi(Q, P)=\check{w}(P, Q)^{-}1$が標準盤のとき,$\check{w}(P, Q)$$=$$\check{w}(Q, P)^{-1}$$=$$w(Q, P)^{-1}$$=$$w(P, Q)$となる.

次の系は系 3. より直ちに従う.
系5$Y(\lambda)$4

補足
以上,が長方形のとき, すなわち$\lambda_{1}=\lambda_{2}=\cdots$のとき, $w(P, Q)=\check{w}(P, Q)$ .

がある条件を満たせば, それらをそれぞれ P-symbol,Q-symbol として持つ対称群の元の構成が簡略化されることをみてきた. 主定理はそのための同値条件を与えはしたが実際の役には立たず, むしろその系 (系. 3) が事実上の判定法を与えるのであった. しかしそれは十分条件の形で述べられている. そして実際, その逆は成立$(P, Q)\in \mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)\mathrm{x}\mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda)$

181

1 3
しない. 反例は $n=4$ からでてくる. この場合, $P=Q=2$
とおくと,4$\tilde{P}$および$\tilde{Q}$が共に標準盤ではないのにが成立している. さらに, $n=5$ の場合にはそのような対は九つ存在する.
また, 我々は本稿においてとなるための条件を, の -symbol と -symbol を用いて記述してきたが, これを $w=(w_{1}, w_{2}, \ldots, w_{n})$ のみを用いて直接記述することに興味がもたれる. これに成功すれば Robinson-Schensted 対応と, vexillary permutation や dominantpermutation との関連を明らかにすることが出来るからである. 現在, 著者はこの問題に関して部分的な解決を得たが, まだ完全な結論には達していない.
$w=\check{w}$$w=\check{w}$$w$$\mathrm{P}$$\mathrm{Q}$

参考文献
[I]

岩堀長慶, 対称群と –般線形群の表現論, 岩波講座基礎数学, 岩波書店.

[JK] G. James and A. Kerber, The Representation Theory of the Symmetric Group, Encyclopedia of Math., vol. 16, Addison-Wesley, 1981.
[M]

I. G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edition, Oxford
University Press, Oxford, 1995.

[Mo] H. Morita, “On the Robinson-Schensted correspondence”, preprint.
[R]

G. B. Robinson,(1938), 745-760.

[S]

C. Schensted, “Longest increasing and decreasing subsequence”, Canad. J. Math. 13(1961), 179-191.

[T]

寺田至, “Young tableau をめぐって,の幾何と表現論 1, (flag variety と RobinsonSchensted 対応)”, 数理解析研究所講究録 670, p. 163-187.

$‘(\mathrm{O}\mathrm{n}$the representations of the symmetric group”, Amer. J. Math. 60$\mathrm{G}\mathrm{L}$