# A Littlewood-Richardson type rule for row-strict quasisymmetric Schur functions

Jeffrey Ferreira<fnref n="1" />†

**Abstract.** We establish several properties of an algorithm defined by Mason and Remmel (2010) which inserts a positive integer into a row-strict composition tableau. These properties lead to a Littlewood-Richardson type rule for expanding the product of a row-strict quasisymmetric Schur function and a symmetric Schur function in terms of row-strict quasisymmetric Schur functions.

**Résumé.** Nous établissons plusieurs propriétés d’un algorithme défini par Mason et Remmel (2010), qui insère un entier positif dans un tableau dont la forme est une composition, avec ordre strict sur les lignes (row-strict). Ces propriétés conduisent à une règle de type Littlewood-Richardson pour étendre le produit d’une fonction de Schur quasi-symétrique “row-strict” et d’une fonction de Schur symétrique en termes de fonctions de Schur quasi-symétriques “row-strict”.

**Keywords:** Littlewood-Richardson rule, quasisymmetric function, Schur function

## 1 Introduction

Quasisymmetric functions were defined by Gessel in [5] where he developed many of their properties, although quasisymmetric functions had already appeared in earlier work of Stanley [14]. Since their introduction, quasisymmetric functions have become of increasing importance. They have appeared in such areas of mathematics as representation theory [9], symmetric function theory [3], and combinatorial Hopf algebras [1].

In [7], the authors define a new basis $CS_\alpha$ for the algebra $QSym$ of quasisymmetric functions, where $\alpha$ is a sequence of positive integers called a *strong composition*. In a fixed number of variables, the functions $CS_\alpha$ are defined to be a certain positive integral sum of Demazure atoms. Demazure atoms first appeared in [10] and later were characterized as specializations of nonsymmetric Macdonald polynomials when $q = t = 0$ [12]. A subset of the functions $CS_\alpha$, in a finite number of variables, were shown in [11] to give a basis of the coinvariant space of quasisymmetric polynomials, thus proving a conjecture of Bergeron and Reutenauer in [2].

In [8] the authors give a Littlewood-Richardson type rule for expanding the product $CS_\alpha s_\lambda$, where $s_\lambda$ is the symmetric Schur function, as a nonnegative integral sum of the functions $CS_\beta$. This rule relied on their

<footnote n="1">¹University of California, Davis, Department of Mathematics, Davis, CA, USA</footnote>

<footnote>†Supported in part by NSF VIGRE grant DMS0636297.</footnote>
combinatorial definition for $CS_\alpha$ as the generating function of column-strict composition tableaux, which are certain fillings of strong composition shape $\alpha$ with positive integers. These column-strict composition tableaux are defined by imposing three relations among certain sets of entries in the fillings of $\alpha$. The proof of the Littlewood-Richardson type rule in [8] utilized an analogue of Schensted insertion on tableaux, which is an algorithm in classical symmetric function theory which inserts a positive integer $b$ into a tableau $T$.

In [13], the authors provide a row-strict analogue of column-strict composition tableaux; specifically they interchange the roles of weak and strict in each of the three relations mentioned above. One of these relations requires the fillings to decrease strictly in each row, thus the name row-strict composition tableaux. Also contained in [13] is an insertion algorithm which inserts a positive integer $b$ into a row-strict composition tableau, producing a new row-strict composition tableau.

This article establishes several new properties of the insertion algorithm given in [13]. If we define $RS_\alpha$ to be the generating function of row-strict composition tableaux of shape $\alpha$, then the properties of this algorithm lead directly to a Littlewood-Richardson type rule for expanding the product $RS_\alpha s_\lambda$ as a nonnegative integral sum of the function $RS_\beta$. The combinatorics of this rule contain many similarities to the classical Littlewood-Richardson rule for multiplying two Schur functions, see [4] for example.

## 1.1 Compositions and reverse lattice words

A strong composition $\alpha = (\alpha_1, \dots, \alpha_k)$ with $k$ parts is a sequence of positive integers. A weak composition $\gamma = (\gamma_1, \dots, \gamma_k)$ with $k$ parts is a sequence of nonnegative integers. A partition $\lambda = (\lambda_1, \dots, \lambda_k)$ with $k$ parts is a weakly decreasing sequence of positive integers. Let $\lambda^* := (\lambda_k, \lambda_{k-1}, \dots, \lambda_1)$ be the reverse of $\lambda$, and let $\lambda^t$ denote the transpose of $\lambda$. Denote by $\tilde{\alpha}$ the unique partition obtained by placing the parts of $\alpha$ in weakly decreasing order. Denote by $\gamma^+$ the unique strong composition obtained by removing the zero parts of $\gamma$. For any sequence $\beta = (\beta_1, \dots, \beta_k)$ with $k$ parts let $l(\beta) := k$ be the length of $\beta$. For $\gamma$ and $\beta$ arbitrary (possibly weak) compositions of the same length $k$ we say $\gamma$ is contained in $\beta$, denoted $\gamma \subseteq \beta$, if $\gamma_i \le \beta_i$ for all $1 \le i \le k$. For $\alpha$ and $\beta$ strong compositions, we say $\beta$ is a refinement of $\alpha$, denote $\beta \le \alpha$, if $\alpha$ can be obtained by summing consecutive parts of $\beta$. That is, $\beta \le \alpha$ if $\alpha_1 = \beta_1 + \dots + \beta_i$, $\alpha_2 = \beta_{i+1} + \dots + \beta_j$, $\alpha_3 = \beta_{j+1} + \dots + \beta_m$, and so on.

A finite sequence $w = w_1w_2\cdots w_n$ of positive integers with largest part size $m$ is called a reverse lattice word if in every prefix of $w$ there are at least as many $i$'s as $(i-1)$'s for each $1 < i \le m$. The content of a word $w$ is the sequence $\text{cont}(w) = (\text{cont}(w)_1, \dots, \text{cont}(w)_m)$ with the property that $\text{cont}(w)_i$ equals the number of times $i$ appears in $w$. A reverse lattice word is called regular if $\text{cont}(w)_1 \ne 0$. Note that if $w$ is a regular reverse lattice word, then $\text{cont}(w) = \lambda^*$ for some partition $\lambda$.

## 1.2 Diagrams and fillings

To any sequence $\beta$ of nonnegative integers we may associate a diagram, also denoted $\beta$, of left justified boxes with $\beta_i$ boxes in the $i$th row from the top. In the case $\beta = \lambda$ is a partition, the diagram of $\lambda$ is the usual Ferrers diagram in English notation. Given a diagram $\beta$, let $(i, j)$ denote the box in the $i$th row and $j$th column.

Given two sequences $\gamma$ and $\beta$ of the same length $k$ such that $\gamma \subseteq \beta$, define the skew diagram $\beta/\gamma$ to be the array of boxes that are in $\beta$ and not in $\gamma$. The boxes in $\gamma$ are called the *skewed boxes*. For each skew diagram contained in this article, an extra column with $k$ boxes will be added strictly to the left of each existing column so that the $i$th row of $\beta/\gamma$ has $(\beta_i + 1) - (\gamma_i + 1)$ boxes. This new column will be called the *0th column*.
A filling $U$ of a diagram $\beta$ is an assignment of positive integers to the boxes of $\beta$. Given a filling $U$ of $\beta$, let $U(i, j)$ be the entry in the box $(i, j)$. A reverse row-strict tableau, or just tableau, $T$ is a filling of partition shape $\lambda$ such that each row strictly decreases when read left to right and each column weakly decreases when read top to bottom. If $\lambda$ is a partition with $\lambda_1 = m$, then let $T_\lambda$ be the tableau of shape $\lambda$ which has the entire $i$th column filled with the entry $(m+1-i)$ for all $1 \le i \le m$.

A filling of a skew diagram $\beta/\gamma$ is an assignment of positive integers to the boxes that are in $\beta$ and not in $\gamma$. We follow the convention that each box in the 0th column and each skewed box is assigned a virtual $\infty$ symbol. Once filled, two such boxes in the same row are defined to strictly decrease, while two such boxes in the same column are defined to be equal.

The column reading order of a (possibly skew) diagram is the total order $<_{col}$ on its boxes where $(i, j) <_{col} (i', j')$ if $j < j'$ or $(j = j'$ and $i > i'$). This is the total order obtained by reading the boxes from bottom to top in each column, starting with the left-most column and working rightwards. The column reading word of a (possibly skew) filling $U$ is the sequence of integers $w_{col}(U)$ obtained by reading the entries of $U$ in column reading order, where we ignore entries from skewed boxes and entries in the 0th column. The content of any filling $U$ of partition or composition shape, denoted $\text{cont}(U)$, is the content of its column reading word $w_{col}(U)$. To any filling $U$ we may associate a monomial
$$x^U = \prod_{i \ge 1} x_i^{\text{cont}(U)_i}.$$

The following definition first appeared in [13].

**Definition 1** Let $\alpha$ be a strong composition with $k$ parts with largest part size $m$. A row-strict composition tableau (RCT) $U$ is a filling of the diagram $\alpha$ such that

1. The first column is weakly increasing when read top to bottom.

2. Each row strictly decreases when read left to right.

3. Triple Rule: Supplement $U$ with zeros added to the end of each row so that the resulting filling $\hat{U}$ is of rectangular shape $k \times m$. Then for $1 \le i_1 < i_2 \le k$ and $2 \le j \le m$,

$$ (\hat{U}(i_2, j) \neq 0 \text{ and } \hat{U}(i_2, j) > \hat{U}(i_1, j)) \Rightarrow \hat{U}(i_2, j) \geq \hat{U}(i_1, j-1). $$

If we let $\hat{U}(i_2, j) = b$, $\hat{U}(i_1, j) = a$, and $\hat{U}(i_1, j-1) = c$, then the Triple Rule ($b \neq 0$ and $b > a$ implies $b \ge c$) can be pictured as

<figure><img src="image_1.png" /></figure>

A row-strict composition tableau is called *standard* if each of the entries $\{1, 2, \dots, n\}$ appears exactly once. Given a standard row-strict composition tableau $U$, define its *descent set* $D(U)$ to be the set of all entries $b$ such that the entry $b+1$ appears in a column strictly to the right of the column containing $b$.

Inversion triples were originally introduced by Haglund, Haiman, and Loehr in [6] to describe a combinatorial formula for symmetric Macdonald polynomials. In this article inversion triples are defined as
follows. Let $\gamma$ be a (possibly weak) composition and let $\beta$ be a strong composition with $\gamma \subseteq \beta$. Let $U$ be some arbitrary filling of $\beta/\gamma$. A Type A triple is a triple of entries

$$U(i_1, j-1) = c, U(i_1, j) = a, U(i_2, j) = b$$

in $U$ with $\beta_{i_1} \ge \beta_{i_2}$ for some rows $i_1 < i_2$ and some column $j > 0$. A Type B triple is a triple of entries

$$U(i_1, j) = b, U(i_2, j) = c, U(i_2, j+1) = a$$

in $U$ with $\beta_{i_1} < \beta_{i_2}$ for some rows $i_1 < i_2$ and some column $j \ge 0$. A triple of either type is said to be an inversion triple if either $b \le a < c$ or $a < c \le b$. Note that triples of either type may involve boxes in the 0th column. Type A and Type B triples can be visualized as

<figure><img src="image_2.png" /></figure>

Central to Theorem 13 in Section 3 is the following definition.

**Definition 2** Let $\beta$ and $\alpha$ be strong compositions. Let $\gamma$ be some (possibly weak) composition satisfying $\gamma^+ = \alpha$. A Littlewood-Richardson skew row-strict composition tableau $S$, or LR skew RCT, of shape $\beta/\alpha$ is a filling of a diagram of skew shape $\beta/\gamma$ such that

1. Each row strictly decreases when read left to right.

2. Every Type A and Type B triple is an inversion triple.

3. The column reading word of $S$, $w_{col}(S)$, is a regular reverse lattice word.

Note that in Definition 2, the filling is defined to be of a diagram of skew shape $\beta/\gamma$ where $\gamma^+ = \alpha$ for some fixed $\alpha$. Thus, we define the shape of a LR skew RCT to be $\beta/\alpha$.

**Example 3** Below is a RCT, $U$, which has shape $(1, 3, 2, 2)$, and a LR skew RCT, $S$, which has shape $(1, 2, 3, 1, 5, 3)/(1, 3, 2, 2)$ with $w_{col}(S) = 4433421$.

<figure><img src="image_3.png" /></figure>

## 1.3 Generating functions

The algebra of symmetric functions $\Lambda$ has many bases, of which the Schur functions $s_\lambda$ are arguably the most important. The Schur function $s_\lambda$ can be defined in a number of ways. In this article it is advantageous to define $s_\lambda$ as the generating function of reverse row-strict tableaux of shape $\lambda^t$. That is
$$s_{\lambda} = \sum x^T$$

where the sum is over all reverse row-strict tableaux $T$ of shape $\lambda^t$.

The algebra QSym of quasisymmetric functions also has several interesting bases, two of which we recall here. The monomial quasisymmetric function basis $M_\alpha$ is given by

$$M_{\alpha} = \sum_{i_1 < i_2 < \dots < i_k} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \dots x_{i_k}^{\alpha_k}$$

where $\alpha$ is a strong composition. In [5], Gessel defines the fundamental quasisymmetric function basis, which can be expressed as

$$F_{\alpha} = \sum_{\beta \le \alpha} M_{\beta}$$

where $\alpha$ and $\beta$ are strong compositions such that $\beta$ is a refinement of $\alpha$.

The generating function of row-strict composition tableaux of shape $\alpha$ are denoted $RS_\alpha$. That is,

$$RS_{\alpha} = \sum x^{U}$$

where the sum is over all row-strict composition tableaux $U$ of shape $\alpha$. The generating functions $RS_\alpha$ are called row-strict quasisymmetric Schur functions and were originally defined in [13].

In [13] the authors show $RS_\alpha$ are indeed quasisymmetric, and furthermore the collection of all $RS_\alpha$, as $\alpha$ ranges over all strong compositions, forms a basis of the algebra QSym of quasisymmetric functions. This result is obtained by expressing the functions $RS_\alpha$ in terms of the fundamental basis $F_\beta$ of quasisymmetric functions.

**Proposition 4** [13] Let $\alpha$ and $\beta$ be strong compositions of $n$. Then

$$RS_{\alpha} = \sum_{\beta} d_{\alpha\beta} F_{\beta}$$

where $d_{\alpha\beta}$ is equal to the number of standard row-strict composition tableaux $U$ of shape $\alpha$ such that $comp(D(U)) := (b_1, b_2 - b_1, \dots, b_k - b_{k-1}, n - b_k) = \beta$. Here, $D(U) = \{b_1, b_2, \dots, b_k\}$ is the descent set of $U$.

In [13] the authors show the transition matrix given by the coefficients $d_{\alpha\beta}$ is upper uni-triangular. Hence the collection of all $RS_\alpha$ form a basis of QSym.

The relation between row-strict quasisymmetric Schur functions and symmetric Schur functions is given in [13] by

$$s_{\lambda} = \sum_{\alpha: \tilde{\alpha} = \lambda^t} RS_{\alpha}.$$

The well-known involution $\omega$ on symmetric functions acts on the Schur basis by the formula $\omega(s_\lambda) = s_{\lambda^t}$. An extension of $\omega$ to quasisymmetric functions appears in [5], and can be defined on the fundamental quasisymmetric functions by the formula $\omega(F_\alpha) = F_{\alpha*}$. Using Proposition 4 the authors in [13] describe the action of $\omega$ on row-strict quasisymmetric Schur functions.
**Theorem 5** [13] Let $\alpha$ be a strong composition of $n$. Let $CS_\alpha$ be the column-strict quasisymmetric Schur function indexed by $\alpha$ (see [7]). Then

$$ \omega(\mathcal{RS}_\alpha(x_1, x_2, \dots, x_n)) = \mathcal{CS}_\alpha(x_n, x_{n-1}, \dots, x_1). $$

In a separate but related work, we show that a certain subset of $\mathcal{RS}_\alpha$ are a basis for the coinvariant space of quasisymmetric functions. This proof is analogous to the proof appearing in [11]. Unlike the functions $CS_\alpha$, there is to date no representation theoretic interpretation of the functions $\mathcal{RS}_\alpha$. It would be interesting to know whether such an interpretation exists.

## 2 Insertion algorithms

Let $A$ be a matrix with finitely many nonzero entries, each entry in $\mathbb{N}$. Associate to $A$ a two-line array $w_A$ by letting

$$ w_A = \begin{pmatrix} i_1 & i_2 & \cdots & i_m \\ j_1 & j_2 & \cdots & j_m \end{pmatrix} $$

where $i_r, j_r$ are positive integers for $1 \le r \le m$, and (a) $i_1 \ge i_2 \ge \cdots \ge i_m$, (b) if $i_r = i_s$ and $r \le s$ then $j_r \le j_s$, and (c) there are exactly $a_{ij}$ numbers $r$ such that $(i_r, j_r) = (i, j)$ for each pair $(i, j)$. Denote by $\tilde{w}_A$ the sequence $i_1, i_2, \dots, i_m$ and denote by $\tilde{w}_A$ the sequence $j_1, j_2, \dots, j_m$.

The classical Robinson-Schensted-Knuth (RSK) correspondence gives a bijection between two-line arrays $w_A$ and pairs of (reverse row-strict) tableaux $(P, Q)$ of the same shape [4]. The basic operation of RSK is Schensted insertion on tableaux, which is an algorithm that inserts a positive integer $b$ into a tableau $T$ to produce a new tableau $T'$. In our setting, Schensted insertion can be stated as

**Definition 6** Given a tableau $T$ and $b$ a positive integer one can obtain $T' := b \to T$ by inserting $b$ as follows:

1. Let $\tilde{b}$ be the largest entry less than or equal to $b$ in the first row of $T$. If no such $\tilde{b}$ exists, simply place $b$ at the end of the first row.

2. If $\tilde{b}$ exists, replace (bump) $\tilde{b}$ with $b$ and proceed to insert $\tilde{b}$ into the second row using the method just described.

The authors in [13] provide an analogous algorithm on row-strict composition tableaux.

**Definition 7** (RCT Insertion) Let $U$ be a RCT with longest row of length $m$, and let $b$ be a positive integer. One can obtain $U' := U \leftarrow b$ by inserting $b$ as follows. Scan the entries of $U$ in reverse column reading order, that is top to bottom in each column starting with the right-most column and working leftwards, starting with column $m+1$ subject to the conditions:

1. In column $m+1$, if the current position is at the end of a row of length $m$, and $b$ is strictly less than the last entry in that row, then place $b$ in this empty position and stop. If no such position is found, begin scanning at the top of column $m$.

2. (a) Inductively, suppose some entry $b_j$ begins scanning at the top of column $j$. In column $j$, if the current position is empty and at the end of a row of length $j-1$, and $b_j$ is strictly less than the last entry in that row, then place $b_j$ in this empty position and stop.
(b) If a position in column $j$ is nonempty and contains $\tilde{b}_j \le b_j$ such that $b_j$ is strictly less than the entry immediately to the left of $\tilde{b}_j$, let $b_j$ bump $\tilde{b}_j$ and continue scanning column $j$ with the entry $\tilde{b}_j$, bumping whenever possible. After scanning the last entry in column $j$, begin scanning column $j-1$.

3. If an entry $b_1$ is bumped into the first column, then place $b_1$ in a new row that appears after the last entry in the first column that is weakly less than $b_1$.

In [13] the authors show $U' = U \leftarrow b$ is a row-strict composition tableau. The algorithm of inserting $b$ into $U$ determines a set of boxes in $U'$ called the *insertion path of $b$* and denoted $I(b)$, which is precisely the set of boxes in $U'$ which contain an entry bumped during the algorithm. We call the row in $U'$ in which the new box is added the *row augmented by insertion*. We establish several new lemmas concerning RCT insertion that are instrumental in proving the main theorem in Section 3.

**Lemma 8** Let $U$ be a RCT and $b$ be a positive integer. Then each row of $U' = U \leftarrow b$ contains at most one box from $I(b)$.

**Lemma 9** Let $U$ be a RCT and $b$ be a positive integer. Let $U' = U \leftarrow b$ with row $i$ of $U'$ being the row augmented by insertion. Then for all rows $r > i$ of $U'$, the length of row $r$ is not equal to the length of row $i$.

**Lemma 10** (Main Bumping Lemma) Let $U$ be a RCT, and let $a, b$, and $c$ be positive integers with $a < b \le c$. Consider successive insertions $U_1 := (U \leftarrow b) \leftarrow c$ and $U_2 := (U \leftarrow b) \leftarrow a$. Let $B_a = (i_a, j_a)$, $B_b = (i_b, j_b)$, and $B_c = (i_c, j_c)$ be the new boxes created after inserting $a, b$, and $c$, respectively, into the appropriate RCT. Let $i_1$ be a row in $U_1$ which contains a box $(i_1, j_1)$ from $I(b)$ and a box $(i_1, j'_1)$ from $I(c)$. Similarly, let $i_2$ be a row in $U_2$ which contains a box $(i_2, j_2)$ from $I(b)$ and a box $(i_2, j'_2)$ from $I(a)$. Then

1. In $U_1$, $j_c \le j_b$. In $U_2$, $j_a > j_b$.

2. In $U_1$, $j'_1 \le j_1$. In $U_2$, $j'_2 > j_2$.

Part (1.) of Lemma 10 says the new box $B_c$ is weakly left of the new box $B_b$ in $U_1$, and the new box $B_a$ is strictly right of the new box $B_b$ in $U_2$. Part (2.) of Lemma 10 says that in any row which contains a box from both $I(b)$ and $I(c)$, or from both $I(b)$ and $I(a)$, then in this row $I(c)$ is weakly left of $I(b)$ in $U_1$, and $I(a)$ is strictly right of $I(b)$ in $U_2$.

**Lemma 11** Consider the RCT obtained after $n$ successive insertions

$$U_n := (\cdots ((U \leftarrow b_1) \leftarrow b_2) \cdots) \leftarrow b_n$$

with $b_1 \le b_2 \le \cdots \le b_n$. Let $B_1, B_2, \dots, B_n$ be the corresponding new boxes. Then in $U_n$,

$$B_n <_{col} B_{n-1} <_{col} \cdots <_{col} B_1.$$

Knuth's contribution to the RSK algorithm included describing Schensted insertion in terms of two elementary transformations $K_1$ and $K_2$ which act on words $w$. Let $a, b$, and $c$ be positive integers. Then
$$ 
\begin{array}{l}
\mathcal{K}_1: bca \to bac \quad \text{if } a < b \le c \\
\mathcal{K}_2: acb \to cab \quad \text{if } a \le b < c
\end{array}
$$

The relations $\mathcal{K}_1, \mathcal{K}_2$, and their inverses $\mathcal{K}_1^{-1}, \mathcal{K}_2^{-1}$, act on words $w$ by transforming triples of consecutive letters. Denote by $\stackrel{1}{\cong}$ the equivalence relation defined by using $\mathcal{K}_1$ and $\mathcal{K}_1^{-1}$. That is, $w \stackrel{1}{\cong} w'$ if and only if $w$ can be transformed into $w'$ using a finite sequence of transformations $\mathcal{K}_1$ or $\mathcal{K}_1^{-1}$. The following lemma is extremely useful in proving Theorem 13.

**Lemma 12** Let $U$ be a RCT and let $w$ and $w'$ be two words such that $w \stackrel{1}{\cong} w'$. Then

$$ U \leftarrow w = U \leftarrow w'. $$

## 3 Littlewood-Richardson type rule

The main theorem of this article is the following.

**Theorem 13** Let $s_\lambda$ be the Schur function indexed by the partition $\lambda$, and let $RS_\alpha$ be the row-strict quasisymmetric Schur function indexed by the strong composition $\alpha$. We have

$$ RS_{\alpha} \cdot s_{\lambda} = \sum_{\beta} C_{\alpha, \lambda}^{\beta} RS_{\beta} \qquad (1) $$

where $C_{\alpha, \lambda}^{\beta}$ is the number of Littlewood-Richardson skew RCT of shape $\beta/\alpha$ and content $\lambda$*.

Theorem 13 is established by constructing a bijection $\rho$ between pairs $(U, T)$ and $(V, S)$, where $U$ is a RCT of shape $\alpha$, $T$ a tableau of shape $\lambda^t$, $V$ is a RCT of shape $\beta$, and $S$ is a LR skew RCT of shape $\beta/\alpha$ and content $\lambda$*.

Specifically, the bijection $\rho$ is obtained in the following way. First, use RSK to map the pair $(T, T_\lambda)$ to a two-line array $w_A$. Then perform the insertion $U \leftarrow \tilde{w}_A$ while simultaneously recording in a skew shape each new box, using the letters of $\hat{w}_A$ in order. The result is a pair $(V, S)$. To invert this procedure, perform the inverse of insertion on $V$ using $S$ in the following way. Find each occurrence of the entry 1 in $S$. Un-insert the entries in the corresponding boxes in $V$ according to the order they appear with respect to $<_{col}$; that is, the smallest box in column reading order is un-inserted first. After each entry is un-inserted we get a pair $(1, j)$. Inductively, find each occurrence of $i$ in $S$ and un-insert the entries in the corresponding boxes of $V$ in the order they appear with respect to $<_{col}$, each time producing a pair $(i, j)$ for some $j$. When all entries have been removed from $S$, the result is a pair $(U, T)$.

Below is an example of the bijection $\rho$ using the RCT of Example 3 and following the notation established above.

$$ U = \begin{array}{c} \begin{array}{|c|c|c|c|} \hline 1 \\ \hline 4 & 3 & 2 \\ \hline 5 & 4 \\ \hline 5 & 3 \\ \hline \end{array} \\ \text{The number of Littlewood-Richardson skew RCTs of shape } \beta/\alpha \text{ and content } \lambda^t \end{array} $$

$$ T = \begin{array}{c} \begin{array}{|c|c|c|c|} \hline 4 & 3 & 2 & 1 \\ \hline 4 & 3 \\ \hline 2 \\ \hline \end{array} \\ \text{The number of Littlewood-Richardson skew RCTs of shape } \beta/\alpha \text{ and content } \lambda^t \end{array} $$

$$ T_{\lambda} = \begin{array}{c} \begin{array}{|c|c|c|c|} \hline 4 & 3 & 2 & 1 \\ \hline 4 & 3 \\ \hline 4 \\ \hline \end{array} \\ \text{The number of Littlewood-Richardson skew RCTs of shape } \beta/\alpha \text{ and content } \lambda^t \end{array} $$

$$ (T, T_{\lambda}) \stackrel{\text{RSK}}{\Rightarrow} \begin{pmatrix} 4 & 4 & 4 & 3 & 3 & 2 & 1 \\ 2 & 4 & 4 & 3 & 3 & 2 & 1 \end{pmatrix} $$
<figure><img src="image_4.png" /></figure>

References

[1] M. Aguiar, N. Bergeron, and F. Sottile. Combinatorial Hopf algebras and generalized Dehn-Sommerville relations. *Compos. Math.*, 142(1):1-30, 2006.

[2] F. Bergeron and C. Reutenauer. The coinvariant space for quasisymmetric polynomials. Unpublished manuscript.

[3] N. Bergeron, S. Mykytiuk, F. Sottile, and S. van Willigenburg. Noncommutative Pieri operators on posets. *J. Combin. Theory Ser. A*, 91(1-2):84-110, 2000.

[4] W. Fulton. *Young Tableaux*, volume 35 of *London Mathematical Society Student Texts*. Cambridge University Press, Cambridge, 1997.

[5] I. M. Gessel. Multipartite P-partitions and inner products of skew Schur functions. In *Combinatorics and algebra (Boulder, Colo., 1983)*, volume 34 of *Contemp. Math.*, pages 289-317. Amer. Math. Soc., Providence, RI, 1984.

[6] J. Haglund, M. Haiman, and N. Loehr. A combinatorial formula for Macdonald polynomials. *J. Amer. Math. Soc.*, 18(3):735-761 (electronic), 2005.

[7] J. Haglund, K. Luoto, S. Mason, and S. van Willigenburg. Quasisymmetric Schur functions. arXiv:0810.2489, 2008.

[8] J. Haglund, K. Luoto, S. Mason, and S. van Willigenburg. Refinements of the Littlewood-Richardson rule. arXiv:0908.3540, 2009.

[9] F. Hivert. Hecke algebras, difference operators, and quasi-symmetric functions. *Adv. Math.*, 155(2):181-238, 2000.

[10] A. Lascoux and M.-P. Schützenberger. Keys & standard bases. In *Invariant theory and tableaux (Minneapolis, MN, 1988)*, volume 19 of *IMA Vol. Math. Appl.*, pages 125-144. Springer, New York, 1990.

[11] A. Lauve and S. Mason. QSym over Sym has a stable basis. arXiv:1003.2124, 2010.

[12] S. Mason. An explicit construction of type A Demazure atoms. *J. Algebraic Combin.*, 29(3):295-313, 2009.

[13] S. Mason and J. Remmel. A dual basis to quasisymmetric Schur functions. to appear, 2010.

[14] R. P. Stanley. *Ordered structures and partitions*. American Mathematical Society, Providence, R.I., 1972. *Memoirs of the American Mathematical Society*, No. 119.