TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6.1-sol)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The RSK shape of a uniform random permutation has the Plancherel law

Statement

Let $n \geq 1$ and let $σ$ be uniformly distributed on $S_{n}$ (The uniform probability space on a nonempty finite set). Let $sh (σ) ⊢ n$ be the common shape of the Robinson-Schensted pair $(P (σ), Q (σ))$ (The Robinson-Schensted correspondence). Then $sh$ is a random element with values in the finite measurable space $(Y_{n}, 2^{Y_{n}})$ (Law or distribution of a random element) and for every $λ ⊢ n$ $P (sh (σ) = λ) = \frac{(f^{λ})^{2}}{n!} = P_{n} (λ) .$ In particular the uniform distribution on $S_{n}$ pushes forward to the Plancherel measure of order $n$ , and the length of a longest increasing subsequence of $σ$ has the same law as the first row length of a Plancherel-random diagram.

Facts & Assumptions

Given: $n \geq 1$ ; the permutations of ${1, \dots, n}$ written in one-line form, equipped with the uniform probability; the Robinson-Schensted map $σ \mapsto (P (σ), Q (σ))$ ; the shape $sh (σ)$ ; the number $f^{λ}$ of standard $λ$ -tableaux for $λ ⊢ n$ ; and the Plancherel weights $P_{n} (λ) = (f^{λ})^{2} / n!$ (The Plancherel measure on the partitions of $n$ ).

[F1]

The Robinson-Schensted map is a bijection from the permutations of ${1, \dots, n}$ onto the set of pairs $(P, Q)$ of standard tableaux of the same shape $λ ⊢ n$ ; $P (σ)$ has shape $sh (σ)$ (The Robinson-Schensted correspondence).

[F2]

For every $λ ⊢ n$ the number of standard $λ$ -tableaux equals $f^{λ}$ , the number of paths from the empty diagram to $λ$ in the Young graph (Young-graph paths correspond to standard tableaux, Standard polytabloids form a basis of a complex Specht module).

[F3]

On a nonempty finite set the uniform probability space gives every element weight $1 / ∣ Ω ∣$ , so an event of cardinality $m$ has probability $m / ∣ Ω ∣$ (The uniform probability space on a nonempty finite set, Finite probability spaces, outcome weights, events, and event probabilities).

[F4]

A function from a finite probability space to a finite set is a random element, its law being the pushforward of the probability (Law or distribution of a random element); a real-valued such function is a real random variable with the distribution of Real random variables on finite probability spaces and their finite distributions.

[F5]

If $σ$ has insertion tableau $P (σ)$ of shape $λ$ , then the length of a longest increasing subsequence of $σ$ is $λ_{1}$ and the length of a longest decreasing subsequence is $λ_{1}^{'}$ (The Schensted theorem on longest increasing and decreasing subsequences).

Proof

technique · direct

1.1givenF1F2

Fibres of the shape map: by [F1] the Robinson-Schensted map is a bijection from the set of $n!$ permutations of ${1, \dots, n}$ onto the set of pairs $(P, Q)$ of standard tableaux of equal shape $λ ⊢ n$ . For a fixed $λ ⊢ n$ the permutations with $sh (σ) = λ$ correspond bijectively to the pairs $(P, Q)$ of standard $λ$ -tableaux, and by [F2] there are exactly $f^{λ}$ choices for $P$ and independently $f^{λ}$ choices for $Q$ ; hence the fibre over $λ$ has cardinality $∣ {sh = λ} ∣ = (f^{λ})^{2}$ .

2.1givenF3step 1.1algebra

Probability of a shape: on $S_{n}$ the uniform probability space of [F3] assigns weight $1 / n!$ to every permutation, so the event ${sh = λ}$ of step 1.1 has probability $∣ {sh = λ} ∣ / n! = (f^{λ})^{2} / n! = P_{n} (λ)$ ; the denominator $n!$ is positive for $n \geq 1$ .

3.1givenF4step 2.1

Random element and its law: $sh$ is a function from the finite probability space $S_{n}$ to the finite set $Y_{n}$ , hence by [F4] a random element with values in $Y_{n}$ , and its law is the pushforward of the uniform probability; step 2.1 computes that law to be exactly $P_{n}$ . Every subset of $Y_{n}$ has a measurable inverse image, since every subset of the finite outcome space $S_{n}$ is an event. Thus the partition-valued map itself has the law $P_{n}$ ; a real encoding would instead have the corresponding encoded law.

4.1givenF5step 2.1step 3.1algebra∎

Longest increasing subsequence: for every realisation $σ$ , [F5] identifies the length of a longest increasing subsequence of $σ$ with the first row length $sh (σ)_{1}$ . Therefore, for every $l \geq 0$ , the probability that the longest increasing subsequence has length $l$ equals $P (sh (σ)_{1} = l) = P_{n} ({λ : λ_{1} = l})$ by step 3.1, which is precisely the law of the first row length of a diagram drawn from $P_{n}$ . Together with step 3.1 this proves the statement.

Depends on

Used by

Dependency tree · two levels

39 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Dan Romik, The Surprising Mathematics of Longest Increasing Subsequences, Cambridge University Press 2015; author-hosted manuscript of 20 August 2014 (363 pp.) (standard reference, not scraped)
Vladimir Ivanov and Grigori Olshanski, Kerov's central limit theorem for the Plancherel measure on Young diagrams, arXiv:math/0304010; survey-paper version in Symmetric Functions 2001, NATO Science Series II 74 (2002), 93-151 (standard reference, not scraped)