Explicit marginal distributions for permutations with prescribed Robinson–Schensted shape
William Q. Erickson · 2026
Read Explicit marginal distributions for permutations with prescribed Robinson–Schensted shape by William Q. Erickson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-00378.txt.
Introduction
William Q. Erickson studies random permutations through the lens of the Robinson-Schensted correspondence, a classic algorithm that assigns each permutation a shape, a partition drawn as a diagram. The shape famously encodes the lengths of the longest increasing and decreasing subsequences, global facts about the permutation. Erickson asks the opposite, local question: fix the shape, and ask how likely position i is to receive value j.
Using the theory of tableaux, the fillings of these diagrams, he derives explicit formulas for those probabilities for hook shapes, two-row shapes, and rectangles. Plotted as matrices, the probabilities form intricate diffraction-like patterns, which he depicts and analyzes. As a surprise application, for hook and two-row shapes the expected share of fixed points tends, as the shape grows, to a classic Wallis integral value. The paper links a global combinatorial machine to fine local statistics.
Catalog record
| CREATOR | William Q. Erickson |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 207 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.00378
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Explicit marginal distributions for permutations with prescribed Robinson–Schensted shape William Q. Erickson Abstract . Given a permutation σ \sigma , the Robinson–Schensted correspondence determines a certain partition called the shape of σ \sigma . Famously, the shape measures the longest unions of increasing and decreasing subsequences, thus giving global information about σ \sigma . In this paper, by contrast, we ask how prescribing a shape collectively controls local behavior: if σ \sigma is a random permutation of shape λ \lambda , then what is P i j λ ≔ P^{\lambda}_{ij}\coloneqq the probability that σ ( i ) = j \sigma(i)=j ? Using tableau-theoretic methods, we derive explicit formulas for P i j λ P^{\lambda}_{ij} when λ \lambda is a hook, two-row, or rectangular shape. We use these formulas to depict and analyze the intricate diffraction-like patterns in the matrices ( P i j λ ) (P^{\lambda}_{ij}) . As a surprising application, we show that for both hook and two-row shapes, as the largest part of λ \lambda tends to infinity with the remaining parts fixed (summing to m m ), the expected proportion of fixed points in σ \sigma approaches the Wallis integral ∫ 0 π / 2 sin 2 m + 1 x 𝑑 x = ( 2 m ) !! / ( 2 m + 1 ) !! \int_{0}^{\pi/2}\sin^{2m+1}x\>dx=(2m)!!/(2m+1)!! . 2020 Mathematics Subject Classification Primary 60C05; Secondary 05A05, 05A10 1. Introduction Let \mathfrak{S}_{n} denote the symmetric group on n letters. In this paper, we solve the following problem in the case where the partition \lambda is a hook or two-row or rectangular shape: Problem 1.1 . Let \sigma\in\mathfrak{S}_{n} be chosen uniformly at random, and let \lambda be a partition of n . For all 1\leq i,j\leq n , find an explicit formula for the conditional probability P^{\lambda}_{ij}\coloneqq\mathbb{P}\Big(\sigma(i)=j\;\Big|\;\sigma\text{ has Robinson--Schensted shape }\lambda\Big). Programming our solution has led us to realize that the doubly stochastic matrix P^{\lambda}=(P^{\lambda}_{ij}) exhibits intricate “diffraction”-like patterns that imitate certain aspects of the Young diagram of \lambda ; see Figures 1 – 3 , which show the heat maps of P^{\lambda} for hook, two-row, and rectangular shapes, respectively. Our P^{\lambda}_{ij} formulas not only describe these patterns explicitly, but also enable us to generate their pictures in the first place, since a brute-force approach becomes computationally prohibitive even for relatively small n . We are hopeful that the results and methods in the paper might provide a launch point in solving Problem 1.1 for other families of shapes, or ultimately for arbitrary \lambda . Motivation At the risk of understatement, the Robinson–Schensted (RS) correspondence is a fundamental concept in algebraic combinatorics. In itself, the RS correspondence is a bijection from \mathfrak{S}_{n} to the set of ordered pairs of same-shaped standard Young tableaux with n boxes; as an example where n=7 , we have (1.1) \operatorname{RS}:(2,7,4,6,3,1,5)\longmapsto\left(\hbox{$\vbox{\hbox{\vtop{\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 1$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 2$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 4$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}\cr\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 3$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 7$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}\cr\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 5$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}\cr\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 6$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}\cr}}\kern 690.4pt}}$}_{\!\!\textstyle,}\;\;\hbox{$\vbox{\hbox{\vtop{\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 1$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 3$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 5$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}\cr\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 2$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}&\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 6$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}\cr\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 4$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}\cr\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.4pt{\vss\hbox to8.00006pt{\hss$\scriptstyle 7$\hss}\vss}\kern-8.4pt\vrule height=8.4pt,width=0.39993pt\kern 8.00006pt\vrule height=8.4pt,width=0.39993pt}\kern-0.19997pt\kern-8.4pt\hrule width=8.79993pt,height=0.39993pt\kern 8.00006pt\hrule width=8.79993pt,height=0.39993pt}\cr}}\kern 690.4pt}}$}\right), with the intermediate details given in Figure 5 . At a less granular level, however, when we forget the tableau entries, the RS correspondence simply associates to each permutation in \mathfrak{S}_{n} a certain shape , namely the partition of n given by the row lengths of either tableau. For example, the permutation in ( 1.1 ) has shape (3,2,1,1) . The shape of a permutation \sigma encodes global information about \sigma : Greene’s theorem ( 2.12 ) states that the partial sums of the shape’s row (resp., column) lengths give the lengths of the longest unions of increasing (resp., decreasing) subsequences in \sigma . Thus, since prescribing the shape of a random permutation \sigma controls the lengths of its monotone subsequences, this should presumably affect the expected local behavior of \sigma , meaning the marginal distribution of \sigma(i) for each 1\leq i\leq n . The effect of shape on the marginal distributions seems not to have been studied in the literature; our desire to understand and quantify it led us to pose Problem 1.1 , the central problem in this project. (a) \lambda\!=\!(15,1^{0}) (b) \lambda\!=\!(14,1^{1}) (c) \lambda\!=\!(13,1^{2}) (d) \lambda\!=\!(12,1^{3}) (e) \lambda\!=\!(11,1^{4}) (f) \lambda\!=\!(10,1^{5}) (g) \lambda\!=\!(9,1^{6}) (h) \lambda\!=\!(8,1^{7}) Figure 1 . Heat maps of P^{\lambda} where \lambda=(\ell,1^{n-\ell}) is a hook shape, for n=15 . In each heat map, the entry P^{\lambda}_{ij} gives the probability that \sigma(i)=j given that a uniform random \sigma has shape \lambda ; white represents 0, and black represents the maximum matrix entry. These were generated in Mathematica using our explicit formula for P^{\lambda}_{ij} in Theorem 1.2 . In light of Lemma 2.3 , the cases \ell=8,7,\ldots,2,1 are obtained by holding the page up to a mirror. (a) \lambda\!=\!(15,0) (b) \lambda\!=\!(14,1) (c) \lambda\!=\!(13,2) (d) \lambda\!=\!(12,3) (e) \lambda\!=\!(11,4) (f) \lambda\!=\!(10,5) (g) \lambda\!=\!(9,6) (h) \lambda\!=\!(8,7) Figure 2 . Heat maps of P^{\lambda} where \lambda=(\ell,n-\ell) is a two-row shape, for n=15 . These were generated in Mathematica using our formula for P^{\lambda}_{ij} in Theorem 1.3 . In light of Lemma 2.3 , a horizontal (or vertical) reflection takes the heat map of \lambda to that of the two-column shape \lambda^{\prime} . (a) \lambda=(9^{3}) (b) \lambda=(8^{3}) (c) \lambda=(7^{3}) (d) \lambda=(7^{4}) (e) \lambda=(6^{4}) (f) \lambda=(5^{4}) (g) \lambda=(6^{5}) (h) \lambda=(5^{5}) Figure 3 . Heat maps of P^{\lambda} where \lambda=(\ell^{m}) is a rectangular shape, showing most cases (up to symmetry) where 20\leq n\leq 30 with more than two rows. These were generated in Mathematica using our formula for P^{\lambda}_{ij} in Theorem 1.4 . The diffraction-like pattern forms a grid with \ell dark antidiagonal bands and m dark diagonal bands, imitating the (rotated) Young diagram of \lambda . Problem 1.1 admits trivial solutions in the two extreme cases where \lambda=(n) is a single row or \lambda=(1^{n})\coloneqq(1,\ldots,1) is a single column. In the one-row case, there is only one permutation of shape \lambda=(n) , namely the identity (1,2,3,\ldots,n) , and so we have P^{\lambda}_{ij}=\delta_{ij} . Likewise, in the one-column case, there is only one permutation of shape \lambda=(1^{n}) , namely the exchange permutation (n,\ldots,3,2,1) , and so we have P^{\lambda}_{ij}=\delta_{i,n+1-j} . All other shapes interpolate between these two extreme cases in a deeply complicated way. To gain some intuition for this, it is helpful to view the heat map of the matrix P^{\lambda} , where each entry P^{\lambda}_{ij} is given a shade between white (0) and black (the maximum matrix