Colored RSK and the multipartition square count

For each color $c$, take the subsequence of values $\sigma (i)$ with ${\kappa }_i=c$, in increasing order of their positions $i$. If its values are not $1,\dots ,m$ in that order, replace them by their increasing ranks before applying ordinary row insertion. The insertion and reverse-deletion routes use only comparisons, so this order-preserving relabelling leaves every bumping position unchanged; after reverse deletion, replace ranks by the original values in the same order. Thus [F1] gives standard insertion and recording tableaux of the same shape for every color subsequence, including an arbitrary subset of $\{1,\dots ,n\}$. At the step for position $i$, record $i$ in the new box of $Q^{(c)}$. Their entries across components are the values $1,\dots ,n$ once in $P$, and the positions $1,\dots ,n$ once in $Q$, so $P,Q$ are standard multitableaux of the same multipartition. This is the stated forward map.

To invert, begin with standard multitableaux $(P,Q)$ of common shape. At global step $i=n,n-1,\dots ,1$, there is exactly one component $c$ with recording entry $i$. Since every recording component is standard and all larger global labels have already been removed, $i$ is the largest entry in the current $Q^{(c)}$ and occupies a removable corner. Remove that box from $Q^{(c)}$. In $P^{(c)}$, replace the current set of distinct values by their increasing ranks, reverse-row-delete the same corner, and replace the expelled rank by the corresponding original value; this works because both bumping and reverse deletion use only comparisons. Define that value to be $\sigma (i)$ and set ${\kappa }_i=c$. The process is defined at every step and ends with empty tableaux.

Starting with a colored permutation and applying the inverse just defined deletes, in each component, its recording boxes in reverse time order. The inverse identity in [F1] expels exactly the value inserted at that position, so it recovers every $\sigma (i)$ and the component records every ${\kappa }_i$. Conversely, starting from $(P,Q)$ and reversing, each expelled value is reinserted into the same component at the same recording time; the insertion/reverse-deletion identity of [F1] restores that component and its new box. Induction over $i$ therefore restores the original pair. Thus the two algorithms are mutually inverse.

There are $n!$ permutations of $1,\dots ,n$ and independently $r$ choices of color at each of the $n$ positions, hence $r^{n}n!$ colored permutations. The bijection of step 2.1 sends them to the disjoint union over shapes $\lambda$ of pairs of standard multitableaux of shape $\lambda$, whose number is ${\sum }_{\lambda }(f^{\lambda }{)}^2$. This proves the square count.