# Tableaux with limited rows and complementary skew shapes

Given a partition $\mu=(\mu_1,\mu_2...,\mu_d)$, define $\bar\mu=(\mu_1-\mu_d,\mu_1-\mu_{d-1},...,\mu_1-\mu_2,0)$, the complementary shape in the $d\times \mu_1$ rectangle. Then the number of skew standard Young tableaux with at most $d$ rows and skew part $\mu$ are (I believe) in bijection with those with skew part $\bar\mu$ (where they each have $n$ labels).

I have a proof for the case $\mu=(i+j,i,0)$, $\bar\mu=(i+j,j,0)$ but I heard the general case may have appeared in the literature. I have been unable to find the reference. It might work with jeu de taquin and I'd love to see the details.

Is anyone familiar with this paper?

EDIT: Equivalently, given a fixed lattice path from $(-\infty,0)$ to $(+\infty,d)$, we want to fill in $n$ labels of a standard Young tableau below the path and above the line $y=0$. The claim is that there's a bijection between these objects and the objects we get if we flip the lattice path over (180 degrees).

For example, if $n=6$, $d=3$, $\mu=(3,1,0)$, and $\bar\mu=(3,2,0)$, these two are paired up by my bijection: • There is an easy bijection if you restrict the numbers to be between $1$ and $\mu_1$ - the column $i$ in $\bar{\mu}$ contains the complement of the elements in column $d-i$ in $\mu$, or did I misinterpret the question? – Per Alexandersson Apr 9 '16 at 11:16
• The skew parts are complements in a rectangle, but there is no restriction on the shape of the rest of the tableaux (other they have at most $d$ rows). – Jordan Apr 9 '16 at 23:11
• There must be some mistake in your formulation, $\mu_d - \mu_1$ is negative... but now I see what you mean... – Per Alexandersson Apr 10 '16 at 3:23
• Typos fixed! Should say $\mu_1-\mu_d$ and the line is $y=0$. Sorry, thanks for catching them! – Jordan Apr 10 '16 at 18:31
• I added an example to clarify. – Jordan Apr 10 '16 at 19:10

Here is another solution, based on the paper "Robinson-schensted algorithms for skew tableaux" by Sagan and Stanley (Darij Grinberg was the one who suggested that this algorithm might work, I'm just filling in the details in a pretty straightforward fashion).

Fix integers $k$ and $n$, and denote $[n]=\{1,2,\dots,n\}$. We say that $$\pi=\begin{pmatrix}i_1 & \dots & i_m\\ j_1 & \dots & j_m\end{pmatrix}$$ is a partial two-line array if the integers $i_1,\dots,i_m$ are distinct elements of $[n]$, the same is true for $j_1,\dots,j_m$, and $i_1<\dots<i_m$.

Also, fix some partition $\mu$ with at most $k$ rows, and assume all parts of $\mu$ are much bigger than $n$ (the correct way is to think of $\mu$ as a lattice path inside an infinite horizontal strip of height $k$).

We say that an SYT $P$ with at most $k$ rows has right boundary $\mu$ if it has shape $\mu/\nu$ for some $\nu$. A similar definition goes for SYT with left boundary $\mu$, and the original conjecture becomes $$\#\mathrm{SYT}_k^n(\mu/*)=\#\mathrm{SYT}_k^n(*/\mu)$$ where the LHS denotes the number of SYTs with $n$ boxes with at most $k$ rows and right boundary $\mu$ while the RHS denotes the number of SYTs with $n$ boxes with at most $k$ rows and left boundary $\mu$.

One more definition: a partial SYT with entry set $S$ is just a Young tableau (i.e. the entries increase along rows and columns) with distinct entries such that the set of its entries is $S$. For example, an SYT with $n$ boxes is a partial SYT with entry set $[n]$.

We are going to describe a bijection $(\pi,T,U)\leftrightarrow (\tau,P,Q)$ where

• $\pi=\begin{pmatrix}i_1 & \dots & i_s\\ j_1 & \dots & j_s\end{pmatrix},\quad \tau=\begin{pmatrix}i'_1 & \dots & i'_t\\ j'_1 & \dots & j'_t\end{pmatrix}$ are partial two-line arrays;

• $T,U$ are partial SYT's of the same shape $\mu/\lambda$ with entry sets $[n]\setminus \{j_1,\dots,j_s\}$ and $[n]\setminus \{i_1,\dots,i_s\}$;

• $P,Q$ are partial SYT's of the same shape $\nu/\mu$ with entry sets $[n]\setminus \{j'_1,\dots,j'_t\}$ and $[n]\setminus \{i'_1,\dots,i'_t\}$.

This bijection is going to work in exactly the same way as in Sagan-Stanley's paper, so we're going to redefine their internal and external insertions.

Let $R$ be a partial SYT with entry set $S$, and let $q$ be an integer not belonging to $S$. Then define the external insertion of $q$ into $R$ to be the new partial SYT denoted $R\leftarrow q$ and defined by the following algorithm: we first row-insert $q$ into the first row of $R$, then it bumps out some element $q_1$ which we then insert into the second row of $R$, and so on until either $q_i$ is just appended on the right to the row $i+1$ of $R$ (i.e. nothing is bumped) or we reach $k$-th row of $R$ in which case we get one extra entry $q_k$ of $R$ which we memorize.

Similarly, let $(i,j)$ be an inner (that is, left) corner of $R$. Define the internal insertion of $(i,j)$ into $R$ to be the new partial SYT denoted $(i,j)\to R$: remove the entry $q$ from $(i,j)$ and insert it into the next row $i+1$ of $R$. It bumps out some entry $q_{i+1}$ which we then insert into row $i+2$ of $R$ and so on until either nothing is bumped or we reach row $k$ in which case we memorize the extra entry $q_k$ that we get.

Now, here is the RSK algorithm that is going to solve the problem:

• initially, set $P=T$, $Q=\mu/\mu$ an empty tableau and $\tau:=\begin{pmatrix} \\ \end{pmatrix}$ an empty partial two-line array;
• for each $q=1,2,\dots,n$, do the following:
• if $q$ belongs to the entry set of $U$, then $q$ lies in an inner corner $(i,j)$ of $U$, so remove it from $Q$ and replace $P$ by $(i,j)\to P$;
• otherwise, if $q$ is equal to $i_m$ for some $m$, replace $P$ by $P\leftarrow j_m$;
• if we memorize an extra entry $p$ of $P$ as a result of our insertion, append $\begin{pmatrix}q\\ p \end{pmatrix}$ to $\tau$;
• otherwise, append $q$ to $Q$ in the box that was added to $P$ at the final step of the insertion.

It is easy to see that this is indeed a bijection. Another property that can be proved analogously to Theorem 3.3 in Sagan-Stanley's paper is the following symmetry of the algorithm:

if $(\pi,T,U)\leftrightarrow (\tau,P,Q)$ then $(\pi^{-1},U,T)\leftrightarrow (\tau^{-1},Q,P)$.

Here $\pi^{-1}$ is obtained from $\pi$ by first switching $i_m$ with $j_m$ for all $m$ and then sorting the columns so that the first row would be increasing. As a corollary of that, we see that the triples $(\pi,T,T)$ where $\pi=\pi^{-1}$ is an involution correspond to the triples $(\tau,P,P)$ where $\tau$ is an involution (Sagan-Stanley, Corollary 3.4). Therefore the following formula is true: $$\sum_{s=0}^n \mathrm{Inv}(n,s) \#\mathrm{SYT}_k^{n-s}(\mu/*)=\sum_{t=0}^n \mathrm{Inv}(n,t) \#\mathrm{SYT}_k^{n-t}(*/\mu),$$ where $\mathrm{Inv}(n,s)$ is the number of involutions $\pi$ with $s$ columns and with entries from $[n]$. This recurrence immediately implies the result by induction on $n$.

One can consider the semistandard version (the Knuth version) of this RSK algorithm which shows the following identity: $$\sum_{\lambda\subset \mu} s_{\mu/\lambda}=\sum_{\mu\subset \nu} s_{\nu/\mu},$$ where the sums are infinite and taken over all partitions $\lambda,\nu$ with at most $k$ parts (that are respectively to the left and right of $\mu$ in this infinite horizontal strip of height $k$). Of course, this is a stronger statement since the number of SYT's is recovered by taking the coefficient of $x_1\dots x_n$ on both parts. The stronger identity was conjectured by Alex Postnikov.

• Can that last identity be seen as a consequence of the $S_3$-symmetry of the Littlewood-Richard coefficients $c_{\nu,\mu}^{\lambda}$? – Sam Hopkins Apr 15 '16 at 20:13
• Good question, I tried that but didn't succeed. If you take inner product of both sides with $s_\kappa$ and then use the fact that skewing by $\mu$ is adjoint to multiplying by $s_\mu$, you get that the sum of L-R coefficients $C^\lambda_{\mu,\kappa}$ over all $\lambda$ equals the sum of L-R coefficients $C^\lambda_{\mu^\vee,\kappa}$ over all $\lambda$ ($\mu^\vee$ denotes rotation). But even though the sums are the same, for certain values of $\mu$ and $\kappa$ you get different lists of numbers. – Pavel Galashin Apr 15 '16 at 23:34
• Huh, very interesting. – Sam Hopkins Apr 15 '16 at 23:39

At first, we reformulate your problem. Denote $m_i=\mu_i-i$, then $m_1>m_2>\dots>m_d$. Consider $d$ bugs $B_1,\dots,B_d$ initially sitting in corresponding points $m_i$ on $\mathbb{Z}$. When we fill a box in $i$-th row, let bug $B_i$ move from its place $x$ to $x+1$. For example, in your first figure the sequence of movements is $(B_3,B_2,B_3,B_1,B_2,B_2)$. Young tableaux condition on bugs language is that no two bugs are allowed to meet. Your claim is that the number of admissible bugs movements consisting given number of $n$ steps does not change if we ask bugs move to the left instead of moving to the right.

Fix $n$. Denote, say, by $W(25,28,34)$ the number of bugs movements with $n$ steps for which $B_5$ meets $B_2$, $B_8$ meets $B_2$, $B_4$ meets $B_3$. We may write inclusion-exclusion formula for the number of not-admissible bug movements. Say, for three bugs the number of not-admissible bug movements is $W(12)+W(23)-W(12,23)$. Of course two fist summands do not change if we change direction of bugs (bijection for the first summand is just changing behaviour of $B_1$ and $B_2$). As for the third summand, the trick is that it equals $W(13)$, that also does not change after bugs reversing. For the proof of equality $W(12,23)=W(13)$ we use induction on $n$. If after first step no two bugs meet, use induction proposition. If, say, $B_2$ meets $B_1$, than the number of continuations of the movement for which $B_3$ meets $B_2$ is of course the same as the number of continuations of the movement for which $B_3$ meets $B_1$. In other words, relation $W(12,23)=W(13)$ is obvious if $B_1$ and $B_2$ have just already met. Analogous formula, but more involved, works for $W(12,23,\dots,(k-1)k)$ (everything reduces to this case after applying initial inclusion-exclusion to $W(12),W(13),\dots$).

For example, $W(12,23,34)=W(14)-W(14,23)+W(13,24)$. For proving this we again induct on $n$ and wee that it suffices to prove in the case when $B_i,B_{i+1}$ already met. In this case it reduces either to already considered case of three bugs (if $i=1$ or $i=3$) or is obvious by the very same argument, if $i=2$.

Now I formulate the formula for $W(12,23,\dots,(k-1)k)$ with general $k$. Consider all sets of segments $[a_1,b_1], [a_2,b_2],\dots,[a_m,b_m]$ with mutually distinct $2m\leqslant k$ endpoints, which cover $[1,k]$. Denote by $T$ the number of pairs of linking segments in this collection (linking is inequality $a_i<a_j<b_i<b_j$). The coefficient of $W(a_1b_1,a_2b_2,\dots,a_mb_m)$ equals $(-1)^{T+\sum a_i+\sum b_i+k-1}$. The proof is induction on $n$. Base $n=0$ consists of checking that sum of coefficients equals 1. This may be proved by additional induction on $k$. If we do not use $k-1$ as an endpoint for no $i$, this is induction proposition. If we do, then interchanging endpoints $k-1,k$ is a sign-changing involution, so such coefficients cancel. Next, we need to prove this identity in the case when some two bugs, say, $B_s$ and $B_{s+1}$ have just already met. If there is a segment $[a_i,b_i]$ such that $a_i<s<s+1<b_i$, we may add or remove the segment $[s,s+1]$, or replace role of $s,s+1$. This is sign-changing involution. If there is no such segment, we are reduced to induction proposition for $[1,s]$ and $[s+1,k]$.