Tedyun: Created page with "== Overview == * For a given $n$, find a probability that this number $n$ will end up in the position $(i,j)$ ($i$-th row and $j$-th column) in the insertion tableau via RSK ..."

2012-12-04T01:17:08Z

Created page with "== Overview == * For a given $n$, find a probability that this number $n$ will end up in the position $(i,j)$ ($i$-th row and $j$-th column) in the insertion tableau via RSK ..."

New page

== Overview ==

* For a given $n$, find a probability that this number $n$ will end up in the position $(i,j)$ ($i$-th row and $j$-th column) in the insertion tableau via RSK algorithm.
* Dually, compute the expectation value of the number that ends up in a given position $(i,j)$.
* Originally from http://mathoverflow.net/questions/82353/permutations-stopping-times-bessel-functions-hook-formula-and-robinson-schenst

== Some Results ==

Let $f_n(i,j)$ be the total number of permutations $p$ in $S_n$ such that the $P$-tableau of $p$ under RSK has $n$ in $(i,j)$-position.
(then $\sum_{i,j} f_n(i,j) = n!$ and $f_n(i,j)/n!$ is the probability that $n$ is in the $(i,j)$-position in the $P$-tableau of a permutation in $S_n$.)

Let $F(i,j)$ be the expected value of the number that eventually lands at $(i,j)$ position in the insertion tableau via RSK, over all permutations in $S_n$ as $n$ goes to infinity.

* $f_n(i,j) = 0$ if $n > ij$ (trivial)
* $f_n(1,2) = n – 1$ (easy)
* $f_n(1,3) = \binom{2n-2}{n-3}$ (http://oeis.org/A002694)
* $f_n(2,2) = n \binom{2n-4}{n-4}$
* $f_n(2,2) = n f_{n-1}(1,3)$ which implies $F(2,2) = F(1,3) + 1$.

== Problem ==

* Want a bijection $\phi$: {permutations in $S_n$ whose $(2,2)$-entry is $n$} $\longrightarrow$ {permutations in $S_n$ whose $(1,3)$-entry is $n-1$}.
* $f_n(k,k) = n f_{n-1}(k-1,k+1)$

== Numerical Results ==

RSK_dist(2);

[[0, 1], [1, 0]]

RSK_dist(3);

[[0, 2, 1], [2, 0, 0], [1, 0, 0]]

RSK_dist(4);

[[0, 3, 6, 1], [3, 4, 0, 0], [6, 0, 0, 0], [1, 0, 0, 0]]

RSK_dist(5);

[[0, 4, 28, 12, 1], [4, 30, 0, 0, 0], [28, 0, 0, 0, 0], [12, 0, 0,
0, 0], [1, 0, 0, 0, 0]]

RSK_dist(6);

[[0, 5, 120, 105, 20, 1], [5, 168, 25, 0, 0, 0], [120, 25, 0, 0, 0,
0], [105, 0, 0, 0, 0, 0], [20, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0]]

RSK_dist(7);

[[0, 6, 495, 830, 276, 30, 1], [6, 840, 462, 0, 0, 0, 0], [495, 462,
0, 0, 0, 0, 0], [830, 0, 0, 0, 0, 0, 0], [276, 0, 0, 0, 0, 0, 0],
[30, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0]]

RSK_dist(8);

[[0, 7, 2002, 6321, 3332, 595, 42, 1], [7, 3960, 5684, 196, 0, 0, 0,
0], [2002, 5684, 0, 0, 0, 0, 0, 0], [6321, 196, 0, 0, 0, 0, 0, 0],
[3332, 0, 0, 0, 0, 0, 0, 0], [595, 0, 0, 0, 0, 0, 0, 0], [42, 0, 0,
0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0]]

RSK_dist(9);

[[0, 8, 8008, 47544, 38108, 10024, 1128, 56, 1], [8, 18018, 59616,
7056, 0, 0, 0, 0, 0], [8008, 59616, 1764, 0, 0, 0, 0, 0, 0], [47544,
7056, 0, 0, 0, 0, 0, 0, 0], [38108, 0, 0, 0, 0, 0, 0, 0, 0], [10024,
0, 0, 0, 0, 0, 0, 0, 0], [1128, 0, 0, 0, 0, 0, 0, 0, 0], [56, 0, 0,
0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0]]

RSK_dist(10);

[[0, 9, 31824, 357000, 427392, 156780, 25104, 1953, 72, 1], [9,
80080, 579069, 158112, 1764, 0, 0, 0, 0, 0], [31824, 579069, 70560,
0, 0, 0, 0, 0, 0, 0], [357000, 158112, 0, 0, 0, 0, 0, 0, 0, 0],
[427392, 1764, 0, 0, 0, 0, 0, 0, 0, 0], [156780, 0, 0, 0, 0, 0, 0,
0, 0, 0], [25104, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1953, 0, 0, 0, 0, 0,
0, 0, 0, 0], [72, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0,
0, 0, 0]]

Permutation RSK distribution - Revision history

Tedyun: Created page with "== Overview == * For a given $n$, find a probability that this number $n$ will end up in the position $(i,j)$ ($i$-th row and $j$-th column) in the insertion tableau via RSK ..."