Reduction formulae from the factorization
Theorem of Littlewood-Richardson
polynomials by King, Tollu and Toumazet†

Soojin Cho<fnref n="1" />‡ and Eun-Kyoung Jung<fnref n="1" /> and Dongho Moon<fnref n="2" />§

**Abstract.** The factorization theorem by King, Tollu and Toumazet gives four different reduction formulae of Littlewood-Richardson coefficients. One of them is the classical reduction formula of the first type while others are new. Moreover, the classical reduction formula of the second type is not a special case of KTT theorem. We give combinatorial proofs of reduction formulae in terms of tableaux or hives. The proofs for the cases $r = 1, 2, n - 2$ in terms of tableaux and the proof for the classical reduction formula of the second type in terms of hives are new.

**Résumé.** Le Théorème de factorisation par King, Tollu, et Toumazet donne quatre formules différentes de réduction des coefficients de Littlewood-Richardson. L'une d'entre eux est la formule classique de réduction du premier type alors que les trois autres sont nouvelles. De plus, la formule classique de réduction du deuxième type n'est pas un cas spécial du KTT théorème. Nous donnons preuves combinatoires des formules de réduction en termes de tableaux ou hives. Les preuves pour les cas $r = 1, 2, n - 2$ en termes de tableaux et la preuve pour la formule classique de réduction du deuxième type en termes de hives sont nouvelles.

**Keywords:** Reduction formulae; KTT factorization theorem; Littlewood-Richardson coefficients.

# 0 Introduction

Littlewood-Richardson coefficients $c_{\lambda\mu}^{\nu}$ are important in many fields of mathematics. They count the number of column strict (skew) tableaux on the shape $\nu/\lambda$ of content $\mu$ that satisfy a certain condition on a word derived from the tableau, which we call a *Littlewood-Richardson tableau*. They explain the rule of multiplication of two Schur functions; $s_{\lambda} \cdot s_{\mu} = \sum_{\nu} c_{\lambda\mu}^{\nu} s_{\nu}$, and the tensor product of two irreducible polynomial representations of $GL_n(\mathbb{C})$; $V(\lambda) \otimes V(\mu) = \bigoplus_{\nu} c_{\lambda\mu}^{\nu} V(\nu)$. They also appear in the Schubert calculus of Grassmannians; $\sigma_{\lambda} \cdot \sigma_{\mu} = \sum_{\nu} c_{\lambda\mu}^{\nu} \sigma_{\nu}$, where $\sigma_{\lambda}$ is the Schubert class in the cohomology ring of a Grassmannian, indexed by the partition $\lambda$.

<footnote n="1">¹ Department of Mathematics, Ajou University, Suwon 443-749, Korea</footnote>

<footnote n="2">² Department of Applied Mathematics, Sejong University, Seoul 143-747, Korea</footnote>

<footnote>†This research was done while authors were visiting Korea Institute for Advanced Study.</footnote>

<footnote>‡The author was supported by a grant from Ajou University.</footnote>

<footnote>§The author was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2007-313-C00019).</footnote>
For given partitions $\lambda, \mu$ and $\nu$, a *stretched Littlewood-Richardson coefficient* with a stretched parameter $t$, where $t$ is a positive integer, is defined to be the Littlewood-Richardson coefficient $c_{t\lambda t\mu}^{t\nu}$. It was conjectured by R. King, C. Tollu and F. Toumazet (5) that there exists a polynomial $P_{\lambda\mu}^{\nu}(t)$ with non-negative rational coefficients such that $P_{\lambda\mu}^{\nu}(0) = 1$ and $P_{\lambda\mu}^{\nu}(t) = c_{t\lambda t\mu}^{t\nu}$ for all positive integers $t$. The polynomiality of $c_{t\lambda t\mu}^{t\nu}$ has been proved in (2; 10). The corresponding polynomial $P_{\lambda\mu}^{\nu}(t)$ is called a *Littlewood-Richardson polynomial*.

Inspired by the Saturation Theorem by A. Knutson and T. Tao (8) and the properties of puzzles that serve as a model of Littlewood-Richardson coefficients introduced by Knutson et al. (9), King, Tollu and Toumazet made a conjecture on the factorization of Littlewood-Richardson polynomials and it has been proved by themselves (7): In this article we call this *KTT theorem* for short.

Roughly speaking, the factorization theorem states that if $c_{\lambda\mu}^{\nu} > 0$ and any one of Horn's inequalities is an equality, then $c_{\lambda\mu}^{\nu}$ can be written as a product of two Littlewood-Richardson coefficients indexed by certain subpartitions of $\lambda, \mu, \nu$, respectively, and hence the corresponding Littlewood-Richardson polynomial $P_{\lambda\mu}^{\nu}(t)$ factorizes also.

One may observe that if the given index sets in the theorem have cardinality 1, 2, $(n-1)$ or $(n-2)$, then KTT theorem gives a reduction formula of Littlewood-Richardson coefficients since there exists a unique Littlewood-Richardson tableau, if there is, when the length of partitions are at most 2. We only focus on this aspect of the theorem and observe that it is the classical reduction formula (see (4)) of the first type when the size of index sets are all $(n-1)$, while it gives new types of reductions when the size of index sets are all 1, 2 or $(n-2)$. The classical reduction formula of the second type is not a special case of KTT theorem though.

Our main concern is on combinatorial proofs of reduction formulae of Littlewood-Richardson coefficients. The proof of the factorization theorem in (7) gives combinatorial proof for reduction formulae in terms of hives, and we give proofs in terms of tableaux in this article. For the classical reduction formula of the second type, we introduce a combinatorial proof based on hives also since this is not a special case of KTT theorem.

# 1 KTT Theorem and its special cases

A *partition* $\lambda = (\lambda_1, \lambda_2, \ldots)$ is a nonincreasing sequence of nonnegative integers with finite number of positive numbers. The *size* of $\lambda$ is $|\lambda| = \sum_i \lambda_i$ and the *length* of $\lambda$, $\ell(\lambda)$, is the number of positive numbers in $\lambda$. The *Young diagram* of a partition $\lambda$ is a left-justified array of boxes with $\lambda_i$ boxes in its $i$th row. For a partition $\lambda$, $\tilde{\lambda}$ is the *conjugate* of $\lambda$, whose diagram is obtained by interchanging rows and columns of $\lambda$. For two partitions $\lambda = (\lambda_1, \lambda_2, \ldots)$, $\nu = (\nu_1, \nu_2, \ldots)$, we write $\lambda \subseteq \nu$, if $\lambda_i \le \nu_i$ for all $i$. For partitions $\lambda, \nu$ with $\lambda \subseteq \nu$, the *skew diagram* of shape $\nu/\lambda$ is the diagram consisting of boxes of $\nu$ which are not the boxes of $\lambda$. A *skew tableau* of shape $\nu/\lambda$ with *content* $\mu = (\mu_1, \mu_2, \ldots)$ is a filling of boxes of a skew diagram $\nu/\lambda$ with $\mu_i$ $i$'s, where entries are weakly increasing in rows and strictly increasing in columns. The *reverse row word* of a skew tableau $T$, denoted by $w(T)$, is the word obtained by reading the entries of $T$ from right to left and top to bottom. A word $w = x_1 \cdots x_r$ is called a *lattice word* if, for any $s \le r$ and $i, x_1 \cdots x_s$ contains at least as many $i$'s as it contains $(i+1)$'s. A skew tableau $T$ is a *Littlewood-Richardson skew tableau* (LR-tableau) if its reverse row word $w(T)$ is a lattice word.

**Definition 1.1.** Given three partitions $\lambda, \mu$ and $\nu$, the *Littlewood-Richardson coefficient* (LR-coefficient) $c_{\lambda,\mu}^{\nu}$ is the number of LR-tableaux on the shape $\nu/\lambda$ of content $\mu$.
When $n$ is a positive integer, we let $[n] = \{1, \dots, n\}$. Let $r \le n$ be a pair of positive integers, $I = \{i_1, i_2, \dots, i_r\}$, $i_1 < i_2 < \dots < i_r$, be an $r$-subset of $[n]$, and $\lambda$ be a partition with $\ell(\lambda) \le n$. Then, we define $\pi(I) = (i_r - r, i_{r-1} - (r-1), \dots, i_1 - 1)$ as a partition associated to $I$ and $\lambda_I = (\lambda_{i_1}, \dots, \lambda_{i_r})$ as a subpartition of $\lambda$. Denoted by $I^c$, we mean the complement of $I$ in $[n]$, i.e. $I^c = [n] - I$.

**Definition 1.2.** For a pair of two positive integers $r \le n$, define a set of triples of $r$-subsets of $[n]$ as follows: $R_r^n = \{(I, J, K) \mid I, J, K$ are $r$-subsets of $[n]$, $c_{\pi(I)\pi(J)}^{\pi(I)} = 1\}$.

Now we state a KTT theorem on the factorization of LR-coefficients and hence of LR-polynomials.

**Theorem 1.3 (KTT factorization Theorem) (7).** Let $\lambda, \mu$ and $\nu$ be partitions of lengths at most $n$ with $c_{\lambda\mu}^{\nu} > 0$. Suppose that there exists $(I, J, K) \in R_r^n$ with $r < n$, which satisfies the equality $\sum_{k \in K} \nu_k = \sum_{i \in I} \lambda_i + \sum_{j \in J} \mu_j$. Then, $c_{\lambda\mu}^{\nu} = c_{\lambda_1\mu_j}^{\nu_K} c_{\lambda_I^c\mu_{J^c}}^{\nu_{K^c}}$, and hence $P_{\lambda\mu}^{\nu}(t) = P_{\lambda_I\mu_J}(t) P_{\lambda_I^{c}\mu_{J^c}}^{\nu_{K^c}}(t)$.

An *n-hive* is a graph of equilateral triangular shape with labeled edges as shown in Fig. 1. For partitions $\lambda, \mu$ and $\nu$ of lengths at most $n$, an *LR-hive of type* $(\lambda, \mu, \nu)$ is an $n$-hive with nonnegative integer (edge) labels and the boundary labels are determined by $\lambda, \mu, \nu$ as shown in Fig. 2, satisfying the following condition; for each rhombus in Fig. 3, $\alpha \ge \gamma$, $\beta \ge \delta$, and in each triangle the sum of two values on oblique sides is same as the value on the horizontal side.

<figure><img src="image_1.png" /><figcaption>Fig. 1: 4-hive</figcaption></figure>

<figure><img src="image_2.png" /><figcaption>Fig. 2</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 3</figcaption></figure>

**Proposition 1.4.** For partitions $\lambda, \mu$ and $\nu$, $c_{\lambda\mu}^{\nu}$ is the number of LR-hives of type $\lambda, \mu, \nu$.

A *puzzle* is an equilateral triangular diagram consisting of three elementary pieces as shown below, where all matching edges must have the same type, thick or thin:

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

Puzzles have been introduced by A. Knutson et al. (9) and they also give LR-coefficients when the boundary of puzzles are fixed by given partitions. For KTT theorem, we only need the fact that if $(I, J, K) \in R_r^n$ then there is a unique puzzle (on the shape of $n$-hive), called a *hive plan* with boundaries determined by $I, J$, and $K$: $I, J, K$ determines the northwest, northeast, south boundary respectively, and the elements of $I, J, K$ are corresponding to thick edges.

The following example explains the original idea of KTT theorem: By cutting out the shaded regions and gluing opposite edges of each rhombus, we obtain two new hive plans determined by triangles with thick or thin edges respectively. Moreover the product of numbers of hives of each hive plan gives the number of hives of the original plan.

**Example 1.5.** Let $n = 9$, $I = \{1, 2, 3, 5, 6, 8, 9\}$, $J = \{1, 2, 3, 4, 6, 8, 9\}$ and $K = \{2, 3, 4, 6, 7, 8, 9\}$. Then, $(I, J, K) \in R_7^9$ and this makes a unique puzzle (hive plan) and the number of LR-hives on the
original hive plan is the product of the numbers of LR-hives on the other two shapes where the boundary
conditions for two small LR-hives are induced from the original one:

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

An immediate observation is if $\lambda, \mu, \nu$ are partitions whose lengths are at most 2, then $c_{\lambda,\mu}^{\nu} = 1$ when it is non-zero. Hence, in Theorem 1.3, if $r \le 2$ or $r \ge n-2$, then $c_{\lambda_1\mu_J}^{\nu_K} = 1$ or $c_{\lambda_{Ic}\mu_{Jc}}^{\nu_K c} = 1$, respectively. Therefore, some special cases of Theorem 1.3 give us reduction formulae of LR-coefficients.

In the following proposition, we describe the conditions for (I, J, K) to be in $R_1^n$ or $R_2^n$, while the proof can be easily done directly from the definition of $R_r^n$. It is stated in (3) as well.

**Proposition 1.6.** Let $n$ be a positive integer. Then,

(a) $(\{i\}, \{j\}, \{k\}) \in R_1^n$ if and only if $i + j = k + 1$.

(b) $(\{i_1, i_2\}, \{j_1, j_2\}, \{k_1, k_2\}) \in R_2^n \text{ if and only if } i_1 + i_2 + j_1 + j_2 = k_1 + k_2 + 3 \text{ and } i_1 + j_1 \le k_1 + 1, i_1 + j_2 \le k_2 + 1, i_2 + j_1 \le k_2 + 1.$

Four cases $r = 1, 2, n-1, n-2$ make a complete list of what give reduction formula from KTT theorem and we state them separately in combinatorial ways.

**Theorem 1.7.** Let $\lambda, \mu$ and $\nu$ be partitions with $\ell(\lambda), \ell(\mu), \ell(\nu) \le n$ and $c_{\lambda\mu}^{\nu} > 0$.

(KTT theorem when r = 1) Suppose there are $1 \le i, j, k \le n$ such that $i + j = k + 1$ and $\nu_k = \lambda_i + \mu_j$. Then, $c_{\lambda, \mu}^{\nu} = c_{\lambda_I^c, \mu_{Jc}}^{\nu_K^c}$ and $P_{\lambda, \mu}^{\nu}(t) = P_{\lambda_I^c, \mu_{Jc}}^{\nu_K^c}(t)$ where $I = \{i_1\}, J = \{j_1\}, K = \{k_1\}$.

(KTT theorem when r = 2) Suppose there are three subsets $I = \{i_1, i_2\}$, $J = \{j_1, j_2\}$, $K = \{k_1, k_2\}$ of $[n]$, which satisfy the conditions given in Proposition 1.6 (b) and $\nu_{k_1} + \nu_{k_2} = \lambda_{i_1} + \lambda_{i_2} + \mu_{j_1} + \mu_{j_2}$. Then, $c_{\lambda, \mu}^{\nu} = c_{\lambda_I^c, \mu_{Jc}}^{\nu_K^c}$ and $P_{\lambda, \mu}^{\nu}(t) = P_{\lambda_I^c, \mu_{Jc}}^{\nu_K^c}(t)$.

Finding explicit conditions for (I, J, K) to be in $R_r^n$ is not a trivial work in general. For explicit statements of KTT theorem when $r = n-1$ and $r = n-2$, we define another class of triples of r-subsets and find the relation to the classes $R_r^n$. For $r \le n$ and an r-subset $I = \{i_1, \dots, i_r\}$, $i_1 < \dots < i_r$, of $[n]$, we define a partition $\sigma(I) = (n-r+1-i_1, n-r+2-i_2, \dots, n-i_r)$.

**Definition 1.8.** For a pair of two positive integers $r \le n$, define a set of triples of $r$-subsets of $[n]$ as follows: $C_r^n = \{(I, J, K) \mid I, J, K$ are $r$-subsets of $[n]$, $c_{\sigma(I), \sigma(J)}^{\sigma(K)} = 1\}$.
We write explicit conditions for a triple to be contained in $C_r^n$ when $r = 1, 2$. The first part of the following proposition is immediate from the definition while the second part can be obtained by applying Proposition 1.6 (b) to $\sigma(I), \sigma(J)$ and $\sigma(K)$.

**Proposition 1.9.** Let $n$ be a positive integer. Then,

(a) $(\{i\}, \{j\}, \{k\}) \in C_1^n$ if and only if $i + j = k + n$.

(b) $(\{i_1, i_2\}, \{j_1, j_2\}, \{k_1, k_2\}) \in C_2^n$ if and only if $i_1 + i_2 + j_1 + j_2 = k_1 + k_2 + 2n - 1$ and $k_2 + n \le i_2 + j_2, k_1 + n \le i_1 + j_1, k_1 + n \le i_1 + j_2$.

The following proposition enables us to understand the triples in $C_r^n$ in terms of triples in $R_{n-r}^n$.

**Proposition 1.10.** For $r$-subsets $I, J, K \subseteq [n]$, $(I, J, K) \in C_r^n$ if and only if $(I^c, J^c, K^c) \in R_{n-r}^n$.

**Proof:** It is well known that $c_{\lambda, \mu}^{\nu} = c_{\tilde{\lambda}, \tilde{\mu}}^{\tilde{\nu}}$, where $\tilde{\lambda}$ is the conjugate of $\lambda$. Hence, $(I, J, K) \in C_r^n$ if and only if $c_{\sigma(\tilde{I}), \sigma(\tilde{J})}^{\tilde{\sigma}(\tilde{K})} = 1$, and for an $r$-subset $I = \{i_1, i_2, \dots, i_r\}$, $i_1 < i_2 < \dots < i_r$, of $[n]$,

$$ \tilde{\sigma}(I) = (\underbrace{r, \dots, r}_{n-i_r}, \underbrace{r-1, \dots, r-1}_{i_r-i_{r-1}-1}, \dots, \underbrace{1, \dots, 1}_{i_2-i_1-1}, \underbrace{0, \dots, 0}_{i_1-1}). $$

Moreover, it is not hard to see that $\pi(I^c) = \tilde{\sigma}(I)$. This completes the proof. $\square$

We can state KTT theorem for $r = n-1, n-2$ cases in combinatorial ways due to Proposition 1.9 and 1.10. KTT theorem for the case $r = n-1$ gives the classical reduction formula of the first type given in (4) whose combinatorial proof using LR-tableaux is given in (1).

**Theorem 1.11.** Let $\lambda, \mu$ and $\nu$ be partitions with $\ell(\lambda), \ell(\mu), \ell(\nu) \le n$ and $c_{\lambda\mu}^{\nu} > 0$.

(KTT theorem when $r = n - 1$) Suppose there are $1 \le i, j, k \le n$ such that $i+j=k+n$ and $\lambda_i+\mu_j = \nu_k$. Then, $c_{\lambda\mu}^{\nu} = c_{\lambda_{I^c}\mu_{J^c}}^{\nu_{K^c}}, P_{\lambda,\mu}^{\nu}(t) = P_{\lambda_{I^c}, \mu_{J^c}}^{\nu_{K^c}}(t)$ where $I = \{i\}, J = \{j\}$ and $K = \{k\}$.

(KTT theorem when $r = n - 2$) Suppose there are three subsets $I = \{i_1, i_2\}$, $J = \{j_1, j_2\}$, $K = \{k_1, k_2\}$ of $[n]$ which satisfy conditions in Proposition 1.9 (b) and $\nu_{k_1} + \nu_{k_2} = \lambda_{i_1} + \lambda_{i_2} + \mu_{j_1} + \mu_{j_2}$. Then, $c_{\lambda, \mu}^{\nu} = c_{\lambda_{I^c}, \mu_{J^c}}^{\nu_{K^c}}$ and $P_{\lambda, \mu}^{\nu}(t) = P_{\lambda_{I^c}, \mu_{J^c}}^{\nu_{K^c}}(t)$.

## 2 Reduction formulae and their combinatorial proofs

In this section, we give combinatorial proofs of Theorem 1.7 and 1.11 by constructing bijections between two sets of LR-tableaux of corresponding shapes and contents. The rigorous proofs require long and complicated work, and we only give main ideas and algorithms. The proofs for $r = 1, 2, n-2$ cases are new, while the proof for the $r = n-1$ case is given in (1).

For partitions $\lambda, \mu, \nu$, we let $LR_{\lambda, \mu}^{\nu}$ be the set of LR-tableaux of shape $\nu/\lambda$ and content $\mu$. In the following subsections, for subsets $I, J, K$ satisfying conditions in Theorem 1.7 or 1.11, $\Phi: LR_{\lambda, \mu}^{\nu} \rightarrow LR_{\lambda_{I^c}, \mu_{J^c}}^{\nu_{K^c}}$ is a bijection defined for the combinatorial proofs and $T$ is an LR-tableau of corresponding shape $\nu/\lambda$ and content $\mu$. For a skew tableau $T$ with $n$ rows and integers $1 \le h, \ell \le n$, we let $n_T^h(\ell)$ be the number of $\ell$'s in the $h$th row of $T$.
## 2.1 r = n − 1: The first classical reduction formula

Throughout this section, we assume that $i+j=k+n$, $\lambda_i+\mu_j=\nu_k$. Detailed proof of this case appeared in (1). The main lemma that allows Definition 2.2 valid is the following:

**Lemma 2.1.** For each $k \le l \le j$, $\sum_{h=l}^{l+n-j} n_T^h(l) = \mu_j$.

**Definition 2.2.** The reduced LR-tableau $\Phi(T)$ is obtained by applying the following algorithm:

**Step 1:** Empty all $\mu_j$ boxes containing $k$ in $(n-j+1)$ consecutive rows from the $k$th row to the $i$th row.

**Step 2:** **for** $l = k + 1$ **to** $j$ **do**
Replace all $\mu_j$ $l$'s in $(n-j+1)$ consecutive rows from the $l$th row with $(l-1)$'s.
**end for**

**Step 3:** **for** $l = j + 1$ **to** $n$ **do**
Replace $l$'s with $(l-1)$'s.
**end for**

**Step 4:** Slide the empty boxes down to the $i$th row or to the end of the column whichever occurs first.

**Step 5:** Remove the empty boxes which are in the $i$th row or at the end of columns.

**Example 2.3.** We let $\lambda = (5, 4, 4, 3, 3, 2, 1, 0)$, $\mu = (5, 5, 5, 4, 4, 1, 0, 0)$ and $\nu = (8, 8, 6, 6, 5, 5, 4, 4)$.
We have $n = 8$ and $i = 6$, $j = 5$, $k = 3$, then $\lambda_6 + \mu_5 = \nu_3$.

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

## 2.2 r = n − 2

Throughout this section, we assume $i_1 + i_2 + j_1 + j_2 = k_1 + k_2 + 2n - 1$, $k_2 + n \le i_2 + j_2$, $k_1 + n \le i_2 + j_1$, $k_1 + n \le i_1 + j_2$ and $\lambda_{i_1} + \lambda_{i_2} + \mu_{j_1} + \mu_{j_2} = \nu_{k_1} + \nu_{k_2}$. Let $a = i_1 - k_1$, $b = i_2 - k_2$, $\alpha = n - 1 - j_1$, and $\beta = n - j_2$. The main lemma that allows Definition 2.7 valid is the following:

**Lemma 2.4.** For $k_2 \le l \le j_2$, $\sum_{h=l}^{l+\beta} n_T^h(l) = \mu_{j_2}$. For $k_2 + b - \alpha - 1 \le l \le j_1$, $\sum_{h=l}^{l+\alpha+1} n_T^h(l) = \mu_{j_1}$.
For $k_1 \le l \le k_2 + b - \alpha - 1$, $\sum_{h=l}^{l+\alpha} n_T^h(l) = \nu_{k_1} - \lambda_{i_1}$.

**Definition 2.5.** Let $S(T)$ be the set of boxes satisfying one of the following conditions:

(S1) Boxes which contain $k_1$ and are in $(a+1)$ consecutive rows from the $k_1$th row to the $i_1$th row.

(S2) Boxes which contain $(k_2+b-\alpha-1)$ and are in $(b-\beta+1)$ consecutive rows from the $(k_2+\beta)$th row to the $i_2$th row.

(S3) Boxes which contain $k_2$ and are in $(\beta+1)$ consecutive rows from the $k_2$th row to the $(k_2+\beta)$th row.
**Definition 2.6.** Define $h_T$ to be a filling of $\nu/\lambda - S(T)$ with integers $0, -1, -2$ so that $h_T(p, q)$ is empty if $(p, q)$-box of $T$ is in $S(T)$. In other cases,

$$h_T(p, q) = \begin{cases} -1 & \text{if } k_1 + 1 \le T(p, q) \le k_2 + b - \alpha - 1 \text{ and } p \le T(p, q) + a, \\ -1 & \text{if } k_2 + b - \alpha \le T(p, q) \le k_2 - 1 \text{ and } p \le T(p, q) + \alpha + 1, \\ -2 & \text{if } k_2 + 1 \le T(p, q) \le j_1 + 1 \text{ and } p \le T(p, q) + \beta, \\ -1 & \text{if } k_2 \le T(p, q) \le j_1 \text{ and } T(p, q) + \beta < p \le T(p, q) + \alpha + 1, \\ -1 & \text{if } \max\{j_1 + 2, k_2 + 1\} \le T(p, q) \le j_2 \text{ and } p \le T(p, q) + \beta, \\ 0 & \text{otherwise.} \end{cases}$$

**Definition 2.7.** The reduced LR-tableau $\Phi(T)$ is obtained by applying the following algorithm:

**Step 1:** Empty all boxes in $S(T)$.

**Step 2:** Add $h_T(p, q)$ to the $(p, q)$-box which is not empty.

**Step 3:** **for** $\ell = (j_1 + 1)$ **to** $(j_2 - 1)$ **do**
Replace all $\ell$'s with $(\ell - 1)$'s.
**end for**

**Step 4:** **for** $\ell = (j_2 + 1)$ **to** $n$ **do**
Replace all $\ell$'s with $(\ell - 2)$'s.
**end for**

**Step 5:** Slide empty boxes of (S2) or (S3) in Definition 2.5 down to the $i_2$th row or to the end of the column whichever occurs first. Also slide empty boxes of (S1) down to the $i_1$th row or to the end of the column whichever occurs first.

**Step 6:** Remove all the empty boxes which are in the $i_1$th row, $i_2$th rows and at the end of columns.

**Example 2.8.** Let $n = 14$. We are given partitions $\lambda = (12, 12, 11, 10, 10, 10, 9, 9, 7, 5, 4, 3, 1, 0)$, $\mu = (9, 8, 7, 6, 6, 5, 5, 5, 5, 3, 3, 1, 1, 1)$ and $\nu = (15, 14, 14, 13, 13, 13, 13, 13, 13, 11, 11, 10, 10, 9, 9)$. We have $i_1 = 6, i_2 = 8, k_1 = 2, k_2 = 5, j_1 = 9, j_2 = 11$ so that $\lambda_6 + \lambda_8 + \mu_9 + \mu_{11} = 27 = \nu_2 + \nu_5$.

<figure><img src="image_7.png" /></figure>
## 2.3 r = 1

Throughout this section, we assume that $i + j = k + 1$, $\lambda_i + \mu_j = \nu_k$. The following is a key lemma that allows Definition 2.10 is valid.

**Lemma 2.9.** For $j + 1 \le l \le k$, $\sum_{h=\ell}^{k} n_T^h(l) = \sum_{h=\ell-1}^{k-1} n_T^h(l-1)$. Also $\sum_{h=j}^{k} n_T^k(h) = \mu_j$.

**Definition 2.10.** The reduced LR-tableau $\Phi(T)$ is obtained by applying the following algorithm:

**Step 1:** **for** $\ell = k$ **downto** $j + 1$ **do**
Empty all boxes containing $\ell$ in $k$th row.
Replace all $(\ell - 1)$'s in $(k - \ell + 1)$ consecutive rows from the $(\ell - 1)$st row to the $(k - 1)$st row with $\ell$'s.
**end for**

**Step 2:** Empty all boxes containing $j$ in the $k$th row.

**Step 3:** **for** $\ell = j + 1$ **to** $n$ **do**
Replace all $\ell$'s with $(\ell - 1)$'s.
**end for**

**Step 4:** Slide each box at $(p, q)$-position, $1 \le p \le k - 1$, $\lambda_i + 1 \le q$, one step down to remove all empty boxes.

**Example 2.11.** Let $n = 6$ and $\lambda = (5, 5, 3, 2, 2, 0)$, $\mu = (8, 7, 5, 5, 4, 1)$, $\nu = (11, 9, 8, 8, 8, 3)$. We have $i = 3, j = 3, k = 5$, and $\lambda_3 + \mu_3 = \nu_5 = 8$.

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

## 2.4 r = 2

Throughout this section, we assume that $i_1 + i_2 + j_1 + j_2 = k_1 + k_2 + 3$, $i_1 + j_1 \le k_1 + 1$, $i_1 + j_2 \le k_2 + 1$, $i_2 + j_1 \le k_2 + 1$, $\lambda_{i_1} + \lambda_{i_2} + \mu_{j_1} + \mu_{j_2} = \nu_{k_1} + \nu_{k_2}$. The following is a key lemma that allows Definition 2.13 valid.

**Lemma 2.12.** (a) For $\ell = j_1 + 1, \dots, k_1$, $\sum_{h=\ell}^{k_1} n_T^h(l) = \sum_{h=\ell-1}^{k_1-1} n_T^h(l-1)$.

(b) For $\ell = j_1 + 1, \dots, j_2 - 1$, $\sum_{h=k_2-j_2+1+\ell}^{k_2} n_T^h(l) = \sum_{h=k_2-j_2+\ell}^{k_2-1} n_T^h(l-1)$.

(c) For $\ell = j_2 + 1, \dots, k_2$, $\sum_{h=\ell}^{k_2} n_T^h(l) = \sum_{h=\ell-1}^{k_2-1} n_T^h(l-1)$.

(d) $\sum_{h=j_1}^{k_1} n_T^{k_1}(h) = \nu_{k_1} - \lambda_{i_1}$ and $\sum_{h=j_1}^{k_2} n_T^{k_2}(h) = \nu_{k_2} - \lambda_{i_2}$.
$$
(e) \sum_{h=j_1}^{k_1} n_T^h(j_1) + \sum_{h=k_2-j_2+j_1+1}^{k_2} n_T^h(j_1) = \mu_{j_1} \quad \text{and} \quad \sum_{h=j_2}^{k_2} n_T^h(j_2) = \mu_{j_2}.
$$

**Definition 2.13.** The reduced LR-tableau $\Phi(T)$ is obtained by applying the following algorithm:

Step 1: **for** $\ell = k_1$ **downto** $j_1 + 1$ **do**

Empty all boxes containing $\ell$ in $k_1$th row.

Replace all $(\ell-1)$'s in $(k_1-\ell+1)$ consecutive rows from the $(\ell-1)$st row to the $(k_1-1)$st row with $\ell$'s.

end for

Step 2: Empty all boxes containing $j_1$ in $k_1$th row.

Step 3: **for** $\ell = j_2 - 1$ **downto** $j_1 + 1$ **do**

Empty all boxes containing $\ell$ in $k_2$th row.

Replace all $(\ell - 1)$'s in $(j_2 - \ell)$ consecutive rows from the $(k_2 - j_2 + \ell)$th row to the $(k_2 - 1)$st row with $\ell$'s.

end for

Step 4: Empty all boxes containing $j_1$ in $k_2$th row.

Step 5: **for** $\ell = k_2$ **downto** $j_2 + 1$ **do**

Empty all boxes containing $\ell$ in $k_2$th row.

Replace all $(\ell-1)$'s in $(k_2-\ell+1)$ consecutive rows from the $(\ell-1)$st row to the $(k_2-1)$st row with $\ell-1$'s.

end for

Step 6: Empty all boxes containing $j_2$ in $k_2$th row.

Step 7: **for** $\ell = j_1 + 1$ **to** $j_2$ **do**

Replace all $\ell$'s with $(\ell - 1)$'s.

end for

Step 8: **for** $\ell = j_2 + 1$ **to** $n$ **do**

Replace all $\ell$'s with $(\ell - 2)$'s.

end for

Step 9: Slide each box at $(p, q)$-position for $1 \le p \le k_1 - 1$, $\lambda_{i_1} + 1 \le q$ or for $k_1 + 1 \le p \le k_2 - 1$, $\lambda_{i_2} + 1 \le q$ down to remove all empty boxes.

**Example 2.14.** Let $n = 10$. Consider $\lambda = (8, 7, 6, 5, 4, 2, 2, 2, 1, 0)$, $\mu = (11, 6, 6, 5, 3, 3, 3, 3, 2)$ and $\nu = (13, 11, 10, 10, 10, 6, 6, 6, 4)$. We have $i_1 = 4$, $i_2 = 6$, $j_1 = 2$, $j_2 = 5$, $k_1 = 5$, $k_2 = 9$ and $\lambda_4 + \lambda_6 + \mu_2 + \mu_5 = \nu_5 + \nu_9 = 16$.

<figure><img src="image_9.png" /></figure>
<figure><img src="image_10.png" /></figure>

### 3 Another reduction formula

The classical reduction formula of the second type, that can be understood as the conjugate (of LR-tableaux) version of the first type (i.e., $r = n - 1$ case of KTT theorem) is not a special case of KTT theorem in a direct way. We give combinatorial proofs of this formula in terms of tableaux and hives.

For a partition $\lambda$ of length $n$ and an integer $i \le n$, we let $\lambda \ominus i = (\lambda_1 - 1, \dots, \lambda_i - 1, \lambda_{i+1}, \dots, \lambda_n)$.

**Theorem 3.1 (The second classical reduction formula (4)).** Let $\lambda, \mu$ and $\nu$ be partitions with $|\nu| = |\lambda| + |\mu|$ and $\ell(\lambda), \ell(\mu), \ell(\nu) \le n$. Suppose that there are indices $i, j, k$ such that $i + j + k = n$ and $\lambda_i + \mu_j \ge \nu_1 + \nu_{n-k+1} + 1$. We also assume that $\lambda_{i+1} < \lambda_i, \mu_{j+1} < \mu_j$ and $\nu_{n-k+1} < \nu_{n-k}$. Then $c_{\lambda, \mu}^{\nu} = c_{\lambda \ominus i, \mu \ominus j}^{\nu \ominus (n-k)}$.

Throughout this section we assume that $n, i, j, k$ and $\lambda, \mu, \nu$ satisfy the given conditions in Theorem 3.1, and $T$ is an LR-tableau of shape $\nu/\lambda$ and content $\mu$. Definition 3.3 gives a bijection $\Phi : LR_{\lambda, \mu}^{\nu} \to LR_{\lambda \ominus i, \mu \ominus j}^{\nu \ominus (n-k)}$ and the following is an essential lemma for the well-definedness of $\Phi$.

**Lemma 3.2.** For each $\ell = 1, 2, \dots, j$, there is an $h$ with $\nu_{n-k+1} + 1 \le h \le \lambda_i$ such that $\ell = T(i+\ell, h)$.

Note that $h$ in the above lemma is not unique. However, $\Phi(T)$ is well-defined in the following definition.

**Definition 3.3.** $\Phi(T)$ is obtained by applying the following algorithm:

**Step 1:** **for** $\ell = 1$ **to** $j$ **do**
Empty a box in the $(i+\ell)$th row and between the $(\nu_{n-k+1} + 1)$st column and the $\lambda_i$th column of $T$ which is containing an $\ell$.
**end for**

**Step 2:** Slide the empty boxes right to reach the end of the row.

**Step 3:** **for** $\ell = 1$ **to** $i$ **do**
Move every box in the $\ell$th row to one box left.
**end for**

**Step 4:** Remove the empty boxes.
by applying $r = n - 1$ (or $r = 1$) case twice (respectively). Key lemmas (Lemma 2.1, 2.4, 2.9, 2.12, 3.2 and 3.5) explain their own characteristics well.

We believe that there must be a general (reduction) theorem which explains all reduction formulae we covered in this paper as special cases. We, therefore, think that conjugate version of KTT theorem when $r = 1, 2, n - 2$ can also be obtained in a natural way.

Reduction formulae for structure constants of various cohomology (equivariant cohomology, K-theory, quantum cohomology) on various types of Schubert variety must be an interesting subject to consider. Combinatorial proofs of those formulae in terms of many recently known combinatorial objects and recurrence relations for structure constants are among our interests, also.

## Acknowledgements

The authors would like to thank R.C. King for letting us read the proof of the factorization theorem (7), and Young-Tak Oh for introducing (6) when it was in preprint form.

## References

[1] Soojin Cho, Eun-Kyoung Jung, and Dongho Moon, *A combinatorial proof of the reduction formula for Littlewood-Richardson coefficients*, J. Combin. Theory Ser. A **114** (2007), no. 7, 1199–1219.

[2] Harm Derksen and Jerzy Weyman, *On the Littlewood-Richardson polynomials*, J. Algebra **255** (2002), no. 2, 247–257.

[3] William Fulton, *Eigenvalues, invariant factors, highest weights, and Schubert calculus*, Bull. Amer. Math. Soc. (N.S.) **37** (2000), no. 3, 209–249 (electronic).

[4] Phillip Griffiths and Joseph Harris, *Principles of algebraic geometry*, Wiley-Interscience [John Wiley & Sons], New York, 1978.

[5] R. C. King, C. Tollu, and F. Toumazet, *Stretched Littlewood-Richardson and Kostka coefficients*, Symmetry in physics, CRM Proc. Lecture Notes, vol. 34, Amer. Math. Soc., Providence, RI, 2004, pp. 99–112.

[6] __________, *The hive model and the polynomial nature of stretched Littlewood-Richardson coefficients*, Séminaire Lotharingien de Combinatoire **54A** (2006), 1–19.

[7] __________, *Factorization of Littlewood-Richardson coefficients*, preprint, 2007.

[8] Allen Knutson and Terence Tao, *The honeycomb model of $GL_n(C)$ tensor products. I. Proof of the saturation conjecture*, J. Amer. Math. Soc. **12** (1999), no. 4, 1055–1090.

[9] Allen Knutson, Terence Tao, and Christopher Woodward, *The honeycomb model of $GL_n(C)$ tensor products. II. Puzzles determine facets of the Littlewood-Richardson cone*, J. Amer. Math. Soc. **17** (2004), no. 1, 19–48 (electronic).

[10] Etienne Rassart, *A polynomiality property for Littlewood-Richardson coefficients*, J. Combin. Theory Ser. A **107** (2004), no. 2, 161–179.