Lagmental Vicfred

RSK Turns a Permutation into Two Tableaux of One Shape by Vicfred

tags: mathematics, integer partitions, Young tableaux, q-analogues

Robinson--Schensted gives a bijection whose first row records longest increasing subsequences. The point is to make the formal expression readable enough to audit line by line.

The data

A partition \(\lambda\vdash n\) is both a decreasing sequence and a Ferrers diagram. Statistics such as hook lengths \(h_{ij}\) turn the diagram into exact product formulas.

$$ \pi\in S_n\longleftrightarrow(P(\pi),Q(\pi)) $$

I read the first line as input and the second as output. The symbols \(\forall\) and \(\exists\) are not interchangeable, and neither may be upgraded silently to \(\Longleftrightarrow\).

$$ \operatorname{LIS}(\pi)=\lambda_1,\qquad\operatorname{LDS}(\pi)=\lambda'_1 $$

Derivation

Now evaluate one representative case. The result should agree with the structural law above, but it is obtained without assuming the conclusion.

$$ n!=\sum_{\lambda\vdash n}(f^\lambda)^2 $$

Invariant content

What survives the example is not its particular numbers but the relation encoded by the two rows below. That relation is the part worth transporting to a new setting.

$$ \begin{aligned} \mathsf{D}\;&:\quad \pi\in S_n\longleftrightarrow(P(\pi),Q(\pi)),\\[5pt] \mathsf{C}\;&:\quad \operatorname{LIS}(\pi)=\lambda_1,\qquad\operatorname{LDS}(\pi)=\lambda'_1. \end{aligned} $$

Scope

Partitions forget order, compositions retain it, and tableaux add labels subject to row and column rules. Interchanging these objects changes the count.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \operatorname{LIS}(\pi)=\lambda_1,\qquad\operatorname{LDS}(\pi)=\lambda'_1 \end{gathered}} $$

The important habit is to remember what was fixed before the calculation began and what was proved only afterward. The final display preserves that order.

This article was posted on Thu 05 December 2019. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.