数学の組合せ論において、フック長の公式（フックちょうのこうしき、）とは、与えられたヤング図形の形をした標準盤を数える公式である。表現論や、確率論、アルゴリズム解析などの多種多様な分野に応用があり、などが例として挙げられる。
定義と主張 をの分割とする. は、通常、ヤング図形として図示的に解釈される。すなわち、行からなり、各について行目に個のセルを持つ、左揃えの正方形のセルの配列である。形状 の 標準ヤング盤 とは、形状 を持つヤング図形のうち、 個の各セルに 1 から までの異なる整数が含まれており（すなわち、重複がない）、かつ各行および各列が増加する 数列 をなすものをいう。ヤング図形における座標 の各セル（すなわち、行目と 列目にあるセル）について、その 『フック』 は、 かつ または かつ を満たすセル の 集合 である。フック長 は、フック に含まれるセルの数である。
よって、フック長に関する公式は、形状 を持つ標準ヤング表の数（時に と表記される）を次のように表す。
ここで、積は の全てのセル についてとられる。
例 右|サムネイル|ヤング図形 の各セルのフック長を一覧にした表 右の図は、分割
9 = 4 + 3 + 1 + 1 に対応する ヤング図形 の全てのセルにおけるフック長を示す。このヤング図形に対する標準的な ヤング・タブロー の数は、次のように計算できる。
歴史 には他にも公式が存在するが、フック長公式はとりわけ容易かつエレガントである。フック長公式は、1954年にJ. S. フレーム、とによって、行列式を用いて を表す、あまり有用ではない公式を改善することで発見されたFrame, J. S., Robinson, G. B. and Thrall, R. M. (1954). The hook graphs of the symmetric group. Can. J. Math. 6, 316–325.。この以前の公式は、G. フロベニウスとによって、それぞれ1900年と1902年に代数的手法を用いて独立に導出されたG. フロベニウス. 『対称群の特性について』, Preuss. &ad. Wk. sitz. (1900), 516–534.A. ヤング. 『定量的置換解析 II』, Proc. London Math. Sot., Ser. 1, 35 (1902), 361–397.。P. A. マクマホンは、1916年に差分法を用いてヤング・フロベニウス公式の別の証明を見出したP. A. マクマホン. 『Combinatory Analysis』, ケンブリッジ大学出版局, ロンドン／ニューヨーク, 1916年; チェルシー社（ニューヨーク）より1960年に再版.。
フック長公式は容易であるにもかかわらず、フレーム・ロビンソン・スロールによる証明は洞察に欠けており、なぜこの公式にフックが現れるのかについて直感的な説明を提供していない。このような容易な結果にふさわしい、簡潔で直感的な説明を求める探索が、フック長公式に対する多くの代替証明を生み出した。A. P. ヒルマンと R. M. グラスルは、1976年に、フック長公式を導くことが知られているのフック内容公式の特殊なケースを証明することで、フックの役割を明らかにした最初の証明を示したA. P. Hillman and R. M. Grassl. Reverse plane partitions and tableau hook numbers, J. Comb. Theory, Ser. A 21 (1976), 216–221.。、とは、1979年にフック・ウォークを用いた確率論的証明を見出し、その中でフック長が自然に現れることを示したGreene, C., Nijenhuis, A. and Wilf, H. S. (1979). 所定の形状を持つヤング表の数に関する公式の確率論的証明。Adv. in Math. 31, 104–109.。は、1982年に、オリジナルのフレーム・ロビンソン・スロールによる証明を応用し、フック長公式に対する最初の全単射な証明を確立したJ. B. Remmel. 標準ヤング表の個数に関する公式の全単射的証明, Linear and Multilinear Algebra 11 (1982), 45–100.。直接的で全単射な証明は、1982年に D. S. フランツブラウと によって初めて発見されたFranzblau, D. S. and Zeilberger, D. (1982). A bijective proof of the hook-length formula. J. Algorithms 3, 317–343.。D.ザイルバーガーもまた、1984年にグリーン・ナイエンハウス・ウィルフのフックウォークによる証明を、全単射な証明へと変換したD. ザイルバーガー. 「グリーン・ナイエンハウス・ウィルフの証明に触発された、フック長に関する短い双射」、Discrete Math. 51 (1984), 101–108. 。より容易で直接的かつ全単射な証明は、1992年にとアレクサンドル・V・ストヤノフスキーによって発表され、その完全な証明は1997年に同二人とジャン＝クリストフ・ノヴェリによって提示された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). フック長公式の直接的な全単射的証明. Discrete Mathematics and Theoretical Computer Science 1, 1997, 53–67.。
一方、フック長公式はいくつかの方法で一般化されている。R. M. スロールは1952年に、シフトされたヤング・タブローに対するフック長公式の類似式を見出したR. M. Thrall. 組合せ論的問題, Michigan Math. J. 1 (1952), 81–88.。は1980年、シフトされたヤング表に対するフック長公式について、シフトされたフックウォークを用いた証明を行ったSagan, B. ランダムなシフトされたヤング表の選択について. J. Algorithms 1, 3 (1980), 213–234.。B. E. セーガンとY. N. イェは、1989年にフックウォークを用いて二分木に対するフック長公式を証明したSagan, B. E., and Yeh, Y. N. Probabilistic algorithms for trees. Fibonacci Quart. 27, 3 (1989), 201–208.。
証明 クヌースのヒューリスティックな議論 フック長公式は、D. E. クヌースが提案した以下のヒューリスティックな（ただし誤った）議論を用いて直感的に理解することができる。タブローの各要素がそのフック内で最小であり、かつタブローの形状がランダムに埋められると仮定すると、セル が対応するフックの最小要素を含む確率は、そのフックの長さの逆数となる。これら全ての および について確率を乗算することで、この式が得られる。しかし、事象が独立していないため、この議論は誤りである。
しかし、ヤング・タブローのそれと類似した単調性の性質を満たす木におけるラベル付けの数え上げに関しては、クヌースの議論は正しい。この場合、問題となっている「フック」事象は、実際には独立した事象である。
フックウォークを用いた確率論的証明法 これは1979年に、 C. グリーン、A. ナイエンハウス と H. S.ウィルフによって発見された、確率論的証明法である。証明の概略は、次のとおりである。
を定義し、 を証明する。
は以下で与えられる。
ここで、 は、がヤング図形λから一つのコーナーセルを削除することで得られるヤングタブローであることを表している。
そのようなμの全体にわたって和をとる。ここで、慣習として を空のダイアグラムとして、 を用いる。
上の式に対する説明は、「ヤングタブローの最大項はそのコーナーセルで生じるものである」となる。
そのセルを削除することで、μの形のヤングタブローを得る。
μの形のヤングタブローの数が で、それらμに関して和をとることでその式を得る。 右|サムネイル|Corners of the Young diagram (5,3,2,1,1) ここで、であることにも注意されたい。それにより、次を示せば十分で、
その結果、 は帰納的に証明される。
上の式の和は、次のように式を書き換えることで、確率の和と捉えることができる。
われわれはこのようにして、 が、ヤング図形μの集合上の確率測度を定めている。（ここで は前述と同様）
これはフックウォークと呼ばれるランダムウォークを定義を用いた構成法によるものである。
フックウォークは、ヤング図形λの上で、ひとつのコーナーセルを選択する。
フックウォークは次のルールによって定義される。
(1) 個のセルのなかから一様ランダムにひとつのセルを選び、そこからランダムウォークを始める。
(2) 現在の セルの次のセルは、一様ランダムにフック から選ぶ。
(3) 一つのコーナーに到達するまでこれを続け、そのコーナーセルをとする。
命題: λに属する全てのコーナーセル に対して、次が成り立つ。
ここで、 .
この命題を得れば、全ての に関して和をとることで、 を得る。
表現論との関連 フック長公式は、対称群 の表現論において極めて重要である。ここで、数 は、 に関連付けられた複素既約表現 の次元と等しいことが知られており、しばしば と表記される。 または と表記されることが多い。
詳細な考察 対称群の複素既約表現 は、 の分割 によってインデックス付けられる（具体的な構成については シュペヒト・モジュール を参照）。それらの特性関数は、ホール内積を介して対称関数の理論と以下の式によって関連付けられている。
ここで、 は に関連付けられた シューア関数 であり、 は のサイクル分解に関連付けられた分割 の冪和対称関数である。例えば、 の場合、 となる。
単位置換 は、サイクル表記において の形をとるため、 となる。よって、この公式は次のように表される。
を用いて単項対称関数によるシューア関数の展開を考慮すると
との内積は となる。これは、 であるためである。なお、 は に等しい。よって、
このことから直ちに以下のことが導かれる。
上記の等式は、からも簡単に導かれる。
また、計算により以下のことが示される：
これは、 であることから、内積によって与えられる係数を用いてシューア関数を用いて を展開したものである。上記の等式は、両辺の各単項式の係数を検証し、ロビンソン・シェンステッド対応を用いることによっても証明できる。あるいは、より概念的に言えば、 を既約な モジュールによる分解として捉え、指標を取ることもできる。を参照のこと。
フロベニウス公式を用いたフック公式の証明の概要 上記の考察より、
よって、
ここで、 は ヴァンデルモンド行列式 である。
与えられた分割 に対し、 について を定義する。以下では、分割の行数以上の変数が必要となるため、これ以降は 個の変数 を用いて扱う。
各項 は、
シューア関数を参照のこと。ベクトル は各分割ごとに異なるため、これは の係数は、（ と表記される）において、 に等しくなる。これはとして知られており、最も初期の証明の一つを与えているW. Fulton, J. Harris. 『Representation Theory: A First Course』 Springer-Verlag, New York, 1991。あとは、技巧と力技を組み合わせてその係数を追跡するだけである。すなわち、
そして、
よって、求めている係数は
これは次のように書き換えることができる。
後者の和は、次の行列式に等しい。
この列はヴァンデルモンド行列式に還元され、次の式が得られる。
なお、 は、ヤング図形の各行の最初のボックスのフック長である。この式を、フック長公式で主張されている形 に変形することは、組合せ論における比較的容易な問題である： 任意の について、 であることを示せばよい。ここで、後者の積は のヤング図形の 行にある全てのセル について和をとり、 が成り立つことを示せばよい。
最長増加部分列との関連 フック長公式は、ランダムな順列における の解析においても重要な応用を持つ。 を順序 の一様ランダムな順列とすると、 をの増加部分列の最大長とし、をの期待値（平均値）とする場合、アナトリー・ヴェルシクとセルゲイ・ケロフ Vershik, A. M.; ケロフ, C. V. (1977), 「対称群のプランシェル測度の漸近挙動とヤング表の極限形」, Dokl. Akad. Nauk SSSR 233: 1024–1027、また、独立してベンジャミン・F・ローガンとローレンス・A・シェップ B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), no. 2, 206–222.は、が十分に大きいとき、はに近似的に等しいことを示した。これは、もともとスタニスラフ・ウラムが提起した疑問に対する答えである。この証明は、ロビンソン–シェンステッド対応を用いて、この問題をに従って選択されたランダムなヤング表の極限形状に関する問題へと変換することに基づいている。プランシェレル測度の定義には量 が含まれるため、フック長公式を用いて極限形状の漸近解析を行うことができ、それによって元の疑問にも答えることができる。
ヴェルシク＝ケロフとローガン＝シェップの考え方は、後にベイク・ジンホ、パーシー・ダイフト、クルト・ヨハンソンによってさらに洗練され、彼らは最大増加部分列の長さの極限挙動について、はるかに精密な解析を行うことに成功し、現在「ベイク＝ダイフト＝ヨハンソン定理」として知られる重要な結果を証明した。彼らの解析では、 にはいくつかの優れた公式が存在するという事実が再び決定的に活用されているが、フック長公式の代わりに、行列式による表現の一つが用いられた。
関連する公式 所定の形状を持つヤング表の数に関する公式は、もともと表現論に関連してフロベニウス行列式公式から導かれたものである 。ヤング図形の形状が行の長さ で与えられる場合、その形状を持つタブローの数は次式で与えられる。
フックの長さを用いることで、与えられた形状の逆平面分割の個数に対する生成関数を積の形で表すこともできる。もし が整数 の分割であるならば、 の形状を持つ逆平面分割は、ヤング図形のマスを、各行および各列に沿って和がとなり、かつ非減少となるような非負の整数で埋めることによって得られる。 フックの長さ は、ヤング表を用いて次のように定義できる。 を、形状 を持つ の逆平面分割の個数とすると、生成関数は次のように表される。
スタンレーは、この生成関数について別の公式を発見したR.P. Stanley, 「Ordered Structures and Partitions」 博士論文, ハーバード大学, 1971。一般に、 が 個の要素を持つ任意の部分順序集合であるとき、 の逆分割の生成関数は
ここで、 は、 が の自然ラベル付けの個数となるような多項式である。
分割 の場合、関係式
によって与えられるセル内の半順序集合を考慮している。
よって、自然なラベル付けとは単に標準的なヤング表、すなわち である。
フック長公式のさらに別の証明 生成関数に関する2つの公式を組み合わせると、次のようになる。
両辺は半径1の円盤内で収束し、 の場合、以下の式が成り立つ。
1を代入するのは粗雑な方法だが、右辺は単位円盤内で連続な関数で、多項式は至る所で連続なので、少なくとも次のように言える。
最後に、ロピタルの定理を n 回適用すると、フックの長さの公式が得られる。
シューア関数の特殊値 シューア関数を変数 に対応する特殊値をとると、次の式が得られる。
数 は次のように定義される。
ここで、 は共役分割である。
スキュー形状の公式 この公式には、スキュー形状に対する一般化が存在するMorales, A. H., Pak, I., and Panova, G. Hook formulas for skew shapes, arXiv:1512.08348.。
ここで、和は形状 を持つ「励起ダイアグラム」および に従って分布するボックスについてとられる。
カタラン数の公式 カタラン数は、有限組合せ論において至る所に見られる。当然、これらはこの話の一部でもある：
その理由を簡単に説明しよう。ダイック経路をたどる際、上（U）または下（D）に進むことができる。よって、長さ の任意のダイック経路について、形状 のタブローを考えます。このタブローの最初の行は、 番目のステップで上方向に進んだ数 で構成され、2行目は下方向に進んだ位置で構成されます。例えば、UUDDUD は、1行目が 125、2行目が 346 となるタブローに対応します。
フックの公式を用いると、カタラン数の閉じた公式を得る別の方法が得られる。
脚注
関連項目 ヤング図形 シューア多項式
外部リンク A published book on longest increasing subsequences by Dan Romik (PDF copy available for download). Contains discussions of the hook length formula and several of its variants, with applications to the mathematics of longest increasing subsequences.