フック長公式

同義語:hook length formulahook-length formula鉤長公式Frame–Robinson–Thrallの公式

概要

フック長公式(hook length formula)とは、$n$ の分割 $\lambda$ の Young 図形に $1,\dots,n$ を行と列が増加するように書き込む標準盤の個数 $f^\lambda$ が、各箱のフックの長さ(その箱と、右にある箱と下にある箱の個数)の積で $n!$ を割った値に等しいという公式である。Frame・Robinson・Thrall が発見した。Greene・Nijenhuis・Wilf の証明は、図形の上の無作為な歩みが各角で止まる確率を計算して漸化式を示すもので、標準盤を一様に無作為に作る方法も与える。$f^\lambda$ は対称群の既約表現の次元に等しい。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Young図形, 分割数

フック長公式(hook length formula)は、Young 図形の箱に $1,2,\dots,n$ を行と列が増加するように書き込む方法の個数 $f^\lambda$ を、各箱の「フックの長さ」の積だけで表す公式
$$ f^\lambda=\frac{n!}{\prod_{u\in\lambda}h(u)} $$
である。Frame・Robinson・Thrall が発見したので Frame–Robinson–Thrall の公式ともよばれ、Young図形 の記事では鉤長公式とよんでいる。$f^\lambda$ は対称群 $S_n$ の既約表現の次元でもあるので、この公式は表現の次元を図形から読む方法でもある。
左辺は書き込みを数えた個数、右辺は図形の形だけから決まる積であり、右辺が整数になること自体が自明ではない。この記事では、Greene・Nijenhuis・Wilf による確率を使った証明を完全に述べる。証明の要は、図形の上をでたらめに歩く「フックの歩み」が各角で止まる確率を正確に計算することである。この証明からは、標準盤を一様に無作為に作る方法も得られる。続いて、各行のフックの長さを並べ替えて得られる積の公式と、根付き木についての同じ形の公式を証明し、公式が成り立たなくなる場合を反例の表にまとめる。

定義

以下、$n\ge0$ を整数とし、$n$ の 分割 $\lambda=(\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_k>0)$、$\lambda_1+\cdots+\lambda_k=n$ を考える(分割数 の記事の定義)。$\lambda\vdash n$ と書き、$k=\ell(\lambda)$ を長さとよぶ。

Young 図形と標準盤

分割 $\lambda\vdash n$ の Young 図形 とは、箱の集合 $\{(i,j)\mid1\le i\le\ell(\lambda),\ 1\le j\le\lambda_i\}$ である。$(i,j)$ を第 $i$ 行・第 $j$ 列の箱とよび、行は上から下へ、列は左から右へ番号を付けて描く。以下 $\lambda$ とその Young 図形を同じ記号で表す。
形 $\lambda$ の 標準盤(standard Young tableau)とは、全単射 $T\colon\lambda\to\{1,\dots,n\}$ であって、各行で左から右へ、各列で上から下へ値が増加するものをいう。その個数を $f^\lambda$ と書き、$f^{\emptyset}=1$ とする。

フックとフックの長さ

箱 $u=(i,j)\in\lambda$ の フック $H(u)$ とは、$u$ 自身と、$u$ と同じ行で右にある箱と、$u$ と同じ列で下にある箱を合わせた集合である。その箱の個数を フックの長さ $h(u)$ という。第 $j$ 列の箱の個数を $\lambda'_j$ と書くと
$$ h(i,j)=(\lambda_i-j)+(\lambda'_j-i)+1 $$
である。$h(u)=1$ となる箱、すなわち右にも下にも箱がない箱を 角(corner)という。

角は各行の右端の箱 $(i,\lambda_i)$ のうち $\lambda_{i+1}< \lambda_i$ となるものであり、角を 1 つ取り除くとまた Young 図形が残る。角 $c$ を取り除いた図形を $\lambda-c$ と書く。

主定理

フック長公式

$\lambda\vdash n$ に対して
$$ f^\lambda=\frac{n!}{\prod_{u\in\lambda}h(u)} $$
が成り立つ。

証明の所在と由来

証明は「Greene–Nijenhuis–Wilf の証明」の節で完全に述べる(prf-hl-main)。この形の公式は Frame が見いだし、Frame・Robinson・Thrall の論文で最初に発表された(Sta13 Chapter 8 の注、p. 156)。同書は Theorem 8.1(p. 133)で主張を証明なしに述べ、注で Greene・Nijenhuis・Wilf の確率的な証明を紹介している(p. 156)。FH91 も §4.3(p. 57)で、Frame・Robinson・Thrall が標準盤の個数とフックの長さの式の一致を示したこと、短い組合せ的な証明が Greene・Nijenhuis・Wilf にあることを述べている。

例

小さい図形

$\lambda=(3,2)$ のフックの長さは、第 1 行が $4,3,1$、第 2 行が $2,1$ で、積は $24$ である。公式は $f^{(3,2)}=5!/24=5$ を与える。実際、標準盤は第 1 行に入る 3 つの数で決まり、それは $123$、$124$、$125$、$134$、$135$ の 5 通りである(第 2 行は残りを小さい順に並べる)。
$\lambda=(3,2,1)$ ではフックの長さが $5,3,1/3,1/1$(スラッシュは行の区切り)で、$f^{(3,2,1)}=720/45=16$ である。$\lambda=(4,2,2)$ では $6,5,2,1/3,2/2,1$ で、$f^{(4,2,2)}=8!/720=56$ である。

2 行の長方形と Catalan 数

$\lambda=(m,m)$ のフックの長さは、第 1 行が $m+1,m,\dots,2$、第 2 行が $m,m-1,\dots,1$ である。よって
$$ f^{(m,m)}=\frac{(2m)!}{(m+1)!\,m!}=\frac{1}{m+1}\binom{2m}{m} $$
であり、これは Catalan数 $C_m$ である。標準盤の第 1 行に入る数を「上がる一歩」、第 2 行に入る数を「下がる一歩」と読むと、$(m,m)$ の標準盤は 0 より下に行かない上下 $m$ 歩ずつの道と一対一に対応する。$m=4$ なら $f^{(4,4)}=14$ である。

フック形

$\lambda=(n-k,1^k)$(第 1 行が $n-k$ 個、その下に 1 個ずつの $k$ 行)では、左上の箱のフックの長さが $n$、第 1 行の残りが $n-k-1,\dots,1$、第 1 列の残りが $k,\dots,1$ である。公式は $f^\lambda=n!/(n\,(n-k-1)!\,k!)=\binom{n-1}{k}$ を与える。標準盤は第 1 列の残り $k$ 箱に入る数を $\{2,\dots,n\}$ から選べば決まるので、直接数えても同じ値になる。

$n=5$ の 7 つの分割について $f^\lambda$ は次のとおりである。

$\lambda$$(5)$$(4,1)$$(3,2)$$(3,1,1)$$(2,2,1)$$(2,1,1,1)$$(1^5)$
フックの長さの積$120$$30$$24$$20$$24$$30$$120$
$f^\lambda$$1$$4$$5$$6$$5$$4$$1$

2 乗の和は $1+16+25+36+25+16+1=120=5!$ である。この等式の意味は「応用」の節で述べる。$n\le9$ のすべての分割について、標準盤を全数で数えた値と公式の値が一致することを計算機で確かめた。

Greene–Nijenhuis–Wilf の証明

$F(\lambda):=n!/\prod_{u\in\lambda}h(u)$、$F(\emptyset):=1$ とおく。証明は 3 段からなる。$f^\lambda$ が満たす漸化式を立て、$F$ も同じ漸化式を満たすことを、比 $F(\lambda-c)/F(\lambda)$ をある確率として読むことで示す。

最大の数が入る箱

$n\ge1$ なら $f^\lambda=\sum_cf^{\lambda-c}$ が成り立つ。和は $\lambda$ の角 $c$ すべてにわたる。

証明を開く

標準盤で $n$ が入る箱の右や下に箱があれば、そこには $n$ より大きい数が入らなければならないが、そのような数はない。よって $n$ は角 $c$ に入り、$c$ を取り除くと形 $\lambda-c$ の標準盤が残る。逆に、角 $c$ と形 $\lambda-c$ の標準盤から、$c$ に $n$ を書き込めば形 $\lambda$ の標準盤が得られる($c$ の左と上の数はすべて $n$ より小さい)。2 つの操作は互いに逆である。$\square$

角を取り除いたときの比

$c=(\alpha,\beta)$ を $\lambda\vdash n$($n\ge1$)の角とする。このとき
$$ \frac{F(\lambda-c)}{F(\lambda)}=\frac1n\prod_{i=1}^{\alpha-1}\frac{h(i,\beta)}{h(i,\beta)-1}\prod_{j=1}^{\beta-1}\frac{h(\alpha,j)}{h(\alpha,j)-1} $$
である。$i< \alpha$ なら $(i,\beta)$ の下に $c$ があるので $h(i,\beta)\ge2$ であり、$j< \beta$ でも同様なので、分母は $0$ でない。

証明を開く

$c$ を取り除くと、フックが $c$ を含む箱のフックだけが 1 つ短くなる。$c$ を含むフックは、$c$ 自身のものと、$c$ と同じ行で左にある箱 $(\alpha,j)$($j< \beta$)、同じ列で上にある箱 $(i,\beta)$($i< \alpha$)のものに限る。$h(c)=1$ なので、$\prod_{u\in\lambda-c}h(u)$ は $\prod_{u\in\lambda}h(u)$ から、$(i,\beta)$ と $(\alpha,j)$ の因子 $h$ を $h-1$ に替えたものである。$(n-1)!/n!=1/n$ とあわせて主張を得る。$\square$

次に、次の確率的な手順を考える。これを フックの歩み という。

  1. $\lambda$ の $n$ 個の箱から 1 つを等確率で選ぶ。
  2. いまいる箱 $v$ が角なら止まる。角でなければ、$H(v)\setminus\{v\}$ の $h(v)-1$ 個の箱から 1 つを等確率で選んで移り、2 に戻る。
    1 歩ごとに行番号と列番号の和が増えるので、歩みは $n$ 歩以内に止まり、止まる箱は角である。
フックの歩みの終点

$\lambda\vdash n$($n\ge1$)の角 $c=(\alpha,\beta)$ でフックの歩みが止まる確率は
$$ \frac1n\prod_{i=1}^{\alpha-1}\Bigl(1+\frac{1}{h(i,\beta)-1}\Bigr)\prod_{j=1}^{\beta-1}\Bigl(1+\frac{1}{h(\alpha,j)-1}\Bigr) $$
である。

通った行と列で分類する

1 歩は、行番号か列番号のどちらか一方だけを増やす。そこで、$c$ で止まる歩みについて、通った箱の行番号の集合 $A$ と列番号の集合 $B$ を記録する。$A\subseteq\{1,\dots,\alpha\}$、$\alpha\in A$、$B\subseteq\{1,\dots,\beta\}$、$\beta\in B$ であり、出発点は $(\min A,\min B)$ である。逆にこのような $A,B$ を与えると、$(\min A,\min B)$ は $c$ の左上にあるので $\lambda$ の箱である。
$(\min A,\min B)$ から出発した歩みが、行の集合がちょうど $A$、列の集合がちょうど $B$ となって $c$ で止まる確率を $q(A,B)$ とし、
$$ P(A,B):=\prod_{i\in A\setminus\{\alpha\}}\frac{1}{h(i,\beta)-1}\prod_{j\in B\setminus\{\beta\}}\frac{1}{h(\alpha,j)-1} $$
とおく。$q(A,B)=P(A,B)$ を $|A|+|B|$ についての帰納法で示す。
$|A|=|B|=1$ なら出発点は角 $c$ で、すぐに止まるので $q=1=P$ である。それ以外のとき、$a:=\min A$、$b:=\min B$ とおくと $(a,b)\ne c$ である。$a< \alpha$ なら $(a+1,b)$ が、$b< \beta$ なら $(a,b+1)$ が $\lambda$ の箱なので、$(a,b)$ は角でない。行の集合が $A$、列の集合が $B$ となるには、最初の 1 歩で $(a',b)$($a'$ は $A\setminus\{a\}$ の最小元)か $(a,b')$($b'$ は $B\setminus\{b\}$ の最小元)に移らなければならない。どちらの箱も $(a,b)$ のフックに入り、移る確率はそれぞれ $1/(h(a,b)-1)$ である。よって
$$ q(A,B)=\frac{1}{h(a,b)-1}\Bigl(q(A\setminus\{a\},B)+q(A,B\setminus\{b\})\Bigr) $$
である。ただし $a=\alpha$ なら第 1 項は現れず、$b=\beta$ なら第 2 項は現れない。
帰納法の仮定から、$a\ne\alpha$ なら $q(A\setminus\{a\},B)=P(A,B)\,(h(a,\beta)-1)$、$b\ne\beta$ なら $q(A,B\setminus\{b\})=P(A,B)\,(h(\alpha,b)-1)$ である。$a=\alpha$ のときは $h(a,\beta)-1=h(c)-1=0$ なので、現れない第 1 項を $P(A,B)(h(a,\beta)-1)$ と書いても同じであり、$b=\beta$ のときも同様である。したがって
$$ q(A,B)=P(A,B)\cdot\frac{(h(a,\beta)-1)+(h(\alpha,b)-1)}{h(a,b)-1} $$
となる。$c$ は角なので第 $\alpha$ 行の長さは $\beta$、第 $\beta$ 列の長さは $\alpha$ であり、def-hl-hook の式から
$$ (h(a,\beta)-1)+(h(\alpha,b)-1)=(\lambda_a-\beta+\alpha-a)+(\beta-b+\lambda'_b-\alpha)=h(a,b)-1 $$
である。よって $q(A,B)=P(A,B)$ が示された。
出発点 $(\min A,\min B)$ は確率 $1/n$ で選ばれ、$A,B$ の組が異なれば歩みも異なるので、$c$ で止まる確率は $\frac1n\sum_{A,B}P(A,B)$ である。積 $\prod_{i< \alpha}(1+x_i)\prod_{j< \beta}(1+y_j)$ を展開すると、$\alpha$ を除いた $A$ の元と $\beta$ を除いた $B$ の元を選ぶ項の和になるので、これは主張の式に等しい。$\square$

歩みの確率で漸化式を示す

$n$ についての帰納法で $f^\lambda=F(\lambda)$ を示す。$n=0$ では両辺が $1$ である。$n\ge1$ とし、$n-1$ 以下では正しいとする。$\frac{h}{h-1}=1+\frac{1}{h-1}$ なので、lem-hl-ratio と lem-hl-walk から、各角 $c$ について $F(\lambda-c)/F(\lambda)$ はフックの歩みが $c$ で止まる確率に等しい。歩みは必ずどこかの角で止まるので、これらの確率の和は $1$ であり、
$$ \sum_cF(\lambda-c)=F(\lambda) $$
を得る。帰納法の仮定と lem-hl-branch から $f^\lambda=\sum_cf^{\lambda-c}=\sum_cF(\lambda-c)=F(\lambda)$ である。$\square$

たとえば $\lambda=(3,2)$ の角は $(1,3)$ と $(2,2)$ で、フックの歩みがそこで止まる確率は $2/5$ と $3/5$ である。これは $f^{(2,2)}/f^{(3,2)}=2/5$、$f^{(3,1)}/f^{(3,2)}=3/5$ に等しい。$n\le8$ のすべての分割と角について、歩みの終点の確率を有理数で正確に計算し、$f^{\lambda-c}/f^\lambda$ と一致することを確かめた。

標準盤を一様に作る

証明は、$f^\lambda$ 個の標準盤から 1 つを等確率で選ぶ手順も与える。

一様な標準盤の生成

$\lambda\vdash n$ に対し、次の手順で形 $\lambda$ の標準盤 $T$ を作る。図形 $\mu:=\lambda$ から始め、$m=n,n-1,\dots,1$ の順に、$\mu$ の上でフックの歩みを 1 回行い、止まった角 $c$ に $m$ を書き込み、$\mu$ を $\mu-c$ に替える。このとき $T$ は形 $\lambda$ の標準盤であり、どの標準盤も確率 $1/f^\lambda$ で得られる。

証明を開く

各段で $m$ を角に書き込むので、$m$ の右と下には $m$ より後に書き込まれる数がなく、行と列は増加する。よって $T$ は標準盤である。$n$ についての帰納法で、各標準盤が確率 $1/f^\lambda$ で得られることを示す。$n=0$ は明らかである。標準盤 $T$ で $n$ が入る角を $c$ とすると、$T$ が得られるのは、最初の歩みが $c$ で止まり、かつ残りの手順が $\lambda-c$ の上で $T$ から $n$ を除いた盤を作るときである。主定理の証明で見たとおり最初の確率は $f^{\lambda-c}/f^\lambda$ であり、帰納法の仮定から後の確率は $1/f^{\lambda-c}$ である。積は $1/f^\lambda$ である。$\square$

積の公式と 2 行の場合

フックの長さの積は、各行の長さだけで書き直せる。$\lambda=(\lambda_1,\dots,\lambda_k)$ に対し $\ell_i:=\lambda_i+k-i$($1\le i\le k$)とおく。$\ell_1>\ell_2>\cdots>\ell_k\ge1$ である。

1 つの行のフックの長さ

第 $i$ 行の $\lambda_i$ 個の箱のフックの長さの集合は
$$ \{1,2,\dots,\ell_i\}\setminus\{\ell_i-\ell_j\mid i< j\le k\} $$
である。

証明を開く

除く数 $\ell_i-\ell_j$($j>i$)は $1$ 以上 $\ell_i-1$ 以下で相異なるので、右の集合の元の個数は $\ell_i-(k-i)=\lambda_i$ である。第 $i$ 行の箱のフックの長さは右へ行くほど小さく相異なり、最大の $h(i,1)=\lambda_i+k-i=\ell_i$ 以下なので、その集合は $\{1,\dots,\ell_i\}$ の $\lambda_i$ 元の部分集合である。よって、どのフックの長さも $\ell_i-\ell_j$($j>i$)と等しくないことを示せばよい。$1\le s\le\lambda_i$ について、第 $s$ 列の長さ $\lambda'_s$ は $\lambda_j\ge s$ となる $j$ の個数なので $i\le\lambda'_s$ である。$h(i,s)=\lambda_i-s+\lambda'_s-i+1$ であり、$j:=\lambda'_s+1$ とおく。$j\le k$ なら $\lambda_j< s\le\lambda_{j-1}$ であり、$\ell_i-\ell_j=\lambda_i-\lambda_j+j-i$ なので、$\ell_i-\ell_{j}=\lambda_i-\lambda_j+\lambda'_s+1-i>h(i,s)$ と $\ell_i-\ell_{j-1}=\lambda_i-\lambda_{j-1}+\lambda'_s-i\le\lambda_i-s+\lambda'_s-i< h(i,s)$ が成り立つ($j-1=\lambda'_s\ge i$ であり、$j-1=i$ のとき後者は $\ell_i-\ell_i=0$ で、除く数ではない)。$\ell_i-\ell_{j'}$ は $j'$ について増加するので、除く数のうち $i< j'\le j-1$ のものは $h(i,s)$ より小さく、$j'\ge j$ のものは $h(i,s)$ より大きい。$j=k+1$ なら $\lambda'_s=k$ で、除く数はすべて $\ell_i-\ell_k\le\lambda_i-s+k-i< h(i,s)$ である。$\square$

積の公式

$\lambda\vdash n$、$\ell_i=\lambda_i+k-i$ とすると
$$ f^\lambda=\frac{n!\prod_{1\le i< j\le k}(\ell_i-\ell_j)}{\ell_1!\,\ell_2!\cdots\ell_k!} $$
である。とくに 2 行の形 $\lambda=(a,b)$($a\ge b\ge0$)では
$$ f^{(a,b)}=\frac{a-b+1}{a+1}\binom{a+b}{b} $$
である。

証明を開く

lem-hl-row から、第 $i$ 行のフックの長さの積は $\ell_i!/\prod_{j>i}(\ell_i-\ell_j)$ である。これを $i=1,\dots,k$ について掛けて thm-hl-main に代入すればよい。2 行の場合は $k=2$、$\ell_1=a+1$、$\ell_2=b$ で、$f^{(a,b)}=(a+b)!\,(a-b+1)/((a+1)!\,b!)$ となり、主張の形に等しい。$b=0$ のときは $f^{(a)}=1$ で、右辺も $1$ である。$\square$

2 行の公式は、$a$ 票と $b$ 票の開票で前者が一度も後者を下回らない並べ方の数(投票の問題)でもある。$a=b=m$ なら ex-hl-catalan の Catalan 数に戻る。cor-hl-frobenius の式は、FH91 (4.11)(p. 50)が対称群の既約表現の次元として与える式と同じである。同書は Exercise 4.13 でこの式からフック長公式を導くことを求めており、lem-hl-row はその道筋にあたる。フックの長さを使わない積の形の公式は、標準盤と同値な数え上げとして MacMahon が、表現の次元として Frobenius が、それぞれ独立に得ていた(Sta13 Chapter 8 の注、p. 156)。

木の上の同じ形の公式

フックの長さの積で割る形の公式は、根付き木にもある。こちらは証明がずっと易しく、主定理との違いが「フック」の選び方にあることを見せてくれる。

根付き木のフック長公式

$\mathcal T$ を $n$ 頂点の根付き木とし、頂点 $v$ を根とする部分木($v$ と $v$ の子孫全体)の頂点数を $h(v)$ とする。頂点に $1,\dots,n$ を 1 つずつ書き込み、どの頂点の数もその親の数より大きくなるようにする方法の個数は
$$ \frac{n!}{\prod_{v}h(v)} $$
である。

証明を開く

$n$ についての帰納法で示す。$n=1$ では $1$ 通りで、右辺も $1$ である。根を $r$ とし、$r$ を除くと根付き木 $\mathcal T_1,\dots,\mathcal T_s$(頂点数 $n_1,\dots,n_s$、$n_1+\cdots+n_s=n-1$)に分かれるとする。条件を満たす書き込みでは $r$ に $1$ が入る($r$ 以外の頂点は $r$ の子孫で、$r$ より大きい数が入る)。残りの $2,\dots,n$ を $\mathcal T_1,\dots,\mathcal T_s$ に配る方法は多項係数 $\frac{(n-1)!}{n_1!\cdots n_s!}$ 通りで、配った数の中での順序だけが条件に関わる。各 $\mathcal T_t$ の中の書き込み方は帰納法の仮定から $n_t!/\prod_{v\in\mathcal T_t}h(v)$ 通りである(部分木の大きさは $\mathcal T_t$ の中で数えても同じ)。掛け合わせると $(n-1)!/\prod_{v\ne r}h(v)$ となり、$h(r)=n$ なので主張の式に等しい。$\square$

Young 図形の箱を、左上の箱が最小になるように半順序集合と見ると、標準盤はこの半順序に沿った書き込みである。ただし Young 図形は木ではなく、フックは「その箱以上の箱全体」ではない。木の公式の $h(v)$ の真似をして「その箱より右下にある箱全体」の個数で割ると誤った値になる(下の反例の表の 2 行目)。Young 図形では、フックという小さな集合だけを数えるのが正しい。頂点数 $n\le6$ の根付き木について、頂点に $1,\dots,n$ の番号を付けて根を頂点 $1$ に固定したもの(各 $n$ で $n^{n-2}$ 本、合わせて 1442 本)を全部調べ、thm-hl-tree を確かめた。

応用

  • 対称群の表現:$\mathbb C$ 上の $S_n$ の既約表現は $n$ の分割で分類され(FH91 §4.1 Theorem 4.3、p. 46)、$\lambda$ に対応する既約表現の次元は $f^\lambda$ である(同 §4.3、p. 57。この記事では証明しない)。フック長公式はこの次元を図形から直接計算する式であり、同書は 4.12(p. 50)でフック長公式として次元の式を述べている。有限群の既約表現の次元の 2 乗の和は群の位数に等しい(同 Corollary 2.18 と (2.19)、p. 17)ので $\sum_{\lambda\vdash n}(f^\lambda)^2=n!$ であり、上の $n=5$ の表はこれを確かめている。この等式は Robinson–Schensted–Knuth対応 で組合せ的にも示される(Sta13 Theorem 8.13、p. 145)。
  • 格子路と投票の問題:2 行の標準盤は 0 より下に行かない格子路にあたり、cor-hl-frobenius がその個数を与える。
  • 無作為な標準盤:cor-hl-random は、大きな図形の標準盤を一様に無作為に作り、その性質を調べるときの基本の手順である。
  • 半標準盤との分担:標準盤が対称群の表現の次元を数えるのに対し、同じ値を繰り返して書いてよい半標準盤は一般線形群の表現の次元を数える。その関係は Schur多項式 の記事にある。

反例の表

主張がどの仮定で成り立たなくなるかを、外す条件を 1 つずつ変えて示す。

外す条件例成り立たなくなること
形が Young 図形(左上に詰まっている)歪んだ図形 $(3,2)/(1)$(箱 $(1,2),(1,3),(2,1),(2,2)$)個数が $4!/\prod h$ に等しいこと(実際は $5$、式は $4$)
割る数がフックの長さ$(2,2)$ で「右下にある箱全体」の個数 $4,2,2,1$ で割る個数が $4!/(4\cdot2\cdot2\cdot1)$ に等しいこと(実際は $2$、式は $3/2$)
列も増加する$(3,2)$ で行だけ増加する書き込み個数が $f^{(3,2)}=5$ に等しいこと(実際は $\binom53=10$)
歩みの出発点を一様に選ぶ$(3,2)$ で必ず $(1,1)$ から歩むlem-hl-walk の確率(角 $(1,3)$ で $1/2$、式は $2/5$)
反例の確認

1 行目:箱 $(2,2)$ は $(1,2)$ の下、$(2,1)$ の右にあるので、行と列が増加する書き込みでは $(1,2)<(1,3)$、$(1,2)<(2,2)$、$(2,1)<(2,2)$ だけが条件である。$4!=24$ 通りの書き込みを全部調べると条件を満たすのは $5$ 通りである。図形の中だけで数えたフックの長さは $(1,2)$ が $3$(自身、右の $(1,3)$、下の $(2,2)$)、$(1,3)$ が $1$、$(2,1)$ が $2$、$(2,2)$ が $1$ で、$24/6=4\ne5$ である。
2 行目:$(2,2)$ の標準盤は $12/34$ と $13/24$ の 2 つである。左上の箱より右下にある箱(自身を含む)は 4 個あり、フック(3 個)より多い。この数で割ると整数にもならない。
3 行目:第 1 行に入る 3 つの数を選べば行だけ増加する書き込みが決まるので $\binom53=10$ 通りあり、列の条件を課すと $5$ 通りに減る。
4 行目:$(1,1)$ のフックの長さは $4$ なので、最初に $(1,2),(1,3),(2,1)$ へ確率 $1/3$ ずつ移る。$(1,2)$ からは $(1,3)$ と $(2,2)$ へ $1/2$ ずつ、$(2,1)$ からは $(2,2)$ へ移る。角 $(1,3)$ で止まる確率は $\frac13\cdot\frac12+\frac13=\frac12$ であり、$f^{(2,2)}/f^{(3,2)}=2/5$ と異なる。出発点を一様に選ぶことは、prf-hl-walk で出発点の確率 $1/n$ を使う箇所に効いている。

関連項目

参考文献

[1]
Richard P. Stanley, Algebraic Combinatorics: Walks, Trees, Tableaux, and More, Undergraduate Texts in Mathematics, Springer, 2013, 著者公開の草稿 Topics in Algebraic Combinatorics(2013 年 2 月 1 日版)の番号と頁:Chapter 8、Theorem 8.1(p. 133)、Theorem 8.13(p. 145)、Notes for Chapter 8(p. 156)
[2]
William Fulton, Joe Harris, Representation Theory: A First Course, Graduate Texts in Mathematics 129, Springer, 1991, §2.2 Corollary 2.18 と式 (2.19)(p. 17)、§4.1 Theorem 4.3(p. 46)、式 (4.11)・Hook Length Formula 4.12・Exercise 4.13(p. 50)、§4.3(p. 57)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する