僕の頭の備考欄

表現論的組合せ論という分野をちょこっと勉強したのでそのまとめ(というか例のごとくメモ)です. 自然数の分割とヤング図形の対応, n次対称群と標準盤とのRS対応, ヤング図形の極限形状までを概観します.

分割とYoung図形

分割

定義(分割)

自然数 $n$ について $n \ge \lambda _1 \ge \lambda _2 \ge \cdots \ge \lambda _l \ge 0$ となる自然数 $\lambda _1, \lambda _2, \cdots , \lambda _l$ を用いて $n = \lambda _1 + \lambda _2 + \cdots +\lambda _l$ と表すことを $n$ の分割といい, $(\lambda _1 , \lambda _2 , \cdots ,\lambda _l)$ と書く.

$n$ の分割の全体の集合のことを $\mathcal{P}(n)$ と書く. すなわち

\begin{align} \mathcal{P}(n) = \left \{ (\lambda _1 , \lambda _2 , \cdots ,\lambda _l) \ ; \sum _{i=1}^{l} \lambda _i = n , \ (\lambda _1 \ge \lambda _2 \ge \cdots \ge \lambda _l \ge 0)\right \} \end{align}

である.

$\mathcal{P}(n)$ の元の数, すなわち $n$ の分割の総数を分割数といい, $p(n)$ で表す.

例) $n=4$ のとき.

$\mathcal{P}(4)$ の元, すなわち自然数 $4$ の分割をすべて書くと $(4), (3,1), (2,2), (2, 1, 1), (1, 1, 1, 1)$ であり, $p(4) = 5$ .

分割数の母関数表示

$1$ 未満の $x$ についての形式的べき級数

\begin{align} \frac{1}{1-x^k} = 1 + x^k + x^{2k} + x^{3k} + \cdots \ (k=1,2,3,\ldots) \end{align}

を用いて分割数 $p(n)$ の母関数表示を与えられることが知られています.

定理(分割数の母関数表示)

形式的に $p(0)=1$ とする. このとき,

\begin{align} \prod _{k=1} ^{\infty} \frac{1}{1-x^k} = \sum _{n=0} ^{\infty} p(n) x^n \end{align}

つまり左辺をn次の項まで級数展開すれば, そのn次の項の係数が分割数と対応しているということです.

Young図形(ヤング図形)

定義(Young図形)

大きさの等しい $n$ 個の正方形(ハコ)を上詰めかつ左詰めに並べたものをサイズ $n$ のYoung図形という.

サイズ $n$ のYoung図形全体を $y(n)$ と書く.

例) $n=4$ のYoung図形を列挙すると以下のようになります.

f:id:shuhoyo:20190215170632p:plain

ここで重要なのはサイズ $n$ のYoung図形について, 各行のハコの数の組が $n$ の分割に対応しているということです.

つまり以下の定理が成り立ちます.

定理

全単射

\begin{align} y(n) & \tilde{\longrightarrow} \mathcal{P}(n) \\ \lambda & \longmapsto (\lambda _1 , \lambda _2 , \cdots ,\lambda _l) \end{align}

が存在する.

サイズ $n$ のYoung図形と自然数 $n$ の分割には一対一対応の関係が成り立つことから, 通常サイズ $n$ のYoung図形の型を自然数 $n$ の分割の書き方で書き表します.

盤(tableau)と標準盤(standard tableau)

定義(盤, 標準盤, 型)

サイズ $n$ のYoung図形のハコの中に $n$ までの自然数を1度ずつ書き入れたものを盤(tableau)という.

このとき盤 $T$ について, 元のYoung図形 $\lambda$ を $T$ の型(shape)という.

また, 盤 $T$ に書き入れた自然数が, 各行ごとに左から右に単調増加でかつ各列ごとに上から下に単調増加となるとき, $T$ を標準盤(standard tableau)という.

Young図形 $\lambda \in \mathcal{P}(n)$ に対して, $\lambda$ を型とする盤全体を $Tab(\lambda)$ と表します. 同様に, $\lambda$ を型とする標準盤全体を $STab(\lambda)$ と表します.

例) 標準盤(n=6)

f:id:shuhoyo:20190223185007p:plain

Young図形上の確率測度

何もない状態からハコを上詰め左詰めで1つずつ並べていき, サイズ $n$ のYoung図形ができた時点で, 今度はハコを1つずつ取り除いていき, 何もない状態に戻す過程を考えます.

例えば $n=3$ としたとき, 以下の6通りの過程が考えられます.

f:id:shuhoyo:20190223151255p:plain — n=3の過程

今の6通りの中では $(2,1)$ のYoung図形が最も多く出現している(4回)ことがわかります.

では一般の $n$ に対してこの過程を行ったとき, サイズ $n$ Young図形のなかでもっとも出現確率が高いものは何かということを考えます. そのためにまずYoung図形上の確率測度を与えなければなりません.

結論だけ言えば, 型が $\lambda$ である標準盤の個数 $d_{\lambda }$ を用いると, 型が $\lambda$ のYoung図形の出現率 $\mathbb{P}^{(n)} (\lambda )$ は以下のように表せることが知られています.

\begin{align} \mathbb{P}_n (\lambda) = \frac{d_{\lambda} ^2}{n!} \end{align}

この確率測度 $\mathbb{P}_n (\lambda)$ はPlancherel測度と言われています.

ちょっと細かい話をするとこの測度は $n$ 次対称群と, 型 $\lambda$ の標準盤同士の直積空間の間に全単射が存在するという事実から導かれます. この全単射をRobinson-Schensted対応(RS対応)といいます.

Robinson-Schensted対応

$n$ 次対称群 $S_n$ と, サイズ $n$ のYoung図形 $\lambda \in \mathcal{P}(n)$ からなる標準盤全体 $STab(\lambda)$ に対して全単射

\begin{align} S_n & \tilde{\longrightarrow} \bigcup _{\lambda \in \mathcal{P}(n)}(STab(\lambda) \times STab(\lambda)) \end{align}

存在する.

この両辺の $\dim$ をとることで $\mathbb{P}_n (\lambda)$ を得ます.

例) $n=4$ のYoung図形の出現率

サイズ4のYoung図形の型は $(4), (3,1), (2,2), (2, 1, 1), (1, 1, 1, 1)$ の5つ. このそれぞれに対して標準盤を列挙してみると以下のようになります.

f:id:shuhoyo:20190223170912p:plain

したがって,

\begin{align} d_{(4)} &= 1\\ d_{(3,1)} &= 3\\ d_{(2,2)} &= 2\\ d_{(2,1,1)} &= 3\\ d_{(1,1,1,1)} &= 1 \end{align}

であり, それぞれの出現率は

\begin{align} \mathbb{P}_4 (4) &= \frac{d_{(4)} ^2}{4!} = \frac{1}{24} \\ \mathbb{P}_4 (3,1) &= \frac{d_{(3,1)} ^2}{4!} = \frac{9}{24}\\ \mathbb{P}_4 (2,2) &= \frac{d_{(2,2)} ^2}{4!} = \frac{4}{24}\\ \mathbb{P}_4 (2,1,1) &= \frac{d_{(2,1,1)} ^2}{4!} = \frac{9}{24}\\ \mathbb{P}_4 (1,1,1,1) &= \frac{d_{(1,1,1,1)} ^2}{4!} = \frac{1}{24} \end{align}

よって, $n=4$ のときは

f:id:shuhoyo:20190223174453p:plain