The paper

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)). The number of standard Young tableaux of shape $\lambda$ is given by the Frame-Robinson-Thrall hook-length formula:

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:

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

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) proves that as $n \to \infty$,

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 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 executes the entire verification pipeline in standard Python with no third-party dependencies.

Results

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

For the exhaustive verification check, patience sorting over all 409113 permutations across the first 9 sample sizes matched the tableau-derived frequencies with zero discrepancies.

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

Across all 50 evaluated sample sizes, the ratio $E[L_n] / (2\sqrt{n})$ attains its maximum of 0.799695 at the largest evaluated sample size, confirming that the finite expectation remains strictly below the asymptotic leading term. The scaled mean reaches -1.475863 and scaled variance reaches 0.526961, 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.