CorollaryStatement: Literature-sourcedProof: Literature-sourcedPipeline-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.

RSK interchanges the insertion and recording tableaux under inversion

Statement

Let $n \geq 0$ and let $w = (w_{1}, \dots, w_{n})$ be a permutation of ${1, \dots, n}$ with RSK pair $(P (w), Q (w))$ (The Robinson-Schensted correspondence). Let $w^{- 1} = (p_{1}, \dots, p_{n})$ be the inverse permutation, where $p_{i}$ is the position of $i$ in $w$ (so $w_{p_{i}} = i$ ). Then $P (w^{- 1}) = Q (w) and Q (w^{- 1}) = P (w) .$ In particular, identifying $σ \in S_{n}$ with the word $(σ (0) + 1, \dots, σ (n - 1) + 1)$ via The finite symmetric group $S_{n}$ , one-line notation, and cycle notation, the RSK pair of $σ^{- 1}$ is $(Q, P)$ .

Facts & Assumptions

Given: An integer $n \geq 0$ , a word $w = (w_{1}, \dots, w_{n})$ of pairwise distinct real numbers with ${w_{1}, \dots, w_{n}} = {1, \dots, n}$ , its RSK pair $(P (w), Q (w))$ , and the inverse word $w^{- 1} = (p_{1}, \dots, p_{n})$ with $w_{p_{i}} = i$ .

[L1]

The Robinson-Schensted map is a bijection from the set $X_{n}$ of such words onto the set of pairs $(P, Q)$ of standard tableaux of a common shape $λ ⊢ n$ ; equivalently, two words with the same RSK pair are equal, and every such pair occurs (The Robinson-Schensted correspondence).

[L2]

For a lexicographically ordered two-line array $(u; v)$ : (a) construction A (insert $v_{k}$ , write the label $u_{k}$ in the new box) produces a pair of semistandard tableaux of common shape, and the correspondence with lexicographically ordered arrays is a bijection; (b) the lexicographically ordered rearrangement of the transposed array $(v; u)$ corresponds to $(Q, P)$ ; (c) if $u_{k} = k$ for all $k$ then construction A is exactly the row-insertion construction of The Robinson-Schensted correspondence and produces its RSK pair (The RSK correspondence for two-line arrays).

[L3]

A two-line array is a pair of finite lists of positive integers whose columns are in nondecreasing lexicographic order; the top line $u$ is strictly increasing exactly when its entries are distinct and increasing (The RSK correspondence for two-line arrays).

[L4]

$S_{n}$ acts on ${0, 1, \dots, n - 1}$ , one-line notation and cycles are as in The finite symmetric group $S_{n}$ , one-line notation, and cycle notation; a standard tableau is a filling of a Young diagram by distinct integers increasing along rows and columns (Tableaux and standard tableaux).

Proof

technique · direct

1.1L3given

The two-line array $A : = ((1, 2, \dots, n); (w_{1}, \dots, w_{n}))$ is lexicographically ordered, because its top line is strictly increasing; its top line has distinct entries and its columns are the pairs $(k, w_{k})$ for $k = 1, \dots, n$ .

1.2L2L1given

Construction A applied to $A$ inserts $v_{k} = w_{k}$ at step $k$ and writes $u_{k} = k$ in the box added at step $k$ ; by L2 the resulting pair is the RSK pair of the word $(w_{1}, \dots, w_{n})$ , namely $(P (w), Q (w))$ .

1.3L3givenalgebra

The transposed array of $A$ is $((w_{1}, \dots, w_{n}); (1, 2, \dots, n))$ , whose columns are the pairs $(w_{k}, k)$ ; since $w$ is a permutation of ${1, \dots, n}$ , each value $i$ occurs exactly once among the first coordinates, at the index $k = p_{i}$ with $w_{p_{i}} = i$ , so the lexicographically ordered rearrangement of these columns is the array $A^{- 1} : = ((1, 2, \dots, n); (p_{1}, \dots, p_{n}))$ .

1.4L4givenalgebra

For the group-theoretic form, let $σ \in S_{n}$ have one-line form $[σ (0), \dots, σ (n - 1)]$ and let $w = (σ (0) + 1, \dots, σ (n - 1) + 1)$ be the associated word; then for each $i \in {1, \dots, n}$ the position $p_{i}$ of $i$ in $w$ satisfies $p_{i} = σ^{- 1} (i - 1) + 1$ , because $w_{σ^{- 1} (i - 1) + 1} = σ (σ^{- 1} (i - 1)) + 1 = i$ ; hence the word associated with $σ^{- 1}$ is exactly $w^{- 1} = (p_{1}, \dots, p_{n})$ .

2.1L2step 1.2step 1.3

By L2 the array $A^{- 1}$ corresponds under construction A to $(Q (w), P (w))$ : it is the lexicographically ordered rearrangement of the transpose of the array $A$ of step 1.2, whose pair is $(P (w), Q (w))$ .

2.2L2L1givenstep 1.3

Construction A applied to $A^{- 1}$ inserts $p_{1}, \dots, p_{n}$ and writes the labels $1, \dots, n$ , so by L2 it produces the RSK pair $(P (w^{- 1}), Q (w^{- 1}))$ of the word $w^{- 1} = (p_{1}, \dots, p_{n})$ .

3.1L2step 2.1step 2.2

By L2 the correspondence between lexicographically ordered two-line arrays and pairs is bijective, and the array $A^{- 1}$ corresponds to exactly one pair; by steps 2.1 and 2.2 this pair is both $(Q (w), P (w))$ and $(P (w^{- 1}), Q (w^{- 1}))$ , so $P (w^{- 1}) = Q (w)$ and $Q (w^{- 1}) = P (w)$ .

4.1step 3.1step 1.4∎

Applying step 3.1 to the permutation $σ$ identified with $w$ gives $(P (σ^{- 1}), Q (σ^{- 1})) = (Q (σ), P (σ))$ , which is the stated group-theoretic form.

Depends on

Used by

Involutions are counted by standard tableaux Corollary
RSK pairs for two nonidentity involutions Example

Dependency tree · two levels

15 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

Donald E. Knuth, Permutations, Matrices, and Generalized Young Tableaux, Pacific Journal of Mathematics 34 (1970), 709-727 (standard reference, not scraped)
Charlotte Chan, Representation Theory of Symmetric Groups (Oxford Hilary Term 2011 lecture notes, 40 PDF pp.) (standard reference, not scraped)
Jeremy L. Martin, Lecture Notes on Algebraic Combinatorics (263 pp.) (standard reference, not scraped)