月刊組合せ論 Natori は面白そうな組合せ論のトピックを紹介していく企画です。今回はヤング図形好きなら外せない、フック長公式について深掘りしていきます。
フック長公式
#
フック長公式は標準タブローの個数を数える公式です。標準タブローはヤング図形のマスに 1 から n n n
フックとは、あるマスとその右・下にあるマスからなる集合です。
フック長公式によると、標準タブローの個数は
n ! ∏ ( i , j ) ∈ λ h ( i , j )
\frac{n!}{\prod_{(i,j)\in\lambda} h(i,j)}
∏ ( i , j ) ∈ λ h ( i , j ) n ! により求められます。ここで h ( i , j ) h(i,j) h ( i , j ) λ \lambda λ h λ ( i , j ) h_{\lambda}(i,j) h λ ( i , j ) n ! n! n !
以下ではフック長公式の証明をいくつか紹介します。1 つ目の証明のみ詳述し、残りは概略を述べるだけとします。
確率を用いた証明
#
この証明が恐らくもっとも有名ではないでしょうか。
[1] の証明です。
λ \lambda λ D λ D_{\lambda} D λ F λ = n ! ∏ ( i , j ) ∈ λ h ( i , j ) F_{\lambda}=\frac{n!}{\prod_{(i,j)\in\lambda}h(i,j)} F λ = ∏ ( i , j ) ∈ λ h ( i , j ) n ! D λ = F λ D_{\lambda}=F_{\lambda} D λ = F λ
λ \lambda λ 隅 とは、右にも下にもマスがないようなマスをいいます。最大の数 n n n n − 1 n-1 n − 1 D λ D_{\lambda} D λ
D λ = ∑ μ ↗ λ D μ
D_{\lambda}=\sum_{\mu\nearrow\lambda}D_{\mu}
D λ = μ ↗ λ ∑ D μ ここで μ ↗ λ \mu\nearrow\lambda μ ↗ λ λ \lambda λ μ \mu μ μ \mu μ
λ = ( 1 ) \lambda=(1) λ = ( 1 ) D λ = F λ = 1 D_{\lambda}=F_{\lambda}=1 D λ = F λ = 1 F λ F_{\lambda} F λ
F λ = ∑ μ ↗ λ F μ
F_{\lambda}=\sum_{\mu\nearrow\lambda}F_{\mu}
F λ = μ ↗ λ ∑ F μ をみたすことを示せばよいです。この式を ∑ F μ F λ = 1 \sum\frac{F_{\mu}}{F_{\lambda}}=1 ∑ F λ F μ = 1
ヤング図形 λ \lambda λ フックウォーク を定義します。
まず λ \lambda λ ( x 1 , y 1 ) (x_1,y_1) ( x 1 , y 1 )
次に ( x 1 , y 1 ) (x_1,y_1) ( x 1 , y 1 ) ( x 1 , y 1 ) (x_1,y_1) ( x 1 , y 1 ) ( x 2 , y 2 ) (x_2,y_2) ( x 2 , y 2 )
これを繰り返します。
選んだマスを並べた ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x k , y k ) (x_1,y_1),(x_2,y_2),\ldots, (x_k,y_k) ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x k , y k ) ( x k , y k ) (x_k,y_k) ( x k , y k )
命題 : 隅 ( a , b ) (a,b) ( a , b ) ( a , b ) (a,b) ( a , b ) F μ F λ \frac{F_{\mu}}{F_{\lambda}} F λ F μ μ \mu μ λ \lambda λ ( a , b ) (a,b) ( a , b )
必ず終点が隅になることから確率の総和は 1 なので、この命題から示すべき式が従います。
命題を証明します。μ \mu μ λ \lambda λ ( a , b ) (a,b) ( a , b ) ( i , j ) (i,j) ( i , j ) ( a , b ) (a,b) ( a , b ) h λ ( i , j ) = h μ ( i , j ) h_{\lambda}(i,j)=h_{\mu}(i,j) h λ ( i , j ) = h μ ( i , j ) h μ ( i , j ) = h λ ( i , j ) − 1 h_{\mu}(i,j)=h_{\lambda}(i,j)-1 h μ ( i , j ) = h λ ( i , j ) − 1
F μ F λ = ( n − 1 ) ! / ∏ ( i , j ) ∈ μ h μ ( i , j ) n ! / ∏ ( i , j ) ∈ λ h λ ( i , j ) = 1 n ∏ ( i , j ) ∈ λ h λ ( i , j ) ∏ ( i , j ) ∈ μ h μ ( i , j ) = 1 n ∏ i = 1 a − 1 h λ ( i , b ) h λ ( i , b ) − 1 ∏ j = 1 b − 1 h λ ( a , j ) h λ ( a , j ) − 1 = 1 n ∏ i = 1 a − 1 ( 1 + 1 h λ ( i , b ) − 1 ) ∏ j = 1 b − 1 ( 1 + 1 h λ ( a , j ) − 1 )
\begin{align*}
\frac{F_{\mu}}{F_{\lambda}} &= \frac{(n-1)!/\prod_{(i,j)\in \mu}h_{\mu}(i,j)}{n!/\prod_{(i,j)\in \lambda}h_{\lambda}(i,j)} \\
&= \frac{1}{n}\frac{\prod_{(i,j)\in\lambda}h_{\lambda}(i,j)}{\prod_{(i,j)\in\mu}h_{\mu}(i,j)} \\
&= \frac{1}{n}\prod_{i=1}^{a-1}\frac{h_{\lambda}(i,b)}{h_{\lambda}(i,b)-1}\prod_{j=1}^{b-1}\frac{h_{\lambda}(a,j)}{h_{\lambda}(a,j)-1} \\
&= \frac{1}{n}\prod_{i=1}^{a-1}\left(1+\frac{1}{h_{\lambda}(i,b)-1}\right)\prod_{j=1}^{b-1}\left(1+\frac{1}{h_{\lambda}(a,j)-1}\right)
\end{align*}
F λ F μ = n ! / ∏ ( i , j ) ∈ λ h λ ( i , j ) ( n − 1 )! / ∏ ( i , j ) ∈ μ h μ ( i , j ) = n 1 ∏ ( i , j ) ∈ μ h μ ( i , j ) ∏ ( i , j ) ∈ λ h λ ( i , j ) = n 1 i = 1 ∏ a − 1 h λ ( i , b ) − 1 h λ ( i , b ) j = 1 ∏ b − 1 h λ ( a , j ) − 1 h λ ( a , j ) = n 1 i = 1 ∏ a − 1 ( 1 + h λ ( i , b ) − 1 1 ) j = 1 ∏ b − 1 ( 1 + h λ ( a , j ) − 1 1 ) となります。展開すると
F μ F λ = 1 n ∑ A ⊆ { 1 , … , a − 1 } ∑ B ⊆ { 1 , … , b − 1 } Q ( A , B ) Q ( A , B ) = ∏ i ∈ A 1 h λ ( i , b ) − 1 ∏ j ∈ B 1 h λ ( a , j ) − 1
\begin{gather*}
\frac{F_{\mu}}{F_{\lambda}}=\frac{1}{n}\sum_{A\subseteq\{1,\ldots,a-1\}}\sum_{B\subseteq\{1,\ldots,b-1\}}Q(A,B) \\
Q(A,B)=\prod_{i\in A}\frac{1}{h_{\lambda}(i,b)-1}\prod_{j\in B}\frac{1}{h_{\lambda}(a,j)-1}
\end{gather*}
F λ F μ = n 1 A ⊆ { 1 , … , a − 1 } ∑ B ⊆ { 1 , … , b − 1 } ∑ Q ( A , B ) Q ( A , B ) = i ∈ A ∏ h λ ( i , b ) − 1 1 j ∈ B ∏ h λ ( a , j ) − 1 1 となります。
ここで部分集合 A , B A,B A , B ( min ( A ∪ { a } ) , min ( B ∪ { b } ) ) (\min(A\cup\{a\}), \min(B\cup\{b\})) ( min ( A ∪ { a }) , min ( B ∪ { b })) ( a , b ) (a,b) ( a , b ) A ∪ { a } A\cup\{a\} A ∪ { a } B ∪ { b } B\cup\{b\} B ∪ { b } P ( A , B ) P(A,B) P ( A , B ) P ( A , B ) = Q ( A , B ) P(A,B)=Q(A,B) P ( A , B ) = Q ( A , B )
∣ A ∣ + ∣ B ∣ |A|+|B| ∣ A ∣ + ∣ B ∣ A A A B B B x 1 = min A , y 1 = min B x_1=\min A, y_1=\min B x 1 = min A , y 1 = min B P ( A , B ) = 1 h λ ( x 1 , y 1 ) − 1 ( P ( A ∖ { x 1 } , B ) + P ( A , B ∖ { y 1 } ) ) P(A,B)=\frac{1}{h_{\lambda}(x_1,y_1)-1}(P(A\setminus\{x_1\}, B)+P(A,B\setminus\{y_1\})) P ( A , B ) = h λ ( x 1 , y 1 ) − 1 1 ( P ( A ∖ { x 1 } , B ) + P ( A , B ∖ { y 1 }))
P ( A ∖ { x 1 } , B ) = Q ( A ∖ { x 1 } , B ) = ∏ i ∈ A ∖ { x 1 } 1 h λ ( i , b ) − 1 ∏ j ∈ B 1 h λ ( a , j ) − 1 = ( h λ ( x 1 , b ) − 1 ) Q ( A , B )
\begin{align*}
P(A\setminus\{x_1\}, B) &= Q(A\setminus\{x_1\}, B) \\
&= \prod_{i\in A\setminus\{x_1\}}\frac{1}{h_{\lambda}(i,b)-1}\prod_{j\in B}\frac{1}{h_{\lambda}(a,j)-1} \\
&= (h_{\lambda}(x_1,b)-1)Q(A,B)
\end{align*}
P ( A ∖ { x 1 } , B ) = Q ( A ∖ { x 1 } , B ) = i ∈ A ∖ { x 1 } ∏ h λ ( i , b ) − 1 1 j ∈ B ∏ h λ ( a , j ) − 1 1 = ( h λ ( x 1 , b ) − 1 ) Q ( A , B ) 同様に
P ( A , B ∖ { y 1 } ) = ( h λ ( a , y 1 ) − 1 ) Q ( A , B )
P(A,B\setminus\{y_1\})=(h_{\lambda}(a,y_1)-1)Q(A,B)
P ( A , B ∖ { y 1 }) = ( h λ ( a , y 1 ) − 1 ) Q ( A , B ) となるので
P ( A , B ) = h λ ( x 1 , b ) − 1 + h λ ( a , y 1 ) − 1 h λ ( x 1 , y 1 ) − 1 Q ( A , B ) = Q ( A , B )
P(A,B)=\frac{h_{\lambda}(x_1,b)-1+h_{\lambda}(a,y_1)-1}{h_{\lambda}(x_1,y_1)-1}Q(A,B)=Q(A,B)
P ( A , B ) = h λ ( x 1 , y 1 ) − 1 h λ ( x 1 , b ) − 1 + h λ ( a , y 1 ) − 1 Q ( A , B ) = Q ( A , B ) となります。h λ ( x 1 , y 1 ) − 1 = h λ ( x 1 , b ) − 1 + h λ ( a , y 1 ) − 1 h_{\lambda}(x_1,y_1)-1=h_{\lambda}(x_1,b)-1+h_{\lambda}(a,y_1)-1 h λ ( x 1 , y 1 ) − 1 = h λ ( x 1 , b ) − 1 + h λ ( a , y 1 ) − 1
これで証明が完了しました。この証明は「確率論的な証明」と呼ばれることがありますが、大学数学における確率論は測度論などを用いた厳密なものであるのに対して、この証明は高校数学の知識しか用いていません。実際に名古屋大学の入試でこの証明を元にした問題が出題されています。
全単射
#
全単射を用いた証明がいくつかあります。F λ F_{\lambda} F λ n ! = F λ ∏ ( i , j ) h ( i , j ) n!=F_{\lambda}\prod_{(i,j)}h(i,j) n ! = F λ ∏ ( i , j ) h ( i , j ) a ( i , j ) a(i,j) a ( i , j ) ( i , j ) (i,j) ( i , j ) l ( i , j ) l(i,j) l ( i , j ) ( i , j ) (i,j) ( i , j ) h ( i , j ) = a ( i , j ) + l ( i , j ) + 1 h(i,j)=a(i,j)+l(i,j)+1 h ( i , j ) = a ( i , j ) + l ( i , j ) + 1 − l ( i , j ) -l(i,j) − l ( i , j ) a ( i , j ) a(i,j) a ( i , j ) h ( i , j ) h(i,j) h ( i , j ) ( i , j ) (i,j) ( i , j ) − l ( i , j ) -l(i,j) − l ( i , j ) a ( i , j ) a(i,j) a ( i , j )
標準タブローの個数が F λ F_{\lambda} F λ ∏ ( i , j ) h ( i , j ) \prod_{(i,j)}h(i,j) ∏ ( i , j ) h ( i , j )
詳しくは
[4] で解説されています。
表現論
#
ヤング図形は対称群の表現論と深くかかわります。例えば対称群 S n S_n S n n n n λ \lambda λ λ \lambda λ
フロベニウスの指標公式と呼ばれるものがあり、そこから証明することができるようです。
[5] を参照してください。
複素解析
#
複素解析を用いた証明もあります。以下の文献で解説されています。
ヤング図形の組合せ論講義
幾何学
#
幾何学な証明は
[2] にあるようです。（読んでいません……）
おわりに
#
今回はフック長公式の様々な証明を紹介しました。1 つの公式にいろいろな証明があるのは面白いですね。
今後も月刊組合せ論 Natori では様々なトピックを紹介予定なので、応援のほどよろしくお願いいたします。
参考文献
#
Greene, Curtis; Nijenhuis, Albert; Wilf, Herbert S. A probabilistic proof of a formula for the number of Young tableaux of a given shape. Adv. Math. 31, 104-109 (1979).
Hook length formula and geometric combinatorics. Sémin. Lothar. Comb. 46, B46f, 13 p. (2001).
Romik, Dan. The surprising mathematics of longest increasing subsequences. Cambridge University Press. (2015).
Sagan, Bruce E. The symmetric group. Representations, combinatorial algorithms, and symmetric functions. 2nd ed. Springer. (2001).
池田岳. テンソル代数と表現論. 東京大学出版会
