フック長の公式

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/04/18 14:05 UTC 版)

Proofs

Knuth's heuristic argument

The hook-length formula can be understood intuitively using the following heuristic, but incorrect, argument suggested by D. E. Knuth.^[16] Given that each element of a tableau is the smallest in its hook and filling the tableau shape at random, the probability that cell $(i,j)$

Corners of the Young diagram (5,3,2,1,1)

ここで、 $e_{\phi }=1$ であることにも注意されたい。それゆえ、次を示せば十分で、

e_{\lambda }=\sum _{\mu \uparrow \lambda }e_{\mu },

その結果、 $d_{\lambda }=e_{\lambda }$ は帰納的に証明される。

上の式の和は、次のように式を書き換えることによって、確率の和と捉えることができる。

\sum _{\mu \uparrow \lambda }{\frac {e_{\mu }}{e_{\lambda }}}=1.

われわれはこのようにして、 ${\frac {e_{\mu }}{e_{\lambda }}}$ が、ヤング図形μの集合上の確率測度を定めている。（ここで $\mu \uparrow \lambda$ ）

これはフックウォークと呼ばれるランダムウォークを定義を用いた構成法によるものである。

フックウォークは、ヤング図形λの上で、ひとつのコーナーセルを選択する。

フックウォークは次のルールによって定義される。

(1) $|\lambda |$ 個のセルのなかから一様ランダムにひとつのセルを選び、そこからランダムウォークを始める。

(2) 現在の $(i,j)$ セルの次のセルは、一様ランダムにフック $H_{\lambda }(i,j)\setminus \{(i,j)\}$ から選ぶ。

(3) 一つのコーナーに到達するまでこれを続け、そのコーナーセルを ${\textbf {c}}$ とする。

命題: λに属するすべてのコーナーセル $(a,b)$ に対して、次が成り立つ。

\mathbb {P} \left({\textbf {c}}=(a,b)\right)={\frac {e_{\mu }}{e_{\lambda }}},

ここで、 $\mu =\lambda \setminus \{(a,b)\}$ .

この命題を得れば、すべての ${\textbf {c}}=(a,b)$ に関して和をとることによって、 $\sum _{\mu \uparrow \lambda }{\frac {e_{\mu }}{e_{\lambda }}}=1$ を得る。

脚注

^ Frame, J. S., Robinson, G. de B. and Thrall, R. M. (1954). The hook graphs of the symmetric group. Can. J. Math. 6, 316–325.
^ G. Frobenius. Uber die charaktere der symmetrischer gruppe, Preuss. &ad. Wk. sitz. (1900), 516–534.
^ A. Young. Quantitative substitutional analysis II, Proc. London Math. Sot., Ser. 1, 35 (1902), 361–397.
^ P. A. MacMahon. “Combinatory Analysis,” Cambridge Univ. Press, London/New York, 1916; reprinted by Chelsea, New York, 1960.
^ Knuth, Donald (1973). The Art of Computer Programming, Volume 3: Sorting and Searching, 3rd Edition, Addison–Wesley, p. 63
^ A. P. Hillman and R. M. Grassl. Reverse plane partitions and tableau hook numbers, J. Comb. Theory, Ser. A 21 (1976), 216–221.
^ Greene, C., Nijenhuis, A. and Wilf, H. S. (1979). A probabilistic proof of a formula for the number of Young tableaux of a given shape. Adv. in Math. 31, 104–109.
^ J. B. Remmel. Bijective proofs of formulae for the number of standard Young tableaux, Linear and Multilinear Algebra 11 (1982), 45–100.
^ Franzblau, D. S. and Zeilberger, D. (1982). A bijective proof of the hook-length formula. J. Algorithms 3, 317–343.
^ D. Zeilberger. A short hook-lengths bijection inspired by the Greene–Nijenhuis–Wilf proof, Discrete Math. 51 (1984), 101–108.
^ Pak, I. M. and Stoyanovskii, A. V. (1992). A bijective proof of the hook-length formula. Funct. Anal. Appl. 24.
^ Novelli, J.-C., Pak, I. M. and Stoyanovskii, A. V. (1997). A direct bijective proof of the hook-length formula. Discrete Mathematics and Theoretical Computer Science 1, 1997, 53–67.
^ R. M. Thrall. A combinatorial problem, Michigan Math. J. 1 (1952), 81–88.
^ Sagan, B. On selecting a random shifted Young tableau. J. Algorithms 1, 3 (1980), 213–234.
^ Sagan, B. E., and Yeh, Y. N. Probabilistic algorithms for trees. Fibonacci Quart. 27, 3 (1989), 201–208.
^ Knuth, Donald (1973), The Art of Computer Programming, Volume 3: Sorting and Searching, 3rd Edition, Addison–Wesley, p. 63, ISBN 0-201-03803-X .
^ Greene, C., Nijenhuis, A. and Wilf, H. S. (1979). A probabilistic proof of a formula for the number of Young tableaux of a given shape. Adv. in Math. 31, 104–109.
^ W. Fulton, J. Harris. Representation Theory: A First Course Springer-Verlag , New York, 1991
^ Vershik, A. M.; Kerov, C. V. (1977), "Asymptotics of the Plancheral measure of the symmetric group and a limiting form for Young tableaux", Dokl. Akad. Nauk SSSR 233: 1024–1027
^ B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), no. 2, 206–222.
^ Knuth, Donald (1973), The Art of Computer Programming, 3 (1 ed.), Addison–Wesley, pp. 61–62
^ Stanley, Richard P. (1971), “Theory and applications of plane partitions, 2”, Studies in Applied Mathematics 50: 259–279
^ R.P. Stanley, "Ordered Structures and Partitions" PhD Thesis, Harvard University, 1971
^ Morales, A. H., Pak, I., and Panova, G. Hook formulas for skew shapes, arXiv:1512.08348.

[前の解説]

[続きの解説]

「フック長の公式」の続きの解説一覧

フック長の公式 Proofs