数理解析研究所講究録
1190 巻 2001 年 82-94

82

On aweight function for trees
和歌山大学教育学部 (Faculty of Education, Wakayama Univ)
有馬功 (Isao Arima), 田川 裕之 (Hiroyuki Tagawa)standard tableau &hook length1

初めに standard tableau の個数が hook length を用いて表せることを紹介する.
以上の整数全体の以下, 自然数全体の集合を , 整数全体の集合を$\mathrm{P}$集合を$\mathrm{N}$$0$$\mathrm{Z},$とする.

Definition 1.1 (partition)に対して$n\in \mathrm{P}$$n$$\lambda=(\lambda_{1}, \lambda_{2,)}\ldots\lambda_{\Gamma})\in \mathrm{P}^{r}$の partition と呼ぶ. 以後,

(i)
(ii)

が$\lambda$$n$が次の条件を満たすとき,の partition であることを$\lambda\vdash n$$\lambda$をで表す.

$\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{r}>0$$\Sigma_{i=1}^{r}\lambda_{i}=n$Definition 1.2 (Young diagram)$\lambda--(\lambda_{1}, \lambda_{2,)}\ldots\lambda)\gamma\vdash n$$n\in \mathrm{P},$べた$n$のとき, 第 行に$i$個の箱からなる図形を shape$\lambda$の$\lambda_{i}$個の箱を左揃えに並Young diagram と呼ぶ,Remark 1.3
Young diagram $k\{(i, j)\in \mathrm{P}^{2}|1\leq i\leq r, 1\leq j\leq\lambda_{i}\}$shapeの 3 つを同–視する.

$\lambda\vdash nk$$\lambda\sigma\supset$

Notation 1.4$\lambda\vdash n$

に対して$\lambda’$を$\lambda$のconjugate とする 1

Example 1.5$\lambda=(3,2)$に対する conjugate I は $\lambda’=(2,2,1)$

Definition 1.6 (tableau)
Young diagram に対して各箱に自然で表数を–つずつ入れたものを tableau と呼び. その集合全体を Tab$(i, j)\in\lambda$ に対してを 行 列の箱に入ってす. また,$n\in \mathrm{P}$,$\lambda\vdash n$

に対して shape$\lambda$の$(\lambda)$$T_{(i,j)}$$T\in \mathrm{T}\mathrm{a}\mathrm{b}(\lambda),$いる数とする.
1i.e.

$\lambda’=(\lambda_{1}’, \lambda_{2k}’\ldots\lambda’),$$\lambda_{i}^{l}:=$it$\{j;i\leq\lambda_{j}\}$

$i$

$j$

83

Definition 1.7 (standard tableau)が次の条件を満たすとき, shapeで表す.の standard tableau と呼び; その集合全体を STab$n\in \mathrm{P},$$\lambda\vdash n$

に対して$\lambda$$T\in \mathrm{T}\mathrm{a}\mathrm{b}(\lambda)$$(\lambda)$$( \mathrm{i} )T_{(i,j)}<T_{(i,j+}1)$

if $(i, j),$ $(i, j+1)\in\lambda$
if $(i, j),$ $(i+1, j)\in\lambda$(ii),$\{T_{(i,j)}|(i,j)\in\lambda\}=\{1,2,\ldots, n\}$(iii)
$T_{(i,\mathrm{j})}<T_{(j)}i+1$

Fact 1.9$n\in \mathrm{P}l\lambda\vdash n,$$\lambda’$

を$\lambda$のconjugate とするとき, $(i, j)\in\lambda$ に対して$h(i, j):=\lambda_{i}+\lambda’-ji-j+1$

とおく 2. このとき次が成立する,$\#^{\mathrm{s}\mathrm{T}\mathrm{a}\mathrm{b}}(\lambda, n)=\frac{n!}{\Pi_{(i,j)\in}\lambda h(i,j)}$

この $h(i, j)$ を $(i, j)$ の hook length(1)と呼ぶ.

Example 1.10
$n=5,$ $m=3,$ $\lambda=(3,2)$ に対する Young tableau に各 $(i, j)$ の hook lengthを書き込むとであり,Factl 9 の (1) 式より$\#^{\mathrm{s}\mathrm{T}\mathrm{a}\mathrm{b}}(\lambda)=\frac{5!}{4\cdot 3\cdot 2\cdot 1\cdot 1}=5$となり Exl 8 の結果と –致していることがわかる.

2i.e. ( , のを起点とする右端、 下端までの箱の数の和である.
$i$

84

2standard tableau と poset
次に standard tableau を poset と見なしたとき standard tableau の個数と poset における linear extension の個数が–致し, linear extension の個数も hook length を用いて表せることを紹介する.

Definition 2.1 (cover)$P$を poset とする 3. $x,$ $y\in P$ に対して; $x<y$ かっ〆 zを満たすとき,$y$$\in P\mathrm{s}.\mathrm{t}$(は $x$ を cover すると呼び\rangle $x<\cdot y$ で表す.

. $x<z<y$.

.

$\cdot$Definition 2.2 (Hasse diagram)$P$を finite poset とする .

$F^{\backslash }$ラフ $G=(V, E)$ が $P$ の Hasse diagram であるとは $V=P,$ $E=\{(x, y)\in P^{2}|x<\cdot y^{\}}$ とし$x<\cdot y\Leftrightarrow \mathrm{I}_{x}^{y}$で表す.

Example 2.3$P=\{\emptyset, \{1\}, \{2\}, \{1,2\}\}$とし,P における順序関係$\leq$を $x\leq y\Leftrightarrow x\subset y$ で定義する.
このとき $P$ の Hasse

diagram はとなる.

Definition 2.4$\lambda=(\lambda_{1)}\lambda 2, \ldots, \lambda)r\vdash n$

に対して$P(\lambda):=\{(i, j)|1\leq i\leq r, 1\leq j\leq\lambda_{i}\}$とおき 4, 順序関係$\leq$

を次で定義する.
$(i, j)\leq(i^{J}, j’)\Leftrightarrow^{\mathrm{d}\mathrm{e}\mathrm{f}}i\geq i’,$3partially ordered set の略

4Remarkl 3 の$\{(i, j);1\leq i\leq r, 1\leq j\leq\lambda_{i}\}$と同じ.

$j\geq j’$

85

ExamDle 2.5Definition 2.6 (linear extension)$P$を poset, $|P|=n$ とする. このとき$L(P):=\{\sigma$: $Parrow$ { $1,2,$$\ldots,$$n^{\}}|x.\leq y\Rightarrow\sigma(x)\leq\sigma(y),.\sigma$: 全単射}

とおき, $L(P)$ の元を $P$ の linear extension と呼ぶ.

Notation 2.7$P=$

とおいたとき, $\sigma\in L(P)$ となっている.

$i....:.’.\cdot,$‘のように表記する.

以下, 簡略化のため

Example 2.8$P=$$L(P)=$$\{$である.

Remark 2.9$\lambda\vdash n$

に対して STab$(\lambda)$と $L(P(\lambda))$ は 1 対 1 に対応 5している. 従って,先の Fact 19 から次の式を得ることが出来る.
$\# L(P(\lambda))=\frac{n!}{\Pi_{(i,j)\in P(}\lambda)h(i,j)}$5linear extension における大小関係を逆にしたものと 1 対 1 になっている.

86

3semi-standard tableau&hook length
次に semi-standard tableau に対して, ある weight による母関数が hooklength を用いて表せることを紹介する.

Definition 3.1 (semi-standard tableau)$n,$ $m\in \mathrm{P},$とする.

$\lambda\vdash n$$T\in \mathrm{T}\mathrm{a}\mathrm{b}(\lambda)$が次の条件を満たすとき shape$\lambda$の semi-standard tableau と呼ぶ.

(i)if(ii) $T_{(i,j)}<T_{(i+1,j)}$ if$T_{(i,\mathrm{j})}\leq T_{(i,j+}1)$$(i,j),$ $(i, j+1)\in\lambda$$(i, j),$ $(i+1, j)\in\lambda$

またSSTab $(\lambda, m):=$ {$T\in \mathrm{T}\mathrm{a}\mathrm{b}(\lambda)|(\mathrm{i}),$$(\mathrm{i}\mathrm{i})$を満たし, $T_{(i,j)}\leq m$ for

とおく.

Notation 3.2$n\in \mathrm{Z}$に対して$[n]:= \frac{1-q^{n}}{1-q}$

とおく,Definition 3.3$n,$ $m\in \mathrm{P},$$T\in \mathrm{S}\mathrm{S}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda, m)$に対して$|T|:= \sum_{\lambda(i,j)\in}\tau_{(i,j)}$

とおき, 次を定義する.
$F( \lambda, m;q):=\sum_{mT\in \mathrm{s}\mathrm{s}\mathrm{T}\mathrm{a}\mathrm{b}(\lambda,)}q^{1}\tau|$

Example 3.4$m$.

$=.\mathrm{q}_{-}\lambda=$[.q$2$-)$\vdash.\mathrm{q}$に “x 汁 1, て$\forall(i,$$j)\in\lambda$}

87

従って
$F((3,2),$ $3;q)$母関数は hook lengtho で表されていることかわかる.
一般に semi-standard tableau の母関数は hook length を用いて, 次のような形で表せることが知られている.

Fact 3.5$n,$ $m\in \mathrm{P},$$\lambda=(\lambda_{1}, \lambda_{2}, \ldots, \lambda)\gamma\vdash n$に対して$F( \lambda, m;q)=q=1\prod_{\lambda}\Sigma_{i}ri\lambda i\frac{[m+j-i]}{[h(i,j)]}(i_{\dot{t}})\in$(2)Problem 3.6
一般の poset に対して, 溶出に semi-standard tableau と同じ様な数の振り方をして母関数を考えたとき, (2) のような形の等式が成立するか ?
この問題をさらに具体的な問題にする前に–般の poset に対して少し定義をする.

4

一般の poset について

Definition 4.1 (hook length formula を持つ poset)$P$を poset, $|P|=n$ とする.

$P$が次の条件を満たすとき hook length for-mula を持つ poset と, ここでは呼ぶことにする.
$\exists h_{P}$:$Parrow \mathrm{P}\mathrm{s}.\mathrm{t}$6hook length は先の Ex 110 を参照. $\# L(P)=\frac{n!}{\Pi_{x\in P}h_{P}(x)}$88Fact 4.2
d-complete poset ?は hook length formula を持つ poset である 7

Definition 4.3
を poset とし, $P$ に対して$P$

とおき,$\mathrm{C}\mathrm{o}\mathrm{v}(P)$$:=\{(_{X}, y)\in P^{2}|\cdot x.<.y\}$${\rm Min}(P)$$:=$$\mathrm{E}\mathrm{L}(P)$$:=\{R:\mathrm{C}\mathrm{o}\mathrm{v}(P)arrow \mathrm{N}\}${ $x\in P|x$ :$P$の極小元}の元を $P$ の edge labehing と呼ぶ.

$\mathrm{E}\mathrm{L}(P)$

Example 4.4

.

. ..

.

$P=$

$=\{(\dot{d}, b), (d, .c), (e, c), (b, a), (c, a)\}$$\iota \mathrm{C}_{0}\mathrm{V}P\sim\ovalbox{\tt\small REJECT}\backslash )$$=\{d, e\}$${\rm Min}(P)$写像$R:\mathrm{C}\mathrm{o}\mathrm{V}(P)arrow \mathrm{N}$を $R(d, b)=2,$ $R(d, c)=0,$ $R(e, C)=1,$ $R$$R(c, a)=1$ とおけば 2$0,$

以下, 簡略化のために$R\in \mathrm{E}\mathrm{L}(P)$$R\in \mathrm{E}\mathrm{L}(P)$となる.

.

.

$(b, a)=\backslash$,を次のように表記する.

$R=$

Definition 4.5 $((P, R)$ -partition)$P$を poset とし,このとき, 写像$\varphi$$R\in \mathrm{E}\mathrm{L}(P)$:$Parrow \mathrm{N}$とする.

が次の条件を満たすとき $(P, R)$ -partition という.
$\varphi(x)-\varphi(y)\geq R(x, y)$

また,$n\in \mathrm{P}$for$\forall(x, y)\in \mathrm{C}\mathrm{o}\mathrm{v}(P)$に対して$A(P, R, n):=$ {$\varphi$: $(P,$$R)-\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}|\varphi(x)\leq n$

とおく.

7tree は d-complete poset のひとつである.

for$\forall x\in P$}

89

Example 4.6$R=$$A$( $P,$ -R, )$3$$=$$\{$$\}$である.

Definition 4.7 (hook edge labeling)$P$を hook length formula を持つ poset,$R\in \mathrm{E}\mathrm{L}(P)$とする,.

$\exists c\in \mathrm{N},$のとき,
但し,$\exists c_{R}$$R$:$.\mathrm{f}_{0}\mathrm{r}n\in \mathrm{N}$$P arrow \mathrm{Z}\mathrm{s}.\mathrm{t}.\sum_{\varphi\in A(P,R,n)}q=|\varphi|cq\prod_{x\in P}\frac{[n+C_{R}(X)]}{[h_{P}(x)]}$を hook edge labeling と呼び, その全体集合を$-|\varphi|:=\Sigma_{x\in P}\varphi(x)$$\mathrm{H}\mathrm{E}\mathrm{L}(P)$で表す.とする ,Example 4.8$[n+j-i+1]$

for$n\in \mathrm{N}$$\varphi\in A(P((3,2))\sum_{R1,n)},q|\varphi|=q^{2}\prod_{3(i,j)\in P((2))},[h_{P(()}3,2)(i, j)]$$\varphi\in A(P((3,2)))R2,)\sum_{n}q|\varphi|=q^{5}(i,j)\in P\square \frac{[n+j-i]}{[h_{P(()}3,2)(i,j)]}((3,2))$

for$n\in \mathrm{N}$となるので $R_{1},$8

は{$R_{1}$である 8.の場合, semi-standard tableau の場合と比べ左辺の分子にずれが生じているのとなっている為-partition における の取り得る値が $1\sim n$ ではなく,$P,$ $R)$である.

$R_{2}\in \mathrm{H}\mathrm{E}\mathrm{L}(P)$,$n$$\mathrm{o}\sim n$90

先ほどの Problem 36 は次の具体的な問題となる.

Problem 4.9
hook length formula を持つ poset に対して hook edge labeling はどのようなものか ?

hook length formula を持つ poset として知られている -complete posetの中の tree について次のように考えた.
$\mathrm{d}$Young tableau に対して hook edge labeling I は と 1 だけで表すことが出来る. そこで tree に対しても同様に出来るだろうと考えた. しかし 出来きないので と 1 だけでなと数を増やし, 実験をおこなった
ところ, 次の実験結果が得られた.
$0$

$0$

$\text{く}2,3,$$\ldots$

Example 4.10$\in \mathrm{E}\mathrm{L}(\mathrm{P})$といりよりに hook lengthw$\mathrm{g}$とおくと用いて表すことが出来た.

この実験結果をもとに ,-般の tree に対するに紹介する.

9tree における hook length は Fact 57 を参照$\mathrm{H}\mathrm{E}\mathrm{L}(P)$がわかったので次

91

tree case

5Definition 5.1 (tree)
poset とする.
が次の条件 (i), (ii), (\"ui) を満たすとき
を finite$P$$P$(i)(ii)(iii)$P$は最大元を持つ.

$P$の Hasse

$P$

$P$

を tree と呼ぶ.

diagram はグラフとして連結である.の Hasse diagram から任意の edge を取り除いたグラフは非連結なグラフである.

Example 5.2
次の (i), (ii) は tree である.

(ii)

(i)

Notation 5.3$P$

を tree とし,$R\in \mathrm{E}\mathrm{L}(P),$$\forall x\in P$$:=\{y\in P|y\leq x\}$$\langle x\rangle$$R_{x}$$:=R|_{\mathrm{c}_{\mathrm{o}\mathrm{V}}}(\langle x\rangle)$に対して次を定義する $1$: subposet of $P$: edge labeling of$\langle x\rangle$

Example 5.4に対して$\langle b\rangle=\{b, d, e\}$$R_{b}=$

Fact 5.5$P$を tree , $|P|=n$ とする.

このとき $h:Parrow \mathrm{P};h(x):=\#\langle x\rangle$ と定義すると$\# L(P)=\frac{n!}{\prod_{x\in P}h(x)}$となる,

従って, tree I は hook length formula を持つ poset であることがわかる.
10$\langle x\rangle$(は $x$ で生成される principle order ideal と呼ばれる.

(3)

92

Example 5.6$P=$である, また, 介 $\pi$ におけ 6hook length を書き込むと従って (3) の等式より:$\# L.(P)-,=..\frac{5!}{5\cdot 3\cdot 1\cdot 1\cdot 1},=8$となり, linear extension の個数と等式から得られた値が–致している,

Definition 5.7$P$

を tree とする. このとき
$C(x):=\{y\in P|y<\cdot x\}$とおく. また,R\in EL(P) に対して写像$z_{R}(x)=\{$$z_{R}$:$Parrow \mathrm{Z}$を次で定義する.

1if $x\in{\rm Min}(P)$$\max\{z_{R}(y)-R(y, x)+1|y\in C(x)\}$ if $x\not\in{\rm Min}(P)$

Example 5.8

93に対して, $z_{R}(d)-R(d, b)+1=-1,$ $z_{R}(e)-R(e, b)+1=-2$ ,$z_{R}(f)-R(f, b)+1=-3$ なので, $z_{R}(b)=-1$ である.
また, に対して, $z_{R}(c)=z_{R}(g)-R(g, c)+1=-4$ , そして, に対して
$z_{R}(g)=1,$

$b$

$-$

$c$

$a$

$z_{R}(b)-R(b, a)+1=-1,$ $z_{R}(C)-R.(C, a)+1=-5$ なので $z_{R}(a)=-1$ となる. 従って$z_{R}=$である.

Theorem 5.9$T$を tree とし,$R\in \mathrm{E}\mathrm{L}(T)$$|\forall x\in T-{\rm Min}(T)$$\exists y_{1},$は次の条件 $(*)$ を満たすとする.

に対して$y_{2,\ldots,y_{\gamma}}\in T\mathrm{s}.\mathrm{t}$$(*)\{$.

$\{y_{1},$$y_{2},$$\ldots,$$y_{r}\mathrm{I}=C(x)$,$R(y_{k}, x)=R(y_{1}, x)+z_{R}(y_{k})-Z_{R}(y_{1})+\Sigma_{i=1}^{k-1}\#\langle yi\rangle$

このとき$x_{0}$.

を $T$ の最大元とすると,$n\in \mathrm{P}$for $k\in\{1, \ldots, r\}$に対して次の式が成立する.

$\varphi\in A(n)\sum_{T,R},q^{|\varphi|}=q\frac{[n+z_{R}(x_{0})][n+Z_{R}(x_{0})-1]\ldots[n+zR-(x0)-\#\langle_{X_{0}}\rangle+1]}{\Pi_{x\in T}[h(_{X})]}c_{R}.$.

が $(*)$ を満たすとき
従って,
但し, $c_{R}= \min\{|\varphi||\varphi\in A(T, R, n)\}$ とする.
$R\in \mathrm{E}\mathrm{L}(P)$$R\in \mathrm{H}\mathrm{E}\mathrm{L}(P)$である.

Example 5.10
, $R_{1}=$$T_{1}=$とすると,$R_{1}$

は条件-(*) を満

たす (/\supset で$\varphi\in A(T1,R1,)\sum_{n}q|\varphi|=q^{6}\frac{[n+2][n+1][n][n-1][n-2]}{\Pi_{x\in T}[h(_{X})]}$の等式が成立する.

$\mathrm{t}^{r}\mathit{2}$

等式か灰 V 丁る,94

また, Theorem 5.9 の条件 $(*)$ より次のことが容易にわかる.

Corollary 5.11
$T:\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}\Rightarrow \mathrm{H}\mathrm{E}\mathrm{L}(T)\neq\emptyset$

Corollary 5.12を tree,$T$$R\in \mathrm{E}\mathrm{L}(T)$る.11 但し, $|T|=n,${は $(*)$ を満たすとする. このとき, 次の式が得られ$x_{0}$を $T$ の最大元とする.

$\varphi\in A(\tau,R,n-ZR(0\sum_{x))}q^{1\varphi}=|qc_{R_{\frac{[n]!}{\Pi_{x\in T}[h(_{X})]}}}$

Theorem59 の逆として , 次のことがわかる.

Theorem 5.13
を tree とし,$T$$R_{x}\in \mathrm{H}\mathrm{E}\mathrm{L}(\langle_{X\rangle})$$R\in \mathrm{E}\mathrm{L}(T)$に対して次が成立する 12

for $\forall x\in T-{\rm Min}(T)\Rightarrow R$ (は $(*)$ を満たす.

また, 次のことが予想できる.

Conjecture 5.14
$T$を tree とする. このとき次が成立する.
$R\in \mathrm{H}\mathrm{E}\mathrm{L}(P)\Rightarrow R$(は $(*)$ を満たす.

参考文献[1] R. A. Proctor, Dynkin Diagram Classification of -Minuscule Bruhat
Lattices and of -Complete Posets, Journal of Algebraic Combinatorics 9 (1999), 61–94.
$\lambda$$d$[2] R. P. Stanley, Enumerative Combinatorics Volume , Wadsworth&Mathematics Series, 1986.
$I$$\mathrm{B}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{k}_{\mathrm{S}}/\mathrm{C}\mathrm{o}\mathrm{l}\mathrm{e}$[3] R. P. Stanley, Enumerative Combinatorics Volume 2, Cambridge
Studies in Advanced Mathematics 62, 1999.
11

この式の右辺は linear extension の個数を表す -analogue になっているは $(*)$ を満たす”. は OK
Theorem 59 より$\mathrm{q}$12$‘ {}^{t}R\in \mathrm{H}\mathrm{E}\mathrm{L}(P)\Leftarrow R$