후크 길이 공식

결합수학에서 후크 길이 공식은 형태가 주어진 영 도표인 표준 영 tableaux의 숫자에 대한 공식이다.그것은 표현 이론, 확률, 알고리즘 분석과 같은 다양한 분야에 응용을 가지고 있다. 예를 들어, 가장 오래 증가하는 부분들의 문제.관련된 공식은 슈르 다항식의 전문화인 반표준 영 tableaux의 수를 카운트한다.

정의 및 문

Let ${\displaystyle \lambda =(\lambda _{1}\geq \cdots \geq \lambda _{k})}$ be a partition of ${\displaystyle n=\lambda _{1}+\cdots +\lambda _{k}}$. It is customary to interpret ${\displaystyle \lambda }$ graphically as a Young diagram, namely a left-justified array of square cells with ${\displaystyle k}$ rows of lengths ${\displaystyle \lambda _{1},\ldots ,\lambda _{k}}$. A (standard) Young tableau of shape ${\displaystyle \lambda }$ is a filling of the ${\displaystyle n}$ cells of the Young diagram with all the integers ${\displaystyle \{1,\ldot$$각$ 행과 각 열이 증가하는 시퀀스를 형성하도록 반복이 없는 s $,n$For the cell in position ${\displaystyle (i,j)}$, in the ${\displaystyle i}$th row and ${\displaystyle j}$th column, the hook ${\displaystyle H_{\lambda }(i,j)}$ is the set of cells ${\displaystyle (a,b)}$ such that ${\displaystyle a=i}$ and ${\displayst$$yle b\geq j}$ 또는$$${\displaystyle \mathrm{or}}$ i ${\displaystyle a\geq$ i$}$ $및$ b${\displaystyle }$= ${\displaystyle j}$ ${\displaystyle b=j$후크 길이 $h{\displaystyle {}_{}}$ ${\displaystyle {\lambda }_{}}$( ${\displaystyle i}$, ${\displaystyle j}$) ${\displaystyle h_{\lambda }(i,j$)}(i,j$)$는 $H{\displaystyle {}_{}}$ ${\displaystyle {\lambda }_{}}$ ${\displaystyle {}_{}j}$) ${\displaystyle H_{\lambda }(i,j)}$에 있는 셀 수입니다$.$

후크 길이 공식은 $f{\displaystyle {}^{}}$ ${\$ $또는$ ${\displaystyle d_{}}$ {$${\$displaystyle d_{\lambda$ $\}\}\}$로 표시된$$shape의 표준 Young tableaux 수를 나타낸다.

${\displaystyle f^{\buffda }={\frac {n!}}{\prod h_{\prodda }}}(i,j)}},}$

여기서 제품은 영 다이어그램의$$ 모든 셀$({\displaystyle i}$, ${\displaystyle j}$) ${\디스플레이$ 스타일$(i,j)}$ 위에 있다.

예

$오른쪽{\displaystyle }$ 그림은 9 = 4 + 3 + 1 + 1${\displaystyle \mathrm{파티션}}$에 해당하는 영 다이어그램$display$ = ( 4, 3, 1, 1) {\displaystyle$\lambda$ = $(4,3,$1$,1)}$에 있는 셀의 후크 길이를 보여준다$.$후크 길이 공식은 다음과 같이 표준 Young tableaux의 수를 제공한다.

${\displaystyle f^{\buffda }={\frac {9!}}{7\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1\cdot 1}=216.}$

카탈로니아 번호 $C{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$은(는) $위로{\displaystyle }$ n ${\displaystyle n}$ 스텝이$$$$ 서로 $교차$하여(U) 각 스텝에서 U보다 더 앞에 D가 있는 경우가 결코 없도록 Dyck 경로를 계산한다$$.이들은 형태 $\lambda {\displaystyle }$=${\displaystyle }$( ${\displaystyle n}$, ${\displaystyle n}$) ${\displaystyle \lambda =(n,n)}$의 Young tableaux와 편향되어 있다$:$ Dyck 경로는 첫 번째 행이 U-step의 위치를 나열하는 tableau에 해당하고, 두 번째 행은 D-step의 위치를 나열한다.예를 들어 UUDDUD는 125행과 346행으로 표에 해당한다.

$이것$은 C ${\displaystyle n_{}}$= ${\displaystyle {}^{}}$( n${\displaystyle {}^{}}$, $){\$을 나타내므로 후크 공식은 잘 알려진 제품 공식에 특화되어 있다.

${\displaystyle C_{n}={\frac {(2n)!}{(n+1)(n)\cdots (3)(2)(n)(n-1)\cdots (2)(1)}}={\frac {(2n)!}{(n+1)!\,n!}}={\frac {1}{n{+}1}}{\binom {2n}{n}}.}$

역사

$f{\displaystyle {}^{}}$ ${\$ $\}\}\}$에 대한 다른 공식도 있지만, 후크 길이 공식은 특히 단순하고 우아하다.결정인자 측면에서$$ $f{\displaystyle {}^{}}$ ${\$ f$^{\lambda }}}}}$을(를) 표현하는 덜 편리한 공식은 1900년과 1902년에 각각 프로베니우스와 영에 의해 대수법을 사용하여 독립적으로 추론되었다.^[1][2]맥마흔은 1916년 영-프로베니우스 공식에 대한 대체 증거를 다른 방법을 사용하여 발견했다.^[3]

갈고리 길이 공식 자체는 1953년 Frame, Robinson, Thrall에 의해 영-프로베니우스 공식의 개선으로 발견되었다.세이건은^[4] 이 발견을 다음과 같이 설명한다.

1953년 5월 어느 목요일, 로빈슨은 미시간 주립대학의 프레임을 방문하고 있었다.스탈(로빈슨의 제자)의 작품을 논하면서 프레임은 후크 공식을 추측하게 되었다.처음에 로빈슨은 그런 간단한 공식이 존재한다는 것을 믿을 수 없었지만, 몇 가지 예를 시도해 본 후 확신하게 되었고, 함께 로빈슨은 그 정체를 증명했다.토요일에 그들은 미시간 대학에 갔고, 그곳에서 로빈슨의 강의가 끝난 후 프레임이 새로운 결과를 발표했다.이것은 그가 같은 날 같은 결과를 막 증명했기 때문에 관중석에 있던 스롤을 놀라게 했다!

후크 길이 공식의 단순함에도 불구하고 프레임-로빈슨-모든 증거는 매우 통찰력이 없고 갈고리의 역할에 대한 직관력을 제공하지 않는다.그러한 단순한 결과에 걸맞은 짧고 직관적인 설명을 찾는 것은 많은 대체 증거를 낳았다.^[5]힐만과 그라슬은 1976년 스탠리 후크-콘텐츠 공식의 특별한 사례를 증명함으로써 후크 길이 공식을 암시하는 것으로 알려져 후크의 역할을 밝히는 첫 번째 증거를 제시했다.^[6]그린, 니젠후이스, 윌프는 1979년에 후크 길이가 자연스럽게 나타나는 후크워크를 이용한 확률론적 증거를 발견했다.^[7]렘멜은 원래의 프레임을-로빈슨-로빈슨-1982년 후크 길이 공식에 대한 첫 번째 주관적 증명에 대한 증거를 모두 삽입하십시오.^[8]직접적인 주관적 증거는 1982년 프란츠블라우와 질베르거에 의해 처음 발견되었다.^[9]제일베르거는 그린-니젠후이스-도 개종했다.Wilf 훅으로 1984년에 증명된 것을 실험적인 증거에 넣는다.^[10]1992년 박과 스토야노프스키에 의해 보다 간단한 직접적 편견이 발표되었고, 그 완전한 증거는 1997년 두 쌍과 Novelli에 의해 제시되었다.^[11][12][13]

한편, 갈고리 길이 공식은 여러 가지 방법으로 일반화되었다.R. M. 스롤은 1952년 시프트 영 타코에 대한 후크 길이 공식에서 아날로그를 발견했다.^[14]Sagan은 1980년에 Shift Young Tableaux의 후크 길이 공식에 대해 시프트 후크 보행 증명서를 주었다.^[15]사간과 예는 1989년에 후크워크를 이용하여 이진수 나무의 후크 길이 공식을 증명했다.^[16]프록터는 실증적 일반화를 실시했다(아래 참조).

확률론적 증거

크누스의 휴리스틱한 주장

후크 길이 공식은 D가 제시한 다음의 휴리스틱하지만 부정확한 인수를 사용하여 직관적으로 이해할 수 있다. E. 크누스.^[17]테이블라우의 각 요소가 후크에서 가장 작고 임의로 테이블라우형을 채우는 경우, 셀$({\displaystyle i}$, j${\displaystyle }$) ${\displaystyle(i,j)}$이(가) 해당 후크의 최소 요소를 포함할 확률은 후크 길이의 역수 값이다.이러한 확률을 모든 $i{\displaystyle }$ ${\displaystyle i}$ 및$$ $j{\displaystyle }$ ${\displaystyle j}$에 곱하면 공식이 제공된다$$.그 사건들이 독립적이지 않기 때문에 이 주장은 틀렸다.

그러나 크누스의 주장은 영 탁아소의 그것과 유사한 단조로운 특성을 만족시키는 나무의 연구 결과를 열거하는 것에 대해서는 옳다.이 경우 문제의 '후크' 사건은 사실상 독립적인 사건이다.

후크워크를 이용한 확률론적 증거

이것은 C가 발견한 확률론적 증거다. 그린, A. 니젠후이스, 그리고 1979년 H. S. 윌프.^[7]정의

${\displaystyle e_{\proda }={\frac {n!}{{\prod _{(i,j)\in Y(\lambda )}h_{\lambda }}{\lambda }(i,j)}}}.}$

$우리$는 ${\displaystyle f^{}}$ ${\displaystyle {}^{}}$ = ${\displaystyle {}_{}}$ ${\displaystyle {\lambda }_{}}$ ${\$우선$,$

${\displaystyle f^{\data }=\sum _{\mu \uparrow \uparrow \f^{\mu }}}$

여기서 합계는 하나의 코너 셀을 삭제하여$$ $\lambda {\displaystyle }$ ${\displaystyle \lambda }$에서 얻은$$ 모든 Young 다이어그램 $[\displaystyle \mu }$에 걸쳐진다. (Young tableau$\lambda {\displaystyle }$ {\$displaysty \lambda$$$$}$ 형상의 최대 입력은 코너 셀 중 하나에서 발생하므로$$ 이를 삭제하면$$Young 테이블 $\mu au$가 된다.)$$

$f{\displaystyle {}^{\mathrm{}}}$∅${\displaystyle {}^{}}$= ${\displaystyle 1}$ ${\displaystyle$ f$^{\emptyset }=1$} 및$$ $e{\displaystyle {}_{}}$ ${\displaystyle {\varnothing \mathrm{}}_{}}$= ${\displaystyle 1}$ ${\displaystyle e_{\emptyset }=1}$을 정의하므로 동일한 반복을 보여주기에 충분하다$.$

${\displaystyle e_{\putda }=\sum _{\mu \uparrow \uparrow \e_{\mu }}}$

$유도로$ f ${\displaystyle {\lambda }^{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {\lambda }_{}}$ ${\$을(를) 암시할 수 있다.위의 합은 다음과 같이 적음으로써 확률의 합으로 볼 수 있다.

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

We therefore need to show that the numbers ${\displaystyle {\frac {e_{\mu }}{e_{\lambda }}}}$ define a probability measure on the set of Young diagrams ${\displaystyle \mu }$ with ${\displaystyle \mu \uparrow \lambda }$. This is done in a constructive way by defining a random walk, called the hook walk, 영 다이어그램 $cells{\displaystyle }$ ${\displaystyle \lambda$ $\}$의 셀에서, 최종적으로 $\lambda {\displaystyle }$ ${\displaystyle \$$lambda$ $}$의 코너 셀 중 하나를 선택한다($$이$$ 셀은 $μ[\displaystyle \uparrow \lambda$}).$$후크워크는 다음 규칙에 의해 정의된다.

1. ${\displaystyle \lambda }$ $displaystyle \lambda }$셀에서$$ 임의로 셀을 균일하게 선택한다.거기서 무작위로 걷기 시작해.
2. 현재 셀$({\displaystyle i}$, j${\displaystyle }$) ${\displaystyle(i,$${\displaystyle j}$$)}$의 후속은 후크 $H{\displaystyle {}_{}}$ ${\displaystyle {\lambda }_{}}$ ${\displaystyle {}_{}i}$, j${\displaystyle }$)${\displaystyle \setminus }$ {${\displaystyle }$(, ${\displaystyle i}$, j${\displaystyle }$)$$∖{\$displaysty$H_{\$lambda }(i,$j)\$setminus \{(i$,j$)\}$에서 무작위로 선택된다$.$
3. 코너 셀 $c{\displaystyle }$ ${\$에 도달할 때까지 계속하십시오$.$

제안:$\lambda {\displaystyle }$ ${\displaystyle \lambda }$의 지정된 코너 셀${\displaystyle (,}$ ${\displaystyle b}$) ${\displaystyle(a,b)}$에 대해$,$

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

여기서 $\mu {\displaystyle }$= ${\displaystyle \lambda }$ ${\displaystyle \setminus \{}$( ${\displaystyle a}$ ,${\displaystyle }$b${\displaystyle }$) ${\displaystyle \}}$ ${\displaystyle \mu =\lambda \setminus \{(a,b$

이를 감안할 때, 모든 코너 셀$({\displaystyle a}$,${\displaystyle b}$ ) ${\displaystyle (a,b)}$을 합하면$$ 주장대로${\displaystyle \underset{}{}}$μ ${\displaystyle \underset{}{\mu }}$μ μ ${\displaystyle \underset{}{}\frac{{}_{}}{}}$ e ${\displaystyle \frac{{\mu }_{}}{{}_{}}\frac{{}_{}}{{}_{}}}$ e ${\displaystyle \frac{{\mu }_{}}{}}$ = ${\displaystyle 1}$ ${\displaystyle \sum \\\\mu$ \$uparrow \lambda }{\frac {e_${\lambda$}}}}}}}}}}}{\lambda }}}}}=1$}.

대칭 그룹의 표현에 대한 연결

후크 길이 공식은 대칭군 ${\displaystyle {Sn}_{}}$ ${\$의 표현 이론에서 매우 중요한데$,$ 여기서 f ${\displaystyle {\lambda }^{}}$ ${\$은(는) ${$ {\$d$}과$$(와) 연관된 복합적 무적 표현 $V{\displaystyle {}_{}}$ ${\$}의$$치수와 동일하다고 알려져$$ 있다.$isplaystyle \lambda$ $\}.$

상세토론

대칭 그룹의$$ 복잡하고 수정 불가능한 표현 $V{\displaystyle {}_{}}$ ${\$은(는) $n{\displaystyle }$ ${\displaystyle n}$의 파티션 ${\displaysty \lambda }$에 의해 인덱싱된다($$Specht 모듈 참조).이들의 성격은 홀 내부를 통한 대칭함수 이론과 관련이 있다.

${\displaystyle \chi ^{\patchda }}=\langles s_{\langleda },p_{\tau(w)}\angle ,}$

where ${\displaystyle s_{\lambda }}$ is the Schur function associated to ${\displaystyle \lambda }$ and ${\displaystyle p_{\tau (w)}}$ is the power-sum symmetric function of the partition ${\displaystyle \tau (w)}$ associated to the cycle decomposition of ${\displaystyle w}$. For example, $w{\displaystyle }$=${\displaystyle }$( ${\displaystyle 154}$)${\displaystyle }$( ${\displaystyle 238}$$)$${\displaystyle }$( 6${\displaystyle }$) ${\displaystyle (79}$) ${\displaystyle$ w$=(lit)(238)(6))}$인 경우, ${\displaystyle \tau }$( w )${\displaystyle }$=${\displaystyle }$(${\displaystyle 3}$, ${\displaystyle 3}$,${\displaystyle }$2,${\displaystyle 1}$) ${\display$ style $\tau (w)=(3,3,$2$,1$

Since the identity permutation ${\displaystyle e}$ has the form ${\displaystyle e=(1)(2)\cdots (n)}$ in cycle notation, ${\displaystyle \tau (e)=(1,\ldots ,1)=1^{(n)}}$, the formula says

${\displaystyle f^{\lambda }\,=\,\dim V_{\\lambda }\,=\,\chi^{\lambda }(e)\,=\,\langles s_{p_{1^{1(n)}}\angle }}}$

단일 대칭함수의 관점에서 Schur 함수의 확장은 Kostka 숫자를 사용한다.

${\displaystyle s_{\lambda }=\sum _{\mu }K_{\lambda \m_{\mu }}}}}$

Then the inner product with ${\displaystyle p_{1^{(n)}}=h_{1^{(n)}}}$ is ${\displaystyle K_{\lambda 1^{(n)}}}$, because ${\displaystyle \langle m_{\mu },h_{\nu }\rangle =\delta _{\mu \nu }}$. Note that ${\displaysty$$le K_{\lambda 1^{(n)}}}$ is equal to ${\displaystyle f^{\lambda }=\dim V_{\lambda }}$, so that ${\displaystyle \textstyle \sum _{\lambda \vdash n}\left(f^{\lambda }\right)^{2}=n!}$ from considering the regular representation of ${\displaystyle S_{n}}$, or com로빈슨-스헨스테드-크누스 서신에서 바이너레이션으로.

이 계산은 또한 다음과 같은 것을 보여준다.

${\displaystyle(x_{1}+x_{2}+\cdots +x_{k}}}^{n}=\sum _{\data \vdash n}s_{\f^{\f^{\cda }}}}}}$

$⟨{\displaystyle }$ ${\displaystyle {}_{}}$${\displaystyle {{}^{}}_{}}$${\displaystyle {\mu }_{}}$ ${\displaystyle {}_{}{\nu }_{}}$ =${\displaystyle {}_{}}$ μ μ, δ = Δ ${\displaystyle {\mu }_{}}$ {\$displaystyle \langle s_{\nu }}\rangele$ = $\delta _{\mu \nu$ \delta _$${\delta \\${\displaystyle {{\mathrm{nu}}^{}}_{}}$ \nu \$nu$$\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}\}.$위의 동등성은 또한 양쪽에서 각 단원형의 계수를 확인하고 로빈슨-스헨스테드-크누스 통신문을 사용하거나, 보다 개념적으로 $V{\displaystyle {}^{}}$ ${\displaystyle {\otimes n}^{}}$ ${\$ V$^{\otimes n}$을(를) 수정할 수 없는 ${\displaystyle G}$ L ${\displaystyle (V)}$ ${\displaysty GL(V)}$ 모듈에$$ 의해$$ 분해된 것을 보고 문자를 가져가는 것도 증명할 수 있다.슈르-와일 이중성을 참조하십시오.

프로베니우스 공식을^[18] 사용한 후크 공식 증명

위와 같은 고려사항

${\displaystyle p_{1^{(n)}}=\sum _{\bdash n}s_{\f^{\f^da }}}}}}}}\sum _{\data }}}}}}}}}}}$

하도록

${\displaystyle \Delta (x)p_{1^{(n)}}=\sum _{\lambda \vdash n}\Delta (x)s_{\lambda }{}f^{\lambda }}}}}}}}}}}}}}}}:$

여기서 )= < (x - ) ${\displaystyle \Delta (x)=\prod _{i}(x_{i}-x_{j}}}}$는 Vandermonde 결정 요인이다.

For the partition ${\displaystyle \lambda =(\lambda _{1}\geq \cdots \geq \lambda _{k})}$, define ${\displaystyle l_{i}=\lambda _{i}+k-i}$ for ${\displaystyle i=1,\ldots ,k}$. For the following we need at least as many variables as rows in the partition, so from이제 $n{\displaystyle }$ ${\displaystyle n}$ 변수$$ x ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}\cdots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$을(를) 사용하여 작업한다$.$

각 용어 $\Delta {\displaystyle \mathrm{}}$( ${\displaystyle x}$) ${\displaystyle {}_{}}$ ${\displaystyle {\lambda }_{}}$ ${\$은 다음과$$ 같다.

${\displaystyle a_{(\lambda_{1}+k-1,\lambda_{2}+k-2,\dots ,\lambda_{k})}(x_{1},x_{2},x_{k},\dots)\ =\\det\!\left는 경우에는{\begin{행렬}x_{1}^{l_{1}}&x_{2}^{l_{1}}&\dots &, x_{k}^{l_{1}}\\x_{1}^{l_{2}}&x_{2}^{l_{2}}&\dots &, x_{k}^{l_{2}}\\\vdots &, \vdots &, \ddots &, \vdots \\x_{1}^{l_{k}}&x_{2}^{l_{k}}&\dots &, x._{k}^{l_{k}}\end{매트릭스}}\right]}$

(슈르 함수 참조)Since the vector ${\displaystyle (l_{1},\ldots ,l_{k})}$ is different for each partition, this means that the coefficient of ${\displaystyle x_{1}^{l_{1}}\cdots x_{k}^{l_{k}}}$ in ${\displaystyle \Delta (x)p_{1^{(n)}}}$, denoted ${\displaystyle {[\mathrm{\Delta }(}_{}}$${\displaystyle \left[\Delta (x)p_{1^{(n)}}\right]_{l_{1},\cdots ,l_{k}}}$, is equal to ${\displaystyle f^{\lambda }}$. This is known as the Frobenius Character Formula, which gives one of the earliest proofs.^[19]

그것은 단지 이 계수를 단순화시키기 위해 남아있다.곱하기

${\displaystyle \Delta (x)\\\sum _{w\in S_{n}\operatorname {sgn}(w)x_{1}^{w(1)-1x_{2}^{w(2)-1}\cdots x_{k(k)-1}^{w(k)-11}$

그리고

${\displaystyle p_{1^{(n)}\\(x_{1}+x_{2}+\cdots +x_{k}}^{n}\\\\sum {\frac {n!}{d_{1}!d_{2}!\cdots d_{k}!}}}x_{1}^{d_{1}x_{2}^{d_{2}}\cdots x_{k}^{d_{k}}}}}}}$

우리는 우리의 계수를 다음과 같이 결론짓는다.

${\displaystyle \sum _{w\in S_{n}}\operatorname {sgn}(w){\frac {n!}{{(l_{1}-w(1)+1)!\cdots (l_{k}-w(k)+1)!}}}$

라고 쓸 수 있는.

$디스플레이 스타일 {\frac {n!}{l_{1}!l_{2}!\cdots l_{k}!}}\sum _{w\in S_{n}}\operatorname {sgn}(w)\left[(l_{1})(l_{1}-1)\cdots (l_{1}-w(1)+2)\right]\left[(l_{2})(l_{2}-1)\cdots (l_{2}-w(2)+2)\right]\left[(l_{k})(l_{k}-1)\cdots (l_{k}-w(k)+2)\right]}$

후자의 합은 다음의 결정요인과 같다.

${\displaystyle \det \left[{\begin{matrix}1&l_{1}&l_{1}(l_{1}-1)&\dots &\prod _{i=0}^{k-2}(l_{1}-i)\\1&l_{2}&l_{2}(l_{2}-1)&\dots &\prod _{i=0}^{k-2}(l_{2}-i)\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&l_{k}&l_{k}(l_{k}-1)&\dots &\prod _{i=0}^{k-2}(l_{k}-i)\end{matrix}}\right]}$

어떤 열이 반데르몬드 결정요소로 감소하면 공식을 얻을 수 있다.

${\displaystyle f^{\buffda }={\frac {n!}{l_{1}!\,l_{2}!\cdots l_{k}!}}}\prod _{i<j}(l_{i}-l_{j}).}$

$l{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$는 영 다이어그램의 각 행에 있는 첫 번째 상자의 후크 길이이며, 이 표현은 원하는 $형식{\displaystyle \frac{}{}}$ n${\displaystyle \frac{!}{}}$ ${\displaystyle \frac{}{}}$ h ${\displaystyle \frac{{\lambda }_{}}{}}$(${\displaystyle \frac{i}{}}$, ${\displaystyle \frac{j}{}}$) ${\$$}}{\prod h_{\prodda }}($$,j$ : =j > ( - ) j i ) ${\$$=\prod _{j}i}(l_{i}-l_{j})\cdot \prod _{j\leq \lambda$ $_$${i}h_{\lambda }}{\$lambda }($i,j$ 여기서 후자의 제품은 영 $다이어그램$의 i {\$d.$

가장 길어지는 부분과의 연결

또한 후크 길이 공식은 무작위 순열에서 가장 오래 증가되는 부분들의 분석에 중요한 응용이 있다.If ${\displaystyle \sigma _{n}}$ denotes a uniformly random permutation of order ${\displaystyle n}$, ${\displaystyle L(\sigma _{n})}$ denotes the maximal length of an increasing subsequence of ${\displaystyle \sigma _{n}}$, and ${\displaystyle \ell _{n}}$ denotes the expected (평균) $L{\displaystyle }$ ($){\displaystyle$ L$(\sigma _{n$ 아나톨리 베르쉬크 및 세르게이 케로프 및 독립적으로 벤자민 F의 값.로건과 로렌스 A.Shepp는^[21] $n{\displaystyle }$ ${\displaystyle n}$이(가) 클 때 ${\displaystyle {\ell n}_{}}$ ${\$이(가) 대략 ${\displaystyle 2n\sqrt{}}$ ${\$ 2${\sqrt{n}$과(와) 같다는$$ 것을 보여주었다$.$이것은 스타니슬라브 울람이 원래 제기했던 질문에 대한 대답이다.그 증거는 로빈슨-스켄스테드 서신을 통해 질문을 플랑쉐렐 측정에 따라 선택된 임의의 영 테이블라우의 제한된 모양에 관한 문제로 번역하는 것에 기초한다.Planchel 측정의 정의는 수량 f ${\$을 포함하므로$,$ 후크 길이 공식을 사용하여 한계 형상의 점증적 분석을 수행하고 그에 따라 원래의 질문에 대답할 수 있다.

Vershik-Kerov와 Logan의 아이디어들셰프는 이후 진호 백, 퍼시 디프트, 커트 요한슨에 의해 정제되었는데, 그는 현재 백-디프트-요한슨 정리라고 알려진 중요한 결과를 증명하면서 최대 증가 부분 길이의 제한 행동을 훨씬 더 정밀하게 분석할 수 있었다.그들의 분석은 비록 후크 길이 공식 대신에 결정적 표현식 중 하나를 사용하였지만, $f{\displaystyle {}^{}}$ ${\displaystyle {\lambda }^{}}$ ${\$ f$^{\lambda }}}$은(는) 여러 가지 좋은 공식을 가지고$$ 있다는 사실을 다시 한번 결정적인 활용을 한다.

관련 공식

$\lambda {\displaystyle }$ ${\displaystyle \lambda }$ 형상의 Young tableau 숫자에 대한 공식은 원래 표현 이론과 관련하여 프로베니우스 결정요인 공식에서 유래되었다$$.^[22]

${\displaystyle f(\lambda _{1},\ldots ,\lambda _{k})={\frac {n!\,\Delta (\lambda _{k},\lambda _{k-1}+1,\ldots ,\lambda _{1}+k-1)}{\lambda _{k}!\,(\lambda _{k-1}+1)!\cdots (\cdda _{1}+k-1)!}}.}$

후크 길이는 또한 특정 형상의 역면 파티션 수에 대한 생성 기능에 대한 제품 표현을 제공하는 데 사용될 수 있다.^[23]λ이 일부 정수 p의 분할인 경우, 영 다이어그램의 상자에 n에 항목이 추가되고 각 행과 각 열을 따라 감소되지 않는 비음수 정수로 채워 n의 역면 분할을 얻는다.후크 길이 ${\displaystyle {h\mathrm{}}_{}}$ 1,${\displaystyle }$… ,${\displaystyle }$h ${\displaystyle p_{}}$ ${\$는 영 tableaux와 같이 정의할 수 있다$$.π가_n n의 역면 파티션 수를 형상 λ으로 나타내면 생성 함수는 다음과 같이 기록할 수 있다.

${\displaystyle \sum \{n=0}^{\infit }\pi _{n}x^{n}=\pod _{k=1}^{p}(1-x^{h_{k}}}})^{-1}:{-1}$

스탠리는 동일한 생성함수에 대한 또 다른 공식을 발견했다.^[24]$일반적$으로 $A{\displaystyle }$ ${\displaystyle A}$이(가) n ${\displaystyle n}$ 요소를$$ 포함하는 포셋인 경우 역 $A{\displaystyle }$ ${\displaystyle A}$ -파티션에$$ 대한 생성 함수는

${\displaystyle {\frac {P(x)}{{(1-x^{2})\cdots(1-x^{n})}}}$

여기서 $P{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle P(x)}$은 $P{\displaystyle }$ ( 1 ) ${\displaystyle$ P(1$)}이(가$$)$ $A{\displaystyle }$ {\$displaystyle A}$의 선형 확장 수입니다$$$.$

파티션 ${\displaystyle \lambda }$의 경우$,$ 우리는 관계가 부여한 셀의 포셋을 고려하고 있다.

${\displaystyle (}$ ${\displaystyle i}$, ${\displaystyle j}$ )${\displaystyle \le }$ (${\displaystyle }$i${\displaystyle {}^{}}$, ${\displaystyle {}^{}}$ )${\displaystyle ⟺}$ ${\displaystyle i{\prime }^{}}$ ${\displaystyle \text{및}}$ ${\displaystyle {}^{}}$ ≤ ${\displaystyle j{}^{}}$ ${\displaystyle {\prime }^{}}$ { { { { { ${$ {\$displaystyle (i,j)\leq (i',j')\iff i\leqqqquad$ {$and}\qquad j\leq$

그래서 선형연장은 단순히 표준 Young tableau, 즉 $P{\displaystyle }$( ${\displaystyle 1}$)${\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle {\lambda }^{}}$ ${\$ P$(1)=f^{\lambda }}}}}}}$에 불과하다.

스탠리의 공식을 사용한 후크 공식 증명

생성 함수에 대한 두 공식을 결합하여

${\displaystyle {\frac {P(x)}{{(1-x^{2})\cdots(1-x^{n})}}}=\prod _{(i,j)\in \{{-x^{h_{(i,j)}}^{-1}$

양쪽이 반지름 1의 디스크 내부에 수렴되고 다음 은 < 1 ${\displaystyle$ x $<1}$에 대해 타당하다.

${\displaystyle P(x)={\frac {\prod _{k=1}^{n}(1-x^{k})}{\prod _{(i,j)\in \lambda }(1-x^{h_{(i,j)}}}}}}}}}}}}.}$

1번 플러그를 꽂으면 폭력적이겠지만, 오른손은 유닛 디스크 내부의 연속적인 기능이고, 다항식이 도처에 연속되어 있어서 적어도 우리는 말할 수 있다.

${\displaystyle P(1)=\lim _{x\to 1}{\frac {\prod}{n1}^{n(1-x^{k})}{\prod _{(i,j)}{\lambda }(1-x^{h_{(i,j)}}}}}}}}}}.}$

L'Hepital의 $규칙{\displaystyle }$ n ${\displaystyle n}$을(를) 곱하면$$ 후크 길이 공식이 생성됨

${\displaystyle P(1)={\frac {n!}}{\prod _{(i,j)\in \lambda }h_{(i,j)}}}}}.}$

반표준 테이블aux 후크 길이 공식

The Schur polynomial ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{k})}$ is the generating function of semistandard Young tableaux with shape ${\displaystyle \lambda }$ and entries in ${\displaystyle \{1,\ldots ,k\}}$. Specializing this to ${\displaystyle x_{i}=1$$}$은(는) 후크 길이로 작성할 수 있는 반표준 테이블aux의 수를 제공한다$$.

${\displaystyle s_{\lambda }(1,\ldots,1)\\\\\prod_{(i,j)\in \mathrm {Y}(\lambda ){\frac {k-i+j}{h_{\lambda,}}}.}$

The Young diagram ${\displaystyle \lambda }$ corresponds to an irreducible representation of the special linear group ${\displaystyle \mathrm {SL} _{k}(\mathbb {C} )}$, and the Schur polynomial is also the character of the diagonal matrix ${\displaystyle \mathrm {diag} (x_{1$이 표현에 대해$$ 동작하는 $},\ldots,$x_{$k}.$따라서 위의 전문화는 불가해한 대표성의 차원이며, 공식은 보다 일반적인 Weyl 치수 공식에 대한 대안이다.

$변수$ $1{\displaystyle \mathrm{}}$,$t,$ ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$,$t$에 있는 $슈르$ 함수의 주요 전문화를 통해 이를 세분화할 수 있다$.$

${\displaystyle s_{\data }(1,t,t^{2},\ldots )\\\\\\\\\\frac {t^{n\left(\data \오른쪽)}}{{\prod_{(i,j)\in Y(\lambda )}}(1-t^{h_{\lambda }}}}},},}$

where ${\displaystyle n(\lambda )=\sum _{i}(i{-}1)\lambda _{i}=\sum _{i}{\tbinom {\lambda _{i}'}{2}}}$ for the conjugate partition ${\displaystyle \lambda '}$.

꼬치형 수식

꼬치모양에 대한 이 공식의 일반화가 있다.

${\displaystyle s_{\lambda /\mu }(1,t,t^{2},\cdots )=\sum _{S\in E(\lambda /\mu )}\prod _{(i,j)\in \lambda \setminus S}{\frac {t^{\lambda _{j}'-i}}{1-t^{h(i,j)}}}}$

여기서 합계는 $[\displaystyle \lambda }$ 형상의$$ 흥분된 도표와 $[\displaystyle \mu$}에 따라 분배된 박스의 합을 이어받는다$.$

d-완전한 포지션에 대한 일반화

Poset $N{\displaystyle \mathbb{}}$ ${\displaystyle \times }$ ${\displaystyle N\mathbb{}}$ ${\$ 표준 Young tableau는 선형 확장자로 간주할 수 있다.로버트 프록터는 나무와 꼬치 도표를 일반화하는 더 큰 종류의 포셋의 선형 확장을 계산하기 위해 후크 길이 공식의 일반화를 실시했다.^[26][27]

참조

외부 링크

• Dan Romik의 가장 오랫동안 증가하는 수학의 놀라운 수학.후크 길이 공식과 그 변형 중 몇 가지에 대한 논의를 포함하며, 가장 긴 반복 반복수치의 수학에 응용한다.