정렬의 가장 기본적인 방법

타블로의 형상이 (n_1, n_2, ..., n_m)이면, 가장 긴 갈고리의 길이는 n_1 + m − 1이다. 갈고리 길이를 더 자세히 살펴보면, 1행은 n_1 + m − 1, n_1 + m − 2, ..., 1의 모든 길이를 포함하되, (n_1 + m − 1) − (n_m), (n_1 + m − 1) − (n_{m−1} + 1), ..., (n_1 + m − 1) − (n_2 + m − 2)는 제외된다. 예를 들어 그림 5(Fig. 5)에서 1행의 갈고리 길이는 12, 11, 10, ..., 1이되, 10, 9, 6, 3, 2는 제외된다; 예외들은 존재하지 않는 칸 (6, 3), (5, 3), (4, 5), (3, 7), (2, 7)에서 칸 (1, 7)까지 이어지는 다섯 개의 존재하지 않는 갈고리에 대응한다. 마찬가지로 j행은 n_j + m − j, ..., 1의 모든 길이를 포함하되, (n_j + m − j) − (n_m), ..., (n_j + m − j) − (n_{j+1} + m − j − 1)은 제외된다. 따라서 모든 갈고리 길이의 곱은 다음과 같다:

이것이 바로 식 (34)에서 일어나는 것이므로, J. S. Frame, G. de B. Robinson, R. M. Thrall에 기인하는 다음의 유명한 결과를 유도했다 [Canadian J. Math. 6 (1954), 316–318]:

정리 H (Theorem H). {1, 2, ..., n}에 대해 지정된 형상을 갖는 타블로의 수는 n!을 갈고리 길이들의 곱으로 나눈 것이다.

정리 H (Theorem H). {1, 2, ..., n}에 대해 지정된 형상을 갖는 타블로의 수는 n!을 갈고리 길이들의 곱으로 나눈 것이다.

이것이 매우 간단한 규칙이므로, 간단한 증명이 있어야 마땅하다; 직관적 논증은 다음과 같이 진행된다: 타블로의 각 원소는 해당 갈고리에서 가장 작다. 타블로 형상을 무작위로 채울 때, 칸 (i, j)가 대응하는 갈고리의 최소 원소를 포함할 확률은 갈고리 길이의 역수이다; 이 확률들을 모든 i와 j에 대해 곱하면 정리 H를 얻는다. 그러나 불행히도 이 논증은 오류가 있는데, 확률들이 전혀 독립적이지 않기 때문이다! 갈고리의 조합론적 성질을 올바르게 사용한 정리 H의 직접 증명은 1992년까지 알려지지 않았다 (연습문제 39 참조).

정리 H는 2장에서 고려한 트리(tree)의 열거와 흥미로운 연결점이 있다. 우리는 n개 노드를 가진 이진 트리(binary tree)가 스택(stack)으로 얻을 수 있는 순열에 대응하며, 그러한 순열이 n개의 S와 n개의 X로 이루어진 수열 a_1 a_2 ... a_{2n}에 대응함을 관찰했는데, 여기서 왼쪽에서 오른쪽으로 읽을 때 S의 개수가 결코 X의 개수보다 작지 않다. (연습문제 2.2.1–3과 2.3.1–6 참조.) 후자의 수열은 형상 (n, n)의 타블로에 자연스러운 방식으로 대응한다; a_i = S인 인덱스 i를 1

정리 H는 2장에서 고려한 트리(tree)의 열거와 흥미로운 연결점이 있다. 우리는 n개 노드를 가진 이진 트리(binary tree)가 스택(stack)으로 얻을 수 있는 순열에 대응하며, 그러한 순열이 n개의 S와 n개의 X로 이루어진 수열 a_1 a_2 ... a_{2n}에 대응함을 관찰했는데, 여기서 왼쪽에서 오른쪽으로 읽을 때 S의 개수가 결코 X의 개수보다 작지 않다. (연습문제 2.2.1–3과 2.3.1–6 참조.) 후자의 수열은 형상 (n, n)의 타블로에 자연스러운 방식으로 대응한다; a_i = S인 인덱스 i를 1행에 놓고, a_i = X인 인덱스를 2행에 놓는다. 예를 들어 수열

이 타블로에서 열 제약조건은 왼쪽에서 오른쪽으로 읽을 때 X의 개수가 S의 개수를 결코 초과하지 않을 때에만 만족된다. 정리 H에 의해, 형상 (n, n)의 타블로 수는

$$\frac{(2n)!}{1 \cdot 3 \cdot 5 \cdots (2n-1) \cdot 2 \cdot 4 \cdot 6 \cdots 2n} = \frac{1}{n+1}\binom{2n}{n}$$