数理解析研究所講究録
第 1722 巻 2010 年 31-37

31

A probabilistic algorithm which generates
standard tableaux of a generalized Young diagram
KENTO NAKADASHUJI OKAMURAJOINT WORK WITH

1. 背景
本稿の主たる対象である generalized Young diagram は 1991 年，J. B. Carrell の論文[1] の中にはじめて現れる．
論文 [1] によれば D. Peterson は，Kac-Moody Lie 代数の Weyl 群の minuscule 元 $w$の reduced decomposition (最短表示) の総数が:

#Red

(1.1)

$(w)= \frac{f(w)!}{\prod_{\beta\in\Phi(w)}ht(\beta)}$,となることを証明したとされる．ここで Red $(w)$ は の reduced decomposition の集
はの inversion set, ht
は の height である．
合， は の length,の一方，よく知られているように，Young diagram
standard tableau の総数は :$w$$\ell(w)$$w$$\Phi(w)$$w$$(\beta)$$\beta$$Y$(1.2)となる．ここで STab $(Y)$ は$\#STab(Y)=\frac{\# Y!}{\Pi_{v\in Y}h_{v}}$$Y$,の standard tableau の集合， は$h_{v}$$v$の hook length である．

式 (1.1) と (12) の類似性は誰の目にも明白で，$\Phi(w) Y$

Red $(w)$ STab $(Y)$$l(w)=\#\Phi(w)\#Y$

ht $(\beta)(\beta\in\Phi(w)) h_{v}(v\in Y)$という関係が見てとれる．この関係を以って，我々は rmiinuscule 元を generalized Young diagram と呼びたい．

$w$の inversion set$\Phi(w)$C.Greene, A.Nijenhuis, HSWilf は論文 [3] で，Young diagram のすべての standard
tableau を等確率に生成する random walk に基づくアルゴリズムを考案した (第 3 節参
照 . 特にこのアルゴリズムから，Young diagram の hook length formula(1.2) の証明が得られる．また，B. E. Sagan は論文 [10] で [3] の方法を shifted Young diagram の場合に適用し，類似の結果を得た (第 4 節参照).
本稿では，generalized Young diagram (ただし，simply-laced であると仮定する) に対して [3] のアルゴリズム (を一般化したもの (第 2 節参照)) が適用できることを解説する．特にこのアルゴリズムから，simply-laced の場合の generalized Young diagram のhook length formula (1.1) の証明が得られる．
$)$

2.

$GNW$-ALGORlTHM の定義

2. 1. graph. GNW-algorithm を定義するために，ここでは分かりやすさのためにグラフを用いる．今後，考えるグラフ $\Gamma=(V;arrow)$ は有向グラフで，以下の性質 (1),(2),(3) を満たすと仮定する:

32(1)(2)(3)$\Gamma$$\Gamma$$\Gamma$$\# V<\infty)$ .
は有限グラフ すなわち，は単純グラフ (すなわち，多重辺をもたない).
は cycle を部分グラフに含まない (特に loop も含まない).
$($$Y$ ’

FIGURB 2.1. cycle and loop

Remark 1. 本稿を通じて $d:=\# V$ とおく．

Definition 1 頂点$v\in V$に対して，集合$H_{\Gamma}(v)^{+}(\subseteq\Gamma)$

を次で定める:$H_{\Gamma}(v)^{+};=\{u\in\Gamma|varrow u\}$集合 Hrの strict hook と呼ぶ．

$(v)^{+}$

を$v$

Definition 2.

$d$$:=\# V$$(V; arrow)$

とおく．全単射$L$の standard tableau と呼ばれる:: $\{1, \cdots ,d\}\Gamma$ は，次の条件を満たすとき$L(k)arrow L(l)\Rightarrow k>l$,$\Gamma=(V;arrow)$.

$k,$ $l\in\{1,\cdots,d\}$.の standard tableaux 全体のなす集合を STab $(V; arrow)$ と書く．

与えられたグラフ $\Gamma=(V;arrow)$ に対して，以下のアルゴリズム ([3] への敬意を込めて を に対する GNW-algorithm と呼びたい:$)$$\Gamma$.
GNWI. Set $i:=0$ and set
GNW2. (Now has $d-i$ nodes.) Set $j:=1$ and pick a node$\Gamma_{0}$$:=\Gamma$$\Gamma_{i}$$v_{1}\in\Gamma_{i}$$1/(d-i)$ .

GNW3. If$\#H_{\Gamma_{l}}(\mathcal{V}j)^{+}\neq 0$, pick a node$\mathcal{V}j+1\in H_{\Gamma_{j}}(\mathcal{V}j)^{+}$

with the probability

with the probability$1/\#H_{\Gamma},$$(\mathcal{V}j)^{+}$. If

not, go to GNW5.
GNW4. Set $j:=j+1$ and retum to GNW3.

GNW5. Now$($$v_{j}$$\#H_{\Gamma_{i}}(\mathcal{V}j)^{+}=0.)$

ffom$\Gamma_{i}$Set $L(i+1)$$:=\mathcal{V}j$and set$\Gamma_{i+1}$$:=\Gamma_{i}\backslash \mathcal{V}j$(the graph deleted).

GNW6. Set $i:=i+1$ . If $i<d$, retum to GNW2; if $i=d$, terminate.

この確率的アルゴリズムは，再帰的にび，結果として， の頂点の列$v_{i+1}\in\nabla(\Gamma_{i})$s.t. Hr; $(v_{i+1})^{+}=$ のを確率的に選を確率的に生成する．結果としての頂点の列が生成される確率をと書く．この はアルゴリズムの定義から の standard tableau になる．
言い換えれば，このアルゴリズムは，有限集合 STab の上に確率分布 ProbrO を与える．無論，一般の では，この確率分布が一様分布になることは到底期待できないが，本研究の主結果は，D. Peterson, R. A. Proctor の意味の一般化された Young diagram か$L=(v_{1}, v_{2}, \cdots, v_{d})$$\Gamma$$L=(v_{1}, v_{2}, \cdots, v_{d})$$\Gamma$$Prob_{\Gamma}(L)$$L$$\Gamma$$(\Gamma)$$\Gamma$ら得られるグラフにおいては，この確率分布が一様分布になることを主張する．
主結果を述べる前に，本研究の先行研究として，Young diagram の場合と shifted
Young diagram の場合を述べる．

33
3. YOUNG DlAGRAM の場合

本節では，Young diagram を$N\cross N$

hook は次のように定義される．

Definition 3.

$Y$

次で定義する:の部分集合として表しておく．Young diagram のを Young diagram とする．
$v=(i,])\in Y$ とする． の部分集合 $H(v)$ を$Y$$H_{Y}(v):=\{(i’,j’)\in Y|i=i’$$H_{Y}(v)$を$v$

and $j\leq j’$”or$i\leq i’$and $j=f$”$\}$.の hook と呼ぶ．

例えば，Figure 3.1 の網掛の部分が hook である．

FIGURE 3.1. hook at and$v$$u$

頂点$v,$$u\in Y$

に対して，$varrow u$

グラフとみなせる．
このとき，次が成り立つ．

を $u\in H_{Y}(v)$ and $u\neq v$ で定義すると，$\Gamma=(Y;arrow)$ はTheorem 3.1 (C. Greene, A. Nijenhuis, H. S. Wilf [3]).
偉 $Y=d$ とする).

このとき，graphtabuleau $(vl, \cdots , v_{d})\in$ STab(3.1)$(\Gamma)$$\Gamma=(Y;arrow)$$Y$

を Young diagram とする

における GNW-algorithm は standard

を．

$Prob_{\Gamma}(v_{1}, \cdots, v_{d})=\frac{\prod_{v\in Y}\#H_{Y}(v)}{d!}$で確率的に生成する．

Corollary 3.2.

$Prob_{\Gamma}($は一様分布である．

Proof. (3.1) の右辺は standard tableau の選び方に依存していないから．
$\square$Corollary 3.3.
$\#STab(\Gamma)=\frac{d!}{\prod_{v\epsilon Y}\#H_{Y}(v)}$Proof. Corollary 3.2 から従う.
$\square$Remark 2.

もちろん，これは J. S. Frame, G. de B. Robinson, R. M. Thrall [2] によってよく知られた Young diagram の standard tableaux の総数についてのフック公式である．
論文 [3] は Young diagram のフック公式の別証明を与えている．

Remark 3. G-N-W の論文 [3] ではグラフの言葉でアルゴリズムを記述してるわけではないが，ここでは他の図形の場合も記述しやすくするためにグラフの言葉で記述した．

34
4.

$SH\mathbb{F}rED$YOUG DlAGRAM の場合

本節では，shiRed Young diagram を$\{(i,j)\in N\cross N|i\leq i\}$の部分集合として表しておく．shified Young diagram の hook は次のように定義される．

Definition 4.
$H_{S}(v)$$S$$S$ の部分集合
を shifted Young diagram とする．
$v=(i,])\in S$ とする．

を次で定義する:$H_{S}(v):=\{(i’,j’)\in S|i=i’$$H_{S}(v)$をand $j\leq j’$ or”$i\leq i’$and $j=f$ or $j+1=i’$””$\}$.の hook (あるいは bar) と呼ぶ．

$v$

例えば，Figure 4.1 の網掛の部分が hook である．

FIGURE 4.1. $u,$$v$と $w$ における hook (bar)$\Gamma=(S;arrow)$ は
頂点 $u\in S$ に対して，$varrow u$ を $u\in Hs(v)$ and $u\neq v$ で定義すると，グラフとみなせる．
$v,$

このとき，次が成り立つ．

Theorem 4.1 (B. E. Sagan [10]). を shifted YOung dtagram とする $(\# S=d$ とする . このとき，graph $\Gamma=(S;arrow)$ における GNW-algorithm は standard tabuleou$S$$)$$(v_{1}, \cdots, v_{d})\in$$STab(\Gamma)$

を．
$\cdot$(4.1)$Prob_{\Gamma}(v_{1}, \cdots, v_{d})=\frac{\Pi_{v\epsilon S}\#H_{S}(v)}{d!}$で確率的に生成する．

Corollary 4.2.

$Prob_{\Gamma}($は一様分布である．

Proof. (4.1) の右辺は standard tabuleau の選び方に依存していないから口Corollary 4.3.
$\#STab(\Gamma)=\frac{d!}{\prod_{\mathcal{V}\epsilon S}\#H_{S}(v)}$Proof Corollary 4.2 から従う.
口Remark 4. もちろん，これは R. M. Thrall [11] によってよく知られた shifted Youngdiagram の standard tableaux の総数についてのフック公式である．論文 [10] は shifted
Young diagram のフック公式の別証明を与えている．
Remark 5. 古典的な確率論においては，全事象の個数が分かっていて，その上に一様分布があるのであれば，各根元事象が起こる確率は，1/(全事象) であると考える．しかし，[3] や [10] ではまったく逆の状況になっている．つまり，全事象の個数は分からな
いが，とにかくその上に一様分布があり，各根元事象がおこる確率が計算できる．したがって全事象の個数は，1/(各根元事象がおこる確率) であると主張しているのである．

35
5. GENERALIZED YOUNG DlAGRAM の定義

5.1. Kac-Moody Lie algebra からの準備．generalized Young diagram を定義するために，simply-laced Kac-Moody Lie 代数のルート系を用いる (例えば $[4][5]$ を参照).
: simply-laced Kac-Moody Lie algebra の Cartan matrix.
り : Cartan subalgebra over ,り : りの dual space,:り り: canonical bilinear form.
$A=(a_{i,j})_{l.j\in I}$$\mathfrak{g}$$\mathbb{R}$$*$$\langle,$$*\cross$$\rangle$$arrow \mathbb{R}$り$\Pi:=\{\alpha_{i}|i\in I\}\subset$:simple roots の集合，$*$

り:simple coroots の集合，$\Pi^{\vee}:=\{\alpha_{i}^{\vee}|i\in I\}\subset$

such that$\lambda\in$$\langle\alpha j,$.

$\alpha_{i}^{\vee}\rangle=a_{i,j}$

けは次を満たすとき integral weight と呼ばれる:$\alpha_{i}^{\vee}\rangle\in \mathbb{Z}$$\langle\lambda,$,$i\in I$.

Integral weights の全体は と書かれる．
各 $i\in I$ に対して，si GL(り ) を:
$P$

$*$

$\in$

$s_{i}:\lambda\mapsto\lambda-\langle\lambda,$$\alpha_{i}^{\vee}\rangle\alpha_{i}$,,$\lambda\in \text{り^{}*}$で定義する．
$W$$\Phi$$\Phi^{\vee}$$\vee:$$\Phi_{+}$

各と$\beta\in\Phi$$\Phi_{-}$: Weyl group$:=W\Pi$ : real root system: real coroot system$:=\langle s_{i}|i\in I\rangle$$:=W\Pi^{\vee}$$\Phi\ni\beta\mapsto\beta^{\vee}\in\Phi^{\vee}:$the dual of real roots

で， の positive roots と negative roots を表す．
$\Phi$に対して，$s_{\beta}\in W$を次で定義する:$s_{\beta}(\lambda)=\lambda-\langle\lambda,$$\beta^{\vee}\rangle\beta$,$*$$\lambda\in$り ’

したがって，りには次で act する:$s_{\beta}(h)=h-(\beta,$各 $w\in W$ に対して，集合$\Phi(w)(\subseteq\Phi_{+})$$h\rangle\beta^{\vee},$$h\in$り．

を (inversion set of $w$ と呼ばれる) 次で定義する:$\Phi(w):=\{\gamma\in\Phi_{+}|w^{-1}(\gamma)<0\}$.

5.2. Generalized Young diagram と，その hook.

Definition 5.

$\lambda\in P$

が pre-dominant であるとは，次を満たすことである:$\langle\lambda,\beta^{\vee}\rangle\geq-1$

Pre-dominant integral weights のなす集合をDefinition 6.
呼ぶ:$\lambda\in P\geq-l$,$\beta\in\Phi_{+}$$P\geq-1$.

で表す．

に対して，次で定義される集合$D(\lambda)\subseteq\Phi_{+}$

が finite であるとは，weights のなす集合を$\#D(\lambda)<\infty$$P_{\geq-1}^{fin}$$\lambda$の diagram と.
を満たすことである．Finite pre-dominant integral$D(\lambda):=\{\beta\in\Phi_{+}|\langle\lambda,\beta^{\vee}\rangle=-1\}$$\lambda$

をと書く．

36
Definition 7([6]).

$\lambda\in P_{\geq-1}^{fin},\beta\in D(\lambda)$とする．このとき，集合$H_{\lambda}\phi):=D(\lambda)\cap\Phi(s_{\beta})$集合$H_{\lambda}\phi)$を$\beta$$\lambda\in P_{\geq-1}^{fin},$$\gamma\in H_{\lambda}(\beta)\backslash \{\beta\}$$\#H_{\lambda}\omega)=$ht$(\beta)$$\beta\in D(\lambda)$とする．このとき，次が成り立つ．とすると，.

$\gamma<\beta$

Lemma 5. 1 により，$\beta,\gamma\in D(\lambda)$

で，$\psi,$$\gamma^{\vee}\rangle=1$$D(\lambda)$.

に対して，$\betaarrow\gamma:\Leftrightarrow\gamma\in H_{\lambda}\phi)$で.

における hook と呼ぶ．

Lemma 5.1 ([6]).
(1)(2)) を次で定める:$H_{\lambda}\phi$

and$\gamma\neq\beta$をグラフとみなすことができる．

53. 主定理．
Theorem 5.2 (N-Okamura [7], Okamura [8]).とすると，GNW-algorithm は を確率:$\lambda\in P_{\geq-1}^{fin}$とする．このとき， STab
$L\in$$(D(\lambda))$

$L$

(5.1)

$Prob_{D(\lambda)}(L)=\frac{\prod_{\beta\epsilon D(\lambda)}\#H_{\lambda}(\beta)}{d!}$.

で生成する．

Corollary 5.3.

$Prob_{D(\lambda)}($は一様分布である．

Proof (5.1) の右辺は standard tableau の選び方に依存していないから．ロ
Corollary 5.4.
$\#STab(D(\lambda))=\frac{d!}{\prod_{\beta\epsilon D(\lambda)}\#H_{\lambda}\varphi)}$.

Proof. Corollaly 5.3 から従う．

口Remark 6. Theorem 5.2(と本質的に同値な定理) は最初，岡村修志によって証明された[8](formulation がまったく異なる). [8] における証明は，R. A. Proctor による分類 [9]に基づく case-by-case argument と，長時間の計算機による計算でなされた．一方，[7]では証明方法を大幅に改良し，colored hook fommla[6] を用いた統一的な証明になっている．

5.4. minuscule 元との関係．最後に，主結果と Peterson のフック公式 (1. 1) の関係について簡単に述べておきたい．
を dominant integral weight とするとき，$w\in W$ が-minuscule 元であるとは，のある reduced decomposition$(w)$
Redに対して，$\Lambda\in P$$w$$\Lambda$$(s_{i_{1}}, \cdots, s_{i_{d}})\in$(5.2)$\langle s_{i_{k+I}}\cdots s_{i_{d}}(\Lambda),$$\alpha_{i_{k}}^{\vee}\rangle=1$が成り立つことである．このとき，任意の,$k=1,$ $\cdots,$ $d$$(s_{i_{1}}, \cdots, s_{i_{d}})\in$

Red $(w)$ に対して (5.2) が成り立つことが分かる [6].

また，$w\in W$ を$\Delta$-minusucule 元とすると，$w(\Lambda)\in P_{\geq-1}^{f\ln}$であることが分かる．さらに，この対応の下で，Red $(w)$ と STab$\lambda=w(\Lambda)$となり，この対応は全単射$\Phi(w)=D(\lambda)$ となる [6].とおけば，は適切に同一視され，Corollary 5.4 は (1.1)$(D(\lambda))$の (simply-laced の場合の) 証明を与える．

37
REFERENCES[1] J. B. Carrell, Vectorfields, flag varieties, and Schubert calculus, Proc. Hyderabad Conference on Algebraic
Groups (ed. S. Ramanan), Manoj Prakashan, Madras, 1991.
[2] J. S. Frame, G. de B. Robinson, and R. M. Thrall, The hook graphs ofsymmetric group, Canad $J$ Math. 6$(1954),316-325$.

[3] C. Greene, A. Nijenhuis, and H. S. Wilf, A probabilistic proofofaformulafor the number of Young tableauxof given shape, Adv. in Math. 31 (1979), 104-109.
[4] V. G. Kac, “Infinite Dimentional Lie Algebras,” Cambridge Univ. Press, Cambridge, UK, 1990.
[5] R. V. Moody and A. Pianzola, “Lie Algebras With Triangular Decompositions,” Canadian Mathematical$0$Society Series of Monograph and Advanced Text, 1995.
[6] K. Nakada, Colored hookformulafor generalized Young diogram, Osaka J. of Math. Vol. 54 No. 4 (2008),$0$1085-1120.

[7] K. Nakada, and S. Okamura, Unifom generation of standard tableaux of a generalized Young diagram,preprint.

[S] S. Okamura, An algorithm which generates random standard tableau on a generalized Young diagram (inJapanese), master thesis, Osaka university, 2003.
[9] R. A. Proctor, Dynkin diagram classification of -minuscule Bruhat lattices and of d-complete posets, J.
Algebraic Combin. 9 (1999), 61-94.
[10] B. E. Sagan, On selecting a random shifed Young tableaux, J. Algorithm 1 (1980), 213-234.
[11] R. M. Thrall, combinatorial problem, Mich. Math. $J1$ (1952), 81-88.
$0$

$s$

$\lambda$$\Lambda$

WAKKANAI HOKUSEI GAKUEN UNIVERSITY, FACULIY OF INTEGRATED MEDIA.
E-mail address: nakada@wakhok.ac.jp