Return to Answer

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 all distinct elements of $[n]$, the same is true for $j_1,\dots,j_m$, and $i_1<\dots<i_m$.

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 belonging to the set $S$. For example, an SYT with $n$ boxes is a partial SYT with entry set $[n]$.

• $\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'_s\}$ and $[n]\setminus \{i'_1,\dots,i'_s\}$.

Let $R$ be a partial SYT with entry set $S$, and let $q$ be an integer not belonging to $S$. Then define an 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 an 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.

• 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$ is 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.

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$.

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]$.

• $\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\}$.

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.

• 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.

One more definition: a partial SYT with entry set $S$ is just a Young tableau with distinct entries belonging to the set $S$. For example, an SYT with $n$ boxes is a partial SYT with entry set $[n]$.

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 belonging to the set $S$. For example, an SYT with $n$ boxes is a partial SYT with entry set $[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 conjecture since the number of SYT's is recovered by taking the coefficient of $x_1\dots x_n$ on both parts. This stronger conjecture is due to Alex Postnikov.

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.