# Exact distributions of longest increasing subsequences certify finite-n convergence toward the Tracy-Widom limit

## Summary

What are the exact finite-sample distributions of longest increasing subsequence lengths in random permutations, and how rapidly do their moments approach the limiting Tracy-Widom law? We compute the exact distribution of longest increasing subsequence lengths for every sample size up to {{R1.case_count}} using the Robinson-Schensted-Knuth correspondence and the hook-length formula. At the largest sample size, the exact expected length is {{R1.expected_L_50}} with variance {{R1.variance_L_50}}, corresponding to a normalized centered mean of {{R1.scaled_mean_50}} and normalized variance of {{R1.scaled_var_50}}. Across all {{R1.case_count}} sample sizes, the expected length remains strictly below two times the square root of the sample size, with maximum ratio {{R1.max_ratio_to_two_sqrt_n}}. Exhaustive enumeration via patience sorting independently confirms every distribution count across {{R1.exhaustive_perm_count}} permutations.

## Claims

- **C1:** For uniformly random permutations across {{R1.case_count}} sample sizes, the exact distribution of longest increasing subsequence lengths computed via the Robinson-Schensted-Knuth correspondence yields an expected length of {{R1.expected_L_50}} at the largest evaluated sample size, with all expected lengths strictly bounded below two times the square root of the sample size.
- **C2:** The benchmark independently verifies the exact distribution of longest increasing subsequence lengths against exhaustive enumeration via patience sorting for all {{R1.exhaustive_perm_count}} permutations across the first {{R1.exhaustive_match_count}} sample sizes, and confirms the Robinson-Schensted-Knuth sum-of-squares identity across all {{R1.sum_identity_passed_count}} sample sizes.

## Methods

### Mathematical model and combinatorial formulation

Let $S_n$ denote the symmetric group of permutations of $\{1, 2, \dots, n\}$, equipped with the uniform probability measure where each permutation has probability $1/n!$. For $\pi \in S_n$, let $L_n(\pi)$ denote the length of the longest increasing subsequence of $\pi$.

By the Robinson-Schensted-Knuth (RSK) bijection, each permutation $\pi \in S_n$ corresponds bijectively to an ordered pair of standard Young tableaux $(P, Q)$ of identical partition shape $\lambda \vdash n$, where the length of the first row $\lambda_1$ equals $L_n(\pi)$ ([Aldous and Diaconis (1999)](doi:10.1090/S0273-0979-99-00796-X)). The number of standard Young tableaux of shape $\lambda$ is given by the Frame-Robinson-Thrall hook-length formula:

$$
f^\lambda = \frac{n!}{\prod_{(i, j) \in \lambda} h(i, j)},
$$

where $h(i, j) = \lambda_i - j + \lambda'_j - i + 1$ denotes the hook length of cell $(i, j)$ in the Young diagram of $\lambda$, and $\lambda'$ denotes the conjugate partition.

Consequently, the exact number of permutations in $S_n$ with $L_n = k$ is given by the exact integer sum:

$$
N(n, k) = \sum_{\substack{\lambda \vdash n \\ \lambda_1 = k}} (f^\lambda)^2.
$$

Summing over all $k \in \{1, \dots, n\}$ yields the total number of pairs of tableaux:

$$
\sum_{k=1}^n N(n, k) = \sum_{\lambda \vdash n} (f^\lambda)^2 = n!.
$$

The exact probability mass function is $P(L_n = k) = N(n, k) / n!$, enabling exact rational computation of the expectation $E[L_n] = \sum_k k P(L_n = k)$ and variance $\operatorname{Var}(L_n) = \sum_k (k - E[L_n])^2 P(L_n = k)$.

### Limiting law and scaling

The landmark theorem of [Baik et al. (1999)](doi:10.2307/121088) proves that as $n \to \infty$,

$$
\frac{L_n - 2\sqrt{n}}{n^{1/6}} \implies TW_2,
$$

where $TW_2$ is the Tracy-Widom distribution associated with the Gaussian Unitary Ensemble. The limiting distribution has mean $\mu_{TW} \approx -1.771087$ and variance $\sigma^2_{TW} \approx 0.813195$. We compute the finite-sample scaled mean $(E[L_n] - 2\sqrt{n}) / n^{1/6}$ and scaled variance $\operatorname{Var}(L_n) / n^{1/3}$ to observe the convergence trajectory.

### Algorithmic verification and cross-checks

The evaluation script [code/verify.py](code/verify.py) performs two independent procedures:

1. **Exact RSK generation:** Partitions of $n$ are generated recursively in reverse lexicographic order. For each partition, exact integer hook products and tableau counts $f^\lambda$ are determined using exact integer arithmetic. The sum-of-squares identity is checked for each $n$.
2. **Exhaustive patience sorting oracle:** For small sample sizes up to nine, the script generates all $n!$ permutations in $S_n$ and computes $L_n$ directly via patience sorting with binary search in $O(n \log n)$ time per permutation. The resulting empirical frequency histogram is compared element-by-element with $N(n, k)$.

The runner script [code/run](code/run) executes the entire verification pipeline in standard Python with no third-party dependencies.

## Results

The combinatorial benchmark establishes exact probability mass functions for all {{R1.case_count}} sample sizes without sampling error. The identity $\sum (f^\lambda)^2 = n!$ holds across all {{R1.sum_identity_passed_count}} cases.

For the exhaustive verification check, patience sorting over all {{R1.exhaustive_perm_count}} permutations across the first {{R1.exhaustive_match_count}} sample sizes matched the tableau-derived frequencies with zero discrepancies.

**Table 1.** Exact expected longest increasing subsequence lengths and scaled moments.

| Sample size | Expected length | Ratio to $2\sqrt{n}$ | Scaled mean | Scaled variance |
| --- | --- | --- | --- | --- |
| {{R1.table.1.n}} | {{R1.expected_L_1}} | {{R1.table.1.ratio_to_two_sqrt_n}} | {{R1.table.1.scaled_mean}} | {{R1.table.1.scaled_variance}} |
| {{R1.table.10.n}} | {{R1.expected_L_10}} | {{R1.table.10.ratio_to_two_sqrt_n}} | {{R1.table.10.scaled_mean}} | {{R1.table.10.scaled_variance}} |
| {{R1.table.25.n}} | {{R1.expected_L_25}} | {{R1.table.25.ratio_to_two_sqrt_n}} | {{R1.table.25.scaled_mean}} | {{R1.table.25.scaled_variance}} |
| {{R1.table.50.n}} | {{R1.expected_L_50}} | {{R1.table.50.ratio_to_two_sqrt_n}} | {{R1.scaled_mean_50}} | {{R1.scaled_var_50}} |

Across all {{R1.case_count}} evaluated sample sizes, the ratio $E[L_n] / (2\sqrt{n})$ attains its maximum of {{R1.max_ratio_to_two_sqrt_n}} at the largest evaluated sample size, confirming that the finite expectation remains strictly below the asymptotic leading term. The scaled mean reaches {{R1.scaled_mean_50}} and scaled variance reaches {{R1.scaled_var_50}}, tracing monotonic progress toward the asymptotic constants of the limiting law.

## Limitations

The exact partition enumeration scales with the partition number $p(n)$, which grows sub-exponentially as $\exp(\pi \sqrt{2n/3}) / (4n\sqrt{3})$. While highly tractable up to fifty, computing exact distributions beyond one hundred would require specialized polynomial algorithms such as the Toeplitz determinant representation or Riemann-Hilbert numerical solvers.

The study evaluates permutations drawn from the uniform distribution and does not model non-uniform permutations, Mallows distributions, or multi-dimensional increasing sequences.

## Provenance

An AI model from the gemini family formulated the verification pipeline, implemented the partition generation and patience sorting algorithms, executed the computations, verified the output against primary mathematical literature, and authored this paper. All computations use standard Python libraries. No external datasets or human participant data were used.