Young Tableau, RSK Correspondence

Young Tableau Diagram, Young 도형, RSK Correspondence, Robinson-Schensted-Knuth

정의

Young Diagram 은 행마다 길이가 단조 감소 하는 칸들의 배열 (왼쪽 위 정렬). Young Tableau 는 그 칸에 1..n 을 채워 넣은 것 중 행과 열 모두 증가 하는 것 (Standard Young Tableau, SYT).

RSK Correspondence (Robinson-Schensted-Knuth) 는 순열 ↔ 같은 모양 (shape) 의 SYT 쌍 (P, Q) 사이의 전단사. PS 에서 LIS / LDS / 순열의 chain 분해 같은 통계를 한 자료구조로 환원.

문제 상황과 동기

순열의 LIS 길이는 DP 로 O(n log n) 이지만, “disjoint LIS k 개의 최대 총 길이” 같은 확장 질문은 naive greedy 로 불가능. RSK 는 순열을 SYT 쌍으로 전단사 시킴으로써 그런 통계를 tableau shape 의 기하 로 바꾼다.

Schensted 정리: RSK 로 만든 P 의 첫 행 길이 = LIS, 첫 열 길이 = LDS. Greene 정리: 처음 k 행 길이 합 = disjoint increasing 부분수열 k 개의 최대 총 길이.

이 구조는 순열 통계를 기하 문제 로 환원하고, SYT 개수 카운팅 (hook length formula), 표현론과도 연결되어 PS / 조합론 양쪽에서 핵심. Young tableau 없이 이런 문제를 풀 방법은 거의 없다.

시각화

핵심 사실

Schensted 정리

순열 π 에 RSK 를 적용해 얻은 SYT 의 첫 번째 행의 길이 = LIS(π). 첫 번째 열의 길이 = LDS(π).

Greene 정리 (일반화)

P-tableau 의 처음 k 행 길이 합 = π 의 서로소 increasing 부분수열 k 개의 최대 길이 합.

Hook Length Formula

shape λ 의 SYT 개수 = n! / Π_{cell} hook_length(cell).

구현

RSK insertion (full implementation)

// O(N√N) RSK insertion (순열 -> (P, Q) SYT 쌍)
#include <vector>
#include <algorithm>
using namespace std;

using Tableau = vector<vector<int>>;

// Binary search bump: P[row] 에서 x 보다 큰 최소 원소를 찾아 교체.
// 없으면 row 끝에 x 추가 후 -1 반환.
int bump(vector<int>& row, int x) {
    auto it = upper_bound(row.begin(), row.end(), x);
    if (it == row.end()) {
        row.push_back(x);
        return -1;
    }
    int old = *it;
    *it = x;
    return old;
}

pair<Tableau, Tableau> rsk(vector<int> perm) {
    Tableau P, Q;
    int n = perm.size();
    
    for (int step = 0; step < n; step++) {
        int x = perm[step];
        int r = 0;
        
        // bump 하면서 내려가기
        while (true) {
            if (r >= (int)P.size()) {
                P.push_back({x});
                Q.push_back({step + 1}); // step+1 = insertion order
                break;
            }
            int old = bump(P[r], x);
            if (old == -1) {
                // x 가 row[r] 끝에 추가됨
                if (r >= (int)Q.size()) Q.resize(r + 1);
                Q[r].push_back(step + 1);
                break;
            }
            x = old;
            r++;
        }
    }
    return {P, Q};
}

작은 입력 step trace

순열 π = [3, 1, 4, 2]

Step 0: insert 3
  P = [[3]]
  Q = [[1]]

Step 1: insert 1
  1 bumps 3 in row 0 → P[0] = [1], 3 goes to row 1
  P = [[1], [3]]
  Q = [[1], [2]]

Step 2: insert 4
  4 > 1, append to P[0]
  P = [[1, 4], [3]]
  Q = [[1, 2], [2]]

Step 3: insert 2
  2 bumps 4 in row 0 → P[0] = [1, 2], 4 goes to row 1
  4 bumps nothing in row 1, appends
  P = [[1, 2], [3, 4]]
  Q = [[1, 2], [2, 4]]

LIS = P[0] 길이 = 2 (실제 LIS: 1,2 또는 1,4 또는 3,4)
LDS = P 첫 열 길이 = 2

응용

1. LIS / LDS

Schensted: 첫 행 길이 = LIS, 첫 열 길이 = LDS. RSK 자체가 O(n²) 또는 O(n log n) (binary search bump) 로 LIS 와 동치.

2. Disjoint LIS / Three Investigators

Greene 정리로 서로소 증가 수열 k 개 의 최대 총 길이 = 처음 k 행 길이 합.

3. SYT 개수 카운팅

Hook length formula 로 다항 시간. 큰 n 에 modular.

4. Schur Polynomial / 표현론

대수적 응용 (PS 에서는 드묾).

복잡도

작업	비용
RSK insert 한 원소	O(√n) (binary search bump)
전체 RSK	O(n √n) 또는 O(n log n)
Hook length formula	O(n)

함정

1. shape 의 정의

행 길이 ≥ 행 길이의 약한 단조 감소. SYT 는 행 / 열 둘 다 증가.

2. P, Q 의 모양 일치

RSK 의 출력 (P, Q) 는 항상 같은 shape. 다른 shape 가 나오면 구현 버그.

3. Greene 정리 적용 범위

“서로소” 가 필수. 교차 가능 한 경우의 합은 다른 정리.

BOJ 연습 문제

번호	제목	링크
BOJ 18594	Three Investigators	kokoa-lab
BOJ 18461	Disjoint LIS	kokoa-lab

참고

• LGV Theorem
• Generating Function
• Matroid