로빈슨-스헨스테드 통신

수학에서 로빈슨-스켄스테드 서신은 같은 모양의 표준 영 표고 쌍과 순열 사이의 주관적 서신이다.다양한 묘사를 가지고 있는데, 모두 알고리즘적인 성질을 가지고 있고, 많은 주목할 만한 특성을 가지고 있으며, 조합학이나 표현 이론과 같은 다른 분야에도 응용이 있다.이 서신은 특히 크누스에 의해 로빈슨-스헨스테드-크누스 통신으로 알려진 것에 대한 일반화, 그리고 젤레빈스키의 사진에 대한 일반화 등 여러 면에서 일반화되었다.

서신에 대한 가장 간단한 설명은 특정 규칙에 따라 순열 값을 연속적으로 삽입하여 하나의 표고를 구성하는 절차인 Scensted 알고리즘(Schensted 1961)을 사용하는 것이며, 다른 표고는 시공 중 도형의 진화를 기록하는 절차다.이 서신은 로빈슨(로빈슨 1938)이 리틀우드-리처드슨 지배를 증명하기 위해 훨씬 앞서 다소 다른 형태로 서술한 것이었다.비록 로빈슨이 사용한 절차는 스헨스테드-알고리즘과 근본적으로 다르며 거의 완전히 잊혀지지만, 서신은 종종 로빈슨-스헨스테드 알고리즘이라고 불린다.대응관계를 정의하는 다른 방법으로는 주 드 타킨의 측면에서 비결정론적 알고리즘이 있다.

서신의 편향적 성격은 그것을 열거적 정체성과 관련시킨다.

\sum _{\lambda \in {\mathcal{P}_{n}(t_{\lambda }})^{2}=n!

여기서 ${\mathcal {P}}_{n}$ ${\mathcal {P}}_{n}$ ${\$ 는 $n$ ( $또는$ n제곱이 있는 영 다이어그램)의 파티션 집합을 나타내며 ${\mathcal {P}}_{n}$ , 표준 Young tableaux of shape의 $수$ 를 $나타낸다 λ$ .

스헨스테드 알고리즘

스헨스테드 알고리즘은 2행 표기법으로 작성된 순열 $σ$ 에서 시작한다.

\pmatrix}{\pmatrix}1&3&\cdots &n\\n\\cdma _{2}&\cdma _{3}\cdots &\nd{pmatrix}}}}}

여기서 $σ i$ = $σ (i)$ 이며, 같은 모양의 (중간) 순서의 영 tableaux 쌍을 순차적으로 구성하여 진행한다.

{\displaystyle(P_{0},Q_{0}),(P_{1},Q_{1}),\ldots ,(P_{n},Q_{n}),}

$여기$ 서₀ P = $Q$ 는₀ 빈 테이블이다.출력표 $aux$ 는_n P = P, $Q$ = $Q$ 이다_n. $P$ 가_i−1 $생성$ 되면_i−1 P에 $σ$ 을_i 삽입하여 $P$ 를_i 형성하고, 삽입에 의해 형상에 추가된 사각형의 $Q$ 에_i−1 entry $i$ 를 추가하여 $Q$ 를_i 형성한다( $P$ 와_i $Q$ 가_i 모든 $i$ 에 대해 동일한 형상을 갖도록 함).Tableaux $Q$ 의_i 보다 수동적인 역할 때문에, 출력물의 일부분이고 이전의 $Q$ 를_i 쉽게 읽어내는 마지막 $Q$ 를_n 기록 Tableau라고 부른다. 반대로 Tablea $P$ 는_i 삽입 Tableau라고 부른다.

삽입

(4)의 삽입:
• (4) 첫 번째 행에서 (5) 교체
• (5) 2열에서 (8) 교체
• (8) 세 번째 행 작성

각 $σ$ 을_i 삽입하는 데 사용되는 기본 절차를 스헨스테드 삽입 또는 행 삽입(column-insertion이라는 변형 절차와 구별하기 위해)이라고 한다.그것의 가장 간단한 형태는 "불완전한 표준 테이블보"의 관점에서 정의된다. 표준 테이블보처럼 그들은 증가하는 행과 열을 형성하면서 뚜렷한 항목을 가지고 있지만, 일부 값들은 (여전히 삽입되어야 한다) 항목으로 존재하지 않을 수 있다.이 절차는 $T$ 의 입력으로 존재하지 않는 tableau $T$ 와 값 $x$ 와 같은 인수로 간주된다; 그것은 $T$ ← $x$ 를 나타내는 새로운 tableau와 그것의 모양이 성장한 제곱 $s$ 를 출력하는 것으로 생산된다. $x$ 값은 T $t$ $x$ 의 첫 번째 행에 나타나며, 끝에 추가되거나( $x$ 보다 큰 항목이 없는 경우), $T$ 의 첫 번째 행에서 첫 $번째$ $항목$ y > x를 대체한다.전자의 $경우$ s는 $x$ 가 추가되고 삽입이 완료된 사각형이며, 후자의 경우 교체된 $항목$ y를 $T$ 의 두 번째 줄 등에 유사하게 삽입하여 어느 단계에서 첫 번째 사례가 적용될 $때$ 까지(T의 빈 줄에 도달하면 확실히 발생한다.

좀 더 형식적으로, 다음의 유사코드는 새로운 값 $x$ 의 행 삽입을 $T$ 에 기술한다.^[1]

$i$ = $1$ 과 $j$ 를 $T$ 의 첫 번째 행의 길이보다 한 개 더 긴 값으로 설정한다.
$j$ > $1$ 과 x < $T$ 는_{i, j−1} 줄이되 $j$ 는 줄이시오.(지금 ( $i,$ j $)$ 는 $t$ 에서 $x$ 보다 크거나 아예 들어가지 않는 항목으로 $i행$ 의 첫 번째 제곱이다.)
정사각형 $(i,$ $j)$ 이 T에서 비어 있는 경우, 정사각형 $(i,$ $j)$ 의 $T$ 에 $x$ 를 추가하고 $s$ = $(i,$ $j$ )를 설정한 후 종료한다 $.$
$x$ 와 $T i, j$ 값을 교환한다(이것은 기존 $x$ 를 $i행$ 으로 삽입하고, 다음 행에 삽입하기 위해 대체하는 값을 저장한다).
$i$ 를 1씩 증가시키고 2단계로 돌아가십시오.

$T$ 의 모양은 정확히 하나의 정사각형, 즉 $s$ 로 자란다.

정확성

$T$ ← $x$ 에 행과 열이 증가한다는 사실은, $T$ 에 대해 동일한 것이 유지되는 경우, 이 절차로부터 명확하지 않다(동일한 열의 항목은 비교조차 되지 않는다).그러나 그것은 다음과 같이 볼 수 있다.4단계 직후를 제외하고 항상 사각형 $(i,$ j $)$ 이 $T$ 에서 비어 있거나 $x$ 보다 큰 값을 가지고 있으며, 5단계에서는 ( $i,$ $j)$ 가 $T$ 에 원래 $x$ 가 포함된 사각형 바로 아래의 사각형이기 때문에 이 속성을 다시 설정한다.따라서 4단계에서 $T값$ 에_{i, j} 대한 교체의 효과는 그것을 더 작게 만드는 것이다. 특히 그것은 오른쪽이나 아래쪽 이웃보다 커질 수 없다.반면에 새 값은 방금 2단계를 종료한 비교에 의해 보장되는 왼쪽 이웃(있는 경우) 이상도 이하도 아니다.마지막으로 새 값이 있는 경우 상부 인접 $T$ 보다_{i−1, j} 큰지 확인하려면 5단계 이후 $T$ 가_{i−1, j} 유지되고 2단계에서 $j$ 가 감소하면 해당 값 $T$ 만_{i−1, j} 감소한다는 점을 관찰하십시오.

Tableaux 구성

순열 $σ$ 에 적용된 전체 스헨스테드 알고리즘은 다음과 같이 진행된다.

$P$ 와 $Q$ 를 모두 빈 테이블au로 설정
$1$ 에서 n까지 $증가$ 하는 i의 경우 삽입 절차에 의해 $P$ ← $σ$ 과_i 제곱 $s$ 를 계산한 다음 $P$ ← $σ$ 으로_i 교체하고 항목 $i$ 를 제곱 $s$ 의 테이블au $Q$ 에 추가한다.
종료하고 페어 $(P,$ Q $)$ 를 반환한다.

이 알고리즘은 표준 Young tableaux 한 쌍을 생산한다.

시공의 역직성

같은 모양의 표준 영 tableaux의 어떤 쌍 $(P,$ $Q)$ 을 주어 스헨스테드 알고리즘에 의해 ( $P,$ $Q)$ 를 발생시키는 역순화를 생성하는 과정이 있음을 알 수 있다.그것은 본질적으로 알고리즘의 역추적 단계들로 $구성$ 되는데, 매번 Q의 항목을 사용하여 역삽입이 시작되어야 하는 정사각형을 찾고, $P$ 의 해당 입력을 앞의 행으로 이동하며, 첫 번째 행의 입력이 교체될 때까지 행을 통해 위쪽으로 계속되는데, 이것은 대응에서 삽입되는 값이다.시공 알고리즘의 ng 단계.이 두 개의 역 알고리즘은 한 쪽에 $n$ 의 순열과 다른 쪽에 $n개$ 의 정사각형을 포함하고 동일한 모양의 표준 Young tableaux 쌍 사이의 주관적 일치성을 정의한다.

특성.

알고리즘 구조에서는 분명하지 않지만 가장 근본적인 특성 중 하나는 대칭이다.

로빈슨-스헨스테드 통신문이 표고 $(P,$ Q $)$ 를 순열 $σ$ 에 연관시키면, $역순열$ $σ$ 에⁻¹ 연관시킨다 $.$

예를 들어, 이것은 비엔노트의 기하학적 구조에 호소함으로써 증명될 수 있다.

추가 속성, 모두 통신문이 표고 $($ $P 1$ $,$ Q $)$ 를 순열 = = ( (, $...,$ $σ n)$ 와 연관시킨다고 가정한다.

역순열 $(σ n,$ ..., $σ 1$ )과 관련된 테이블au $(P,, Q$ $')$ 쌍에서 $테이블au$ P는 테이블au $P$ 의 전치물이며, $Q'$ 는 $P$ (명칭 슈첸베르거가 비자발적으로 $Q$ 로부터 얻은 테이블au의 전치물)과 독립하여 $Q$ 가 결정한 테이블au이다.
$σ 1, ...,$ $σ$ 의_n 최장 증가 부분열 길이는 $P$ ( $및$ Q)의 첫 번째 행의 길이와 같다.
$σ 1, ...,$ $σ$ 의_n 가장 긴 감소 반복의 길이는 앞의 두 속성에서 다음과 같이 $P$ 의 첫 $번째$ 열(및 Q)의 길이와 같다.
$σ$ 의 하강 집합 { $i$ : $σ i$ > $σ i +1$ }은 하강 집합 { $i$ : $i +1$ 이 $Q$ 의 $i$ } 행 $아래 일렬로 있다$ .
지수 집합으로 $π$ 의 반복을 확인한다.그린의 정리로서, $어떤$ k $1$ 1에 대해서도, $증가$ 된 부분들의 조합으로 쓰일 수 있는 가장 큰 집합의 $크기$ 는₁ $+ +$ … + $λ k$ . 특히 $λ$ 은₁ $증가$ 하는 부분 중 가장 큰 길이와 같다.
$σ$ 이 비자발적인 경우, $fixed$ 의 고정점수는 $λ$ 의 홀수 길이의 열 수와 같다.

참고 항목

비엔노트의 기하학적 구조로, 서신을 도식적으로 해석할 수 있다.
Plactic monoid: 삽입 프로세스를 사용하여 1과 $n$ 사이의 항목과 영 tableaux의 연관 제품을 정의할 수 있으며, 이를 순서 $n$ 의 Plactic monoid라고 한다.

메모들

^ 적응 대상D. E. Knuth (1973), The Art of Computer Programming, vol. 3, pp. 50–51

참조

Fulton, William (1997), Young Tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, ISBN 978-0-521-56144-0, MR 1464693.
Knuth, Donald E. (1970), "Permutations, matrices, and generalized Young tableaux", Pacific Journal of Mathematics, 34: 709–727, doi:10.2140/pjm.1970.34.709, MR 0272654
Robinson, G. de B. (1938), "On the Representations of the Symmetric Group", American Journal of Mathematics, 60 (3): 745–760, doi:10.2307/2371609, JSTOR 2371609, Zbl 0019.25102.
Sagan, B. E. (2001), The Symmetric Group, Graduate Texts in Mathematics, vol. 203, New York: Springer-Verlag, ISBN 0-387-95067-2.
Schensted, C. (1961), "Longest increasing and decreasing subsequences", Canadian Journal of Mathematics, 13: 179–191, doi:10.4153/CJM-1961-015-3, MR 0121305.
Stanley, Richard P. (1999), Enumerative Combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, ISBN 978-0-521-56069-6, MR 1676282.
Zelevinsky, A. V. (1981), "A generalization of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence", Journal of Algebra, 69 (1): 82–94, doi:10.1016/0021-8693(81)90128-9, MR 0613858.

추가 읽기

Green, James A. (2007). Polynomial representations of GL_n. Lecture Notes in Mathematics. Vol. 830. With an appendix on Schensted correspondence and Littelmann paths by K. Erdmann, J. A. Green and M. Schocker (2nd corrected and augmented ed.). Berlin: Springer-Verlag. ISBN 3-540-46944-3. Zbl 1108.20044.

외부 링크

van Leeuwen, M.A.A. (2001) [1994], "Robinson–Schensted correspondence", Encyclopedia of Mathematics, EMS Press
윌리엄스, L. 로빈슨-스헨스테드 알고리즘의 인터랙티브 애니메이션

[1] 적응 대상D. E. Knuth (1973), The Art of Computer Programming, vol. 3, pp. 50–51

[1]

Search