Séminaire Lotharingien de Combinatoire 54 (2006), Article B54j

COMBINATORIAL OPERATORS FOR KRONECKER POWERS OF REPRESENTATIONS OF 𝔖_{n}

ALAIN GOUPIL^{1} AND CEDRIC CHAUVE^{2}

Dans ce monde il n’existe que deux tragédies : ne pas obtenir ce que l’on veut et obtenir ce que l’on veut. La dernière est un vrai drame.

Oscar Wilde

En mathématiques, quand on obtient ce qu’on veut, on en fait un coquillage pour tenter de conserver un moule de la pensée éphémère qui l’a engendré. Nous dédions cet article à Xavier-Gérard Viennot et à ses coquillages pleins de reliefs.

Abstract. We present combinatorial operators for the expansion of the Kronecker product of irreducible representations of the symmetric group 𝔖_{n}. These combinatorial operators are defined in the ring of symmetric functions and act on the Schur functions basis. This leads to a combinatorial description of the Kronecker powers of the irreducible representations indexed with the partition (n − 1, 1) which specializes the concept of oscillating tableaux in Young’s lattice previously defined by S. Sundaram. We call our specialization Kronecker tableaux. Their combinatorial analysis leads to enumerative results for the multiplicity of irreducible representations in the Kronecker powers of the forms χ^{(n−1,1)}^{⊗k} and P^{⊗k} where P is the permutation representation of 𝔖_{n}.

1. Introduction

The subject of the present work is the investigation of the Kronecker product, sometimes called inner tensor product, of irreducible representations of the symmetric group 𝔖_{n}. Given two linear representations

\begin{matrix}A : 𝔖_{n} → Aut(V) \\ σ ↦ A(σ) \end{matrix} \begin{matrix}B : 𝔖_{n} → Aut(W) \\ σ ↦ B(σ) \end{matrix}

which associate linear operators to permutations σ ∈ 𝔖_{n}, the Kronecker product of A and B, denoted A ⊗ B, is the representation of 𝔖_{n} defined by

\begin{matrix}A ⊗ B : 𝔖_{n} → Aut(V ⊗ W) \\ σ ↦ A(σ) ⊗ B(σ) \end{matrix}

which is the action on the tensor product V ⊗ W of vector spaces V and W by means of the tensor product A(σ) ⊗ B(σ) of the linear operators A(σ) and B(σ).

1Work partially supported by a grant from NSERC. 2Work partially supported by a grant from UQÀM.

The irreducible representations of 𝔖_{n} are the representations which are indecomposable as direct sums of representations. They are indexed with the partitions λ of n:

\begin{matrix}A^{λ} : 𝔖_{n} → Aut(V) \\ σ ↦ A^{λ}(σ). \end{matrix}

The Kronecker product A^{λ} ⊗ A^{μ} of two irreducible representations of 𝔖_{n} is in general not an irreducible representation of 𝔖_{n} and the fundamental problem of expanding it as a direct sum of irreducible representations

A^{λ} ⊗ A^{μ} = ∑_{α⊢n} t_{λ,μ}^{α}A^{α}

goes back to the foundation of the representation theory. This problem was studied by Murnaghan [10, 11], Littlewood [8] and more recently by Lascoux [7], Garsia and Remmel [6], Thibon et al. [14, 15] and others (see [1] and references therein).

To obtain the decomposition coefficients t_{λ,μ}^{α}, one can use the characters of the corresponding representations. The character of a representation A of 𝔖_{n} is the map χ^{A} which sends permutations σ ∈ 𝔖_{n} to the traces of A(σ):

\begin{matrix}χ^{A} : 𝔖_{n} → ℂ \\ σ ↦ tr(A(σ)). \end{matrix}

The fact that the character of the Kronecker product A ⊗ B of two representations is obtained by multiplying the traces of the linear operators A(σ) and B(σ):

\begin{matrix}χ^{A⊗B} : 𝔖_{n} → ℂ \\ σ ↦ tr(A(σ)) tr(B(σ)) \end{matrix} (1)

is a straightforward consequence of the definition of tensor product of linear operators. Hence one can use property (1) of characters and the character table, indexed by integer partitions of n (see Table 1 for example) to compute the characters of a Kronecker product of two irreducible representations.

Let us recall that character values χ^{A}(σ_{1}), χ^{A}(σ_{2}) on two permutations σ_{1}, σ_{2} in the same conjugacy class C_{μ} are always equal. Therefore we use the notation χ_{μ}^{λ} for the value of the irreducible character χ^{λ} on any element of the conjugacy class C_{μ}.

Example 1. Let Table 1 be the table of the irreducible characters of 𝔖_{4}.

\begin{matrix}λ\μ & (4) & (3, 1) & (2, 2) & (2, 1^{2}) & (1^{4}) \\ (4) & 1 & 1 & 1 & 1 & 1 \\ (3, 1) & −1 & 0 & −1 & 1 & 3 \\ (2, 2) & 0 & −1 & 2 & 0 & 2 \\ (2, 1^{2}) & 1 & 0 & −1 & −1 & 3 \\ (1^{4}) & −1 & 1 & 1 & −1 & 1 \end{matrix}

Table 1. Irreducible characters χ_{μ}^{λ} of S_{4}.

The character of the Kronecker product A^{(3,1)} ⊗ A^{(3,1)} of the irreducible representation A^{(3,1)} with itself is obtained by multiplying each element of the row-vector (−1, 0, −1, 1, 3) in Table 1 with itself and we obtain

χ^{(3,1)⊗(3,1)} = (1, 0, 1, 1, 9)

Since Table 1 contains the row-vectors of all possible irreducible characters and that (1, 0, 1, 1, 9) is obviously not one of these rows, it is immediate that the character represented by (1, 0, 1, 1, 9) is not irreducible. But we observe that the identity χ^{(3,1)⊗(3,1)} = χ^{(4)} + χ^{(3,1)} + χ^{(2,1,1)} + χ^{(2,2)} is true by adding the rows of Table 1 corresponding to the partitions in the right hand side. ⋄

More generally, the problem of computing the coefficients t_{λ,μ}^{α} has a solution when one accepts to use the character table [χ_{μ}^{λ}] of 𝔖_{n}:

t_{λ,μ}^{α} = χ^{λ} ⊗ χ^{μ}|_{χ^{α}} = ∑_{γ⊢n} \frac{|C_{γ}|}{n!}χ_{γ}^{λ}χ_{γ}^{μ}χ_{γ}^{α}. (2)

Identity (2) follows from the orthonormality of the characters χ^{λ} with respect to the standard scalar product in the group algebra of 𝔖_{n} and from (1). But since the coefficients t_{λ,μ}^{α} are positive integers, we find equation (2) unsatisfactory and the goal of this paper is to contribute to other avenues for computing the coefficients t_{λ,μ}^{α}.

Our contribution is to expand kth tensor powers χ^{(n−1,1)}^{⊗k} for arbitrary positive integers k. Our main tools are operators on the ring of symmetric functions which reproduce tensor products of irreducible representations when they act on Schur functions. Then we develop a combinatorial model to represent the tensor powers χ^{(n−1,1)}^{⊗k}. One outcome of this combinatorial model is the following exponential generating function for the multiciplity of χ^{λ} in χ^{(n−1,1)}^{⊗k}:

(3)  ∑_{k≥|\overline{λ}|} χ^{(n_{k}−1,1)}^{⊗k}|_{χ^{λ^{k}}} \frac{x^{k}}{k!} = \frac{f\overline{λ}}{|\overline{λ}|!}e^{e^{x}−x−1}(e^{x} − 1)^{|\overline{λ}|},

where, \overline{λ} = (λ_{2}, λ_{3}, …) is an integer partition of weight |\overline{λ}|, and for every k ≥ |\overline{λ}|, n_{k} ≥ k + λ_{2} and λ^{k} is the integer partition obtained by adding the part n_{k} − |\overline{λ}| to \overline{λ}. Now the permutation representation P derived from the action of 𝔖_{n} on the set {1, 2, …, n} satisfies χ^{P} = χ^{(n−1,1)} + χ^{(n)} where χ^{(n)} is the character of the identity representation. So we also obtain a nice generating function for the multiciplity in (χ^{P})^{⊗k}

(4)  ∑_{k≥|\overline{λ}|} (χ^{P})^{⊗k}|_{χ^{λ^{k}}} \frac{x^{k}}{k!} = \frac{f\overline{λ}}{|\overline{λ}|!}e^{e^{x}−1}(e^{x} − 1)^{|\overline{λ}|}.

2. Combinatorial operators

2.1. Symmetric functions. Let ℚ[𝔖_{n}] be the group algebra of the symmetric group over the field ℚ of rational numbers and let Z_{n} be the center of this group algebra. The irreducible characters of S_{n} can be seen as elements of Z_{n} when one writes

χ^{λ} = ∑_{σ∈𝔖_{n}} χ^{λ}(σ)σ,

and the pointwise multiplication of two elements a = ∑_{σ∈𝔖_{n}} a_{σ}σ and b = ∑_{σ∈𝔖_{n}} b_{σ}σ of ℚ[𝔖_{n}] is defined by

a · b = ∑_{σ∈𝔖_{n}}(a_{σ}b_{σ})σ.

In Example 1 we have seen that pointwise multiplication of characters gives the character of Kronecker product of the corresponding representations: χ^{λ} · χ^{μ} = χ^{λ⊗μ}.

Let x = {x_{1}, x_{2}, …} be a set of indeterminates, Λ = Λ_{ℚ}[x] the ring of symmetric functions in x_{1}, x_{2}, … over the field ℚ and Λ^{n} the restriction to homogeneous symmetric functions of degree n. Two important sets of symmetric functions are the homogeneous symmetric functions and the Schur symmetric functions. Given a partition λ = (λ_{1}, …, λ_{m}), one defines h_{λ}(x) = ∏_{i=1}^{m} h_{λ_{i}}(x), where h_{r}(x) is the rth homogeneous symmetric function, and one denotes by s_{λ}(x) the Schur symmetric function associated to λ (see [9]). The sets {h_{λ}(x)}_{λ⊢n} and {s_{λ}(x)}_{λ⊢n} are linear basis of Λ^{n}. The Frobenius map F : Z_{n} → Λ^{n} is a vector space isomorphism which sends the irreducible characters χ^{λ} to the Schur functions s_{λ} : F(χ^{λ}) = s_{λ}. Schur functions can be expanded as determinants of homogeneous functions:

(5)  s_{λ} = det(h_{λ_{i}−i+j})_{1≤i,j≤n} ,

where h_{0} = 1 and h_{r} = 0 if r < 0. The Littlewood–Richardson coefficients (denoted by LR) are defined as the coefficients in the expansion of the ordinary product of two or more Schur functions in the basis of Schur functions:

s_{ν^{(1)}}s_{ν^{(2)}} ⋯ s_{ν^{(r)}} = ∑_{μ} LR_{ν^{(1)},ν^{(2)},...,ν^{(r)}}^{μ}s_{μ}.

The adjoint operator to multiplication by s_{γ} in Λ with respect to the standard scalar product in Λ is denoted s_{γ}^{⊥} and its action on the Schur function s_{λ} is as follows:

(6)  s_{γ}^{⊥}s_{λ} = s_{λ/γ} = \begin{cases}∑_{α} LR_{γ,α}^{λ}s_{α} & if γ ⊆ λ, \\ 0 & otherwise, \end{cases}
(7)  ⟨s_{γ}f, g⟩ = ⟨f, s_{γ}^{⊥}g⟩ for all f, g ∈ Λ.

Now let us define in Λ^{n} the operation f ⊙g corresponding to pointwise multiplication in ℚ[𝔖_{n}] by means of the Frobenius map:

f ⊙ g = F(F^{−1}(f) · F^{−1}(g)) for all f, g, ∈ Λ^{n}.

We shall call this operation inner product of symmetric functions, and we have in particular

(8)  s_{λ} ⊙ s_{μ} = ∑_{α} t_{λ,μ}^{α}s_{α},

where the coefficients t_{λ,μ}^{α} are the same than in equation (2). We can expand the inner product h_{λ} ⊙ s_{μ} in the basis {s_{α}} as follows (see also [9, 1.7, Example 23 (d)]):

(9)  h_{λ} ⊙ s_{μ}(x) = ∑_{{ν^{(1)}⊢λ_{1},ν^{(2)}⊢λ_{2},...,ν^{(k)}⊢λ_{k}}} LR_{ν^{(1)}ν^{(2)}···ν^{(k)}}^{μ}s_{ν^{(1)}} ⋯ s_{ν^{(k)}}

= ∑_{{ν^{(2)}⊢λ_{2},...,ν^{(k)}⊢λ_{k}}}(s_{ν^{(2)}} ⋯ s_{ν^{(k)}})(s_{ν^{(2)}}^{⊥} ⋯ s_{ν^{(k)}}^{⊥})s_{μ}. (10)

To prove identity (9) in the language of λ-rings, it suffices to notice that (h_{λ} ⊙ s_{μ})[X] = h_{λ}[XY]|_{s_{μ}[Y]}. Then (9) follows from the fact that

h_{λ}[XY] = ∑_{μ} ( ∑_{{ν^{(1)}⊢λ_{1},...,ν^{(k)}⊢λ_{k}}} LR_{ν^{(1)}···ν^{(k)}}^{μ}s_{ν^{(1)}}[X] ⋯ s_{ν^{(k)}}[X]) s_{μ}[Y].

Identity (10) follows from (9) and (6).

2.2. The operators U\overline{λ}.

Definition 1. Let λ = (λ_{1}, …, λ_{m}) ⊢ n be a partition of n, with λ_{1} ≥ λ_{2} ≥ … ≥ λ_{m}, and \overline{λ} the truncated partition of λ defined by \overline{λ} = (λ_{2}, …, λ_{m}). One denotes by U\overline{λ} the operator from Λ^{n} to Λ^{n} defined as follows:

a): Expand the determinant

(11)  | \begin{matrix}1 & 1 & … & 1 \\ h_{λ_{2}−1} & h_{λ_{2}} & … & h_{λ_{2}+r−2} \\ ⋮ & ⋮ & … & ⋮ \\ h_{λ_{r}−r+1} & h_{_{r}−r+2} … & … & h_{λ_{r}} \end{matrix} |

b): Replace each term h_{α} = h_{α_{1}}h_{α_{2}} ⋯ h_{α_{m}} in the expansion of (11) by

∑_{ν^{(1)}⊢α_{1},...,ν^{(m)}⊢α_{m}}(s_{ν^{(1)}} · s_{ν^{(m)}})(s_{ν^{(1)}}^{⊥} ⋯ s_{ν^{(m)}}^{⊥})

to obtain the operator U\overline{λ}.

Theorem 1. For any partitions λ and μ of n, we have

U\overline{λ}s_{μ} = s_{λ} ⊙ s_{μ}

= ∑_{α⊢n} t_{λ,μ}^{α}s_{α}.

Proof. This is a straightforward consequence of equations (5), (8) and (10). □

Example 2. The Kronecker product χ^{(n−1,1)} ⊗ χ^{μ} is obtained by applying the operator U_{(1)} on s_{μ} which is obtained by expanding the determinant in Definition 1 a) and then writing the h_{λ} in terms of Schur functions using Definition 1 b):

| \begin{matrix}1 & 1 \\ h_{0} & h_{1} \end{matrix} | = h_{1} − 1 ⇒ U_{(1)} = s_{(1)}s_{(1)}^{⊥} − 1

Similarly the operator U_{(2)} needed for the computation of χ^{(n−2,2)} ⊗ χ^{μ} is obtained with the determinant

| \begin{matrix}1 & 1 \\ h_{1} & h_{2} \end{matrix} | = h_{2} − h_{1} ⇒ U_{(2)} = s_{(2)}s_{(2)}^{⊥} + s_{(1,1)}s_{(1,1)}^{⊥} − s_{(1)}s_{(1)}^{⊥}

⋄

Remark 1. The fact that the computation of χ^{λ} ⊗ χ^{μ} is independent of the largest part of λ was already observed by Murnaghan [11] and also described by Thibon [15], but the definition of the operators U\overline{λ} seems to be new.

3. A combinatorial model for χ^{(n−1,1)⊗k} and some consequences

We are now ready to present a combinatorial model for the multiplicity of irreducible representations in any Kronecker power χ^{(n−1,1)⊗k}, in terms of paths in Young’s lattice. From Example 2, it is immediate that the expansion of the Kronecker power χ^{(n−1,1)⊗k} is obtained by the application of the operator U_{(1)}^{k} = (s_{(1)}s_{(1)}^{⊥} − 1)^{k} on the Schur function s_{(n)}. In the remaining of this section we develop a combinatorial interpretation of this process, followed by some enumerative consequences.

When λ = (λ_{1}, …, λ_{m}) is an integer partition of n, we call n the weight of λ and we write |λ| = n. We recall that the unique Ferrers diagram associated to λ is formed of m stacked rows of cells, ordered from bottom to top in increasing order and such that the i^{th} row contains λ_{i} cells. A cell of a diagram λ located at the right end of a row and having no cell above it is called a corner of λ. For example, in the following Ferrers diagram, corresponding to the partition (4, 4, 2, 1), the corners are indicated by •.

• ; • ; •

The unique corner of a Ferrers diagram located on a longest row is called the first corner of the diagram.

It follows immediately from the definition of the operator s_{(1)}^{⊥} that, for a Ferrers diagram λ, s_{(1)}^{⊥}(s_{λ}) is the sum of the Schur functions indexed by the Ferrers diagrams obtained by removing a single corner from λ. Symmetrically, s_{(1)}(s_{λ}) is the sum of the Schur functions indexed by the Ferrers diagrams obtained by adding to λ a new cell that becomes a corner of the new diagram. Hence s_{(1)}s_{(1)}^{⊥}(s_{λ}) is the sum of the Schur functions indexed with the Ferrers diagrams that are obtained from λ by first removing a corner from λ, which gives a diagram denoted λ′, then adding a corner to λ′. One says that every diagram, or equivalently partition, λ′ ≠ λ indexing a Schur function occurring in the sum s_{(1)}s_{(1)}^{⊥}(s_{λ}) differs from λ by the position of a corner. It should be noticed that the multiplicity of s_{λ} in the sum s_{(1)}s_{(1)}^{⊥}(s_{λ}) is at least 1. Hence, as U_{(1)} = s_{(1)}s_{(1)}^{⊥} − 1, one can define U_{(1)} as s_{(1)}s_{(1)}^{⊥}(s_{λ}) minus one occurrence of s_{λ}.

Example 3. U_{(1)}(s_{(3,3,1)}) = s_{(3,3,1)} + s_{(4,2,1)} + s_{(3,2,1,1)} + s_{(3,2,2)} + s_{(4,3)}, and the partitions (4, 2, 1), (3, 2, 1, 1), (3, 2, 2) and (4, 3) differ from (3, 3, 1) by the position of a corner. The multiplicity of s_{(3,3,1)} is 1 because there are two corners in (3, 3, 1), and thus only two ways to obtain (3, 3, 1) from itself by removing then replacing a corner, one of these occurrences being not taken into account due to the −1 term in the definition of U_{(1)}. ⋄

We now define the main combinatorial object that we will need in order to encode the action of U_{(1)}, iterated k times, on a Schur function s_{μ}.

Definition 2. Given a positive integer k and partitions λ and μ of same weight, a Kronecker tableau K of length k, initial shape μ and final shape λ is a sequence ν^{0} = μ, ν^{1}, …, ν^{k} = λ of Ferrers diagrams where, for every pair of consecutive diagrams ν^{i} and ν^{i+1}, either ν^{i+1} differs from ν^{i} by the position of a corner, or ν^{i+1} = ν^{i} and one corner of ν^{i+1}, other than its first corner, is distinguished. One denotes by KT_{μ,λ}^{k} the set of Kronecker tableaux of length k, initial shape μ and final shape λ.

Example 4. The following Kronecker tableau — where a distinguished corner is indicated by a × — belongs to KT_{(5),(3,2)}^{9}

×  ×

Proposition 1. Let k and n be two positive integers and λ a partition of n. Then

(12)  χ^{(n−1,1)}^{⊗k}|_{χ^{λ}} = |KT_{(n),λ}^{k}|.

Proof. The definition of U_{(1)} as an operator on Schur functions can be translated in the combinatorial framework of partitions and Ferrers diagrams, due to the fact that Schur functions are indexed by partitions. Hence, the sum of Schur functions U_{(1)}^{k}(s_{n}) can be seen as a formal sum of Ferrers diagrams. The number of occurrences of a diagram λ in this formal sum of diagrams is then given by the number of ways to obtain λ from (n) by iterating k times the combinatorial operation associated to U_{(1)}. The identity follows immediately from this fact and from the definition of Kronecker tableaux, where the restriction that the first corner of a diagram can not be distinguished in the next diagram accounts for the −1 term of U_{(1)} = s_{(1)}s_{(1)}^{⊥} − 1. □

Proposition 1 establishes a link between the multiplicity of the irreducible character χ^{λ} in some Kronecker power and sequences of Ferrers diagrams seen as paths in Young’s lattice (the lattice of Ferrers diagrams ordered by inclusion). We rely on this fact to obtain enumerative results about the multiplicity of irreducible representations in the Kronecker power χ^{(n−1,1)⊗k}. The main tool we use is a combinatorial construction defined for a family of paths in Young’s lattice called oscillating tableaux and introduced by Sundaram [13], in a different algebraic context (see also the work of Delest, Dulucq and Favreau [3, 5] for a purely combinatorial point of view).

Briefly, oscillating tableaux are paths in Young’s lattice, that is sequences of Ferrers diagrams, starting at ∅ and such that two consecutive diagrams differ by the addition or removal of exactly one corner.

Example 5. Here is an oscillating tableau of length 7 and final shape (2, 1), that contains five additions of corner and two removal of corner (steps 4 and 7).

∅
⋄

In Lemmas 1 and 2 below, we consider a class of Kronecker tableaux that can be related to oscillating tableaux. This allows to use a variant of the combinatorial construction defined in [13, 3] that will be central in the proof of our main enumerative result, Proposition 2.

Lemma 1. Let n and k be positive integers and λ a partition of n such that n ≥ k +λ_{2}. There is a bijection between Kronecker tableaux of KT_{(n),λ}^{k} and sequences μ^{0}, …, μ^{k} of k Ferrers diagrams such that μ^{0} = ∅, μ^{k} = \overline{λ} and, for every pair μ^{i} and μ^{i+1} of consecutive diagrams, either μ^{i+1} is obtained from μ^{i} by the addition or removal of one corner, or μ^{i+1} differs from μ^{i} by the position of a corner, or μ^{i+1} = μ^{i} and μ^{i+1} has one distinguished corner.

Proof. Let K be a Kronecker tableau of KT_{(n),λ}^{k} such that n ≥ k + λ_{2}. Due to this last condition, the first corner of every Ferrers diagram of K, except possibly the last diagram, is on its first row. Then, by removing the first row of every diagram of K one obtains the sequence μ^{0}, …, μ^{k}. Conversely, consider a sequence of k + 1 Ferrers diagrams μ^{0} = ∅, …, μ^{k} = \overline{λ}. By adding, for every diagram μ^{i}, a first row of length n − |μ^{i}|, one obtains a Kronecker tableau of KT_{(n),λ}^{k}. □

The combinatorial construction we describe below relies partly on the Robinson-Schensted-Knuth (RSK) insertion and deletion algorithms, and we first recall some basic facts about standard tableaux and these algorithms (see [12] for example for details on these algorithms).

• Given a positive integer n and a Ferrers diagram α with at most n cells, a partial standard tableau of shape α and labels in [n] is a labelling of the cells of α with distinct integers chosen from {1, …, n}, such that the labels are increasing in rows (from left to right) and columns (from bottom to top).

• Let S be a partial standard tableau. Given an integer x, the RSK insertion algorithms inserts x into S, creating a tableau S′ whose shape differs from the shape of S by the addition of a corner and labels are the labels of S plus x. Given a corner of S, the RSK deletion algorithm removes this corner and moves some labels of cells of S, this process ending when a label is ejected from the first row of the tableau.

Lemma 2. Let n and k be two positive integers and λ a partition of n such that n ≥ k + λ_{2}. There is a bijection between the set KT_{(n),λ}^{k} and the set of pairs (T, π), where T is a partial standard tableau of shape \overline{λ} with labels in \{1, 2, …, k\} and π is a permutation of k such that: every cycle of π that is not a fixed point is decreasing, every fixed point of π is also the label of a cell of T and every label of T is either the greatest element of a cycle of π or a fixed point of π.

Proof. Let K = ν^{0}, …, ν^{k} be a Kronecker tableau of length k, initial shape (n) and final shape λ, such that n ≥ k + λ_{2}. Let μ^{0}, …, μ^{k} be the sequence of Ferrers diagrams corresponding to K obtained by the construction of Lemma 1.

One can associate to μ^{0}, …, μ^{k} a sequence of partial standard tableaux (T_{0} = ∅, …, T_{k} = T) with entries in {1, 2, …, k} and a permutation π, such that the shape of T_{i} is μ^{i} for every i and in each cycle of π the elements can be presented in decreasing order. We proceed as follows. Start with setting π as the identity permutation on {1, …, k}, and for i from 1 to k:

1. If μ^{i} is obtained from μ^{i−1} by the addition of a corner, then add to T_{i−1} this corner, labelled with i, to obtain T_{i}.

2. If μ^{i} is obtained from μ^{i−1} by the removal of a corner, then delete this corner from T_{i−1}, using the RSK deletion algorithm. If j is the integer ejected from T_{i−1} by the RSK deletion algorithm, then multiply π by the transposition (i, j).

3. If μ^{i} differs from μ^{i−1} by the position of a corner, or μ^{i} = μ^{i−1} and μ^{i−1} has a distinguished corner (therefore μ^{i} and μ^{i−1} have the same weight), then delete this corner from T_{i−1} using again the RSK deletion algorithm, then add the corner needed to obtain μ^{i} and label it with i. If j is the ejected label then multiply π by the transposition (i, j).

The fact that in the permutation π all non fixed point cycles are decreasing follows from the fact that in every transposition (i, j) considered in the construction above one has i > j.

The reverse construction starts with a partial standard tableau T_{k} = T with shape μ^{k} and a permutation π of the set {1, …, k} with each non fixed point cycle in decreasing order such that each entry of T is the greatest element of a cycle of π (including the fixed points). Then perform the following steps, for i from k to 1:

1. If no cell of T_{i} is labelled with i, there exists j < i such that π(i) = j. Then insert the integer j into the tableau T_{i} using the RSK insertion algorithm to obtain T_{i−1} and define μ^{i−1} as the shape of T_{i−1}.

2. If a cell of T_{i} is labelled with i, then remove the cell labelled i: by induction this cell is a corner and this removal gives a partial standard tableau denoted U. 2.a. If furthermore there exists j < i such that π(i) = j, then insert the integer j into the tableau U, using the RSK insertion algorithm, to obtain T_{i−1}, and define μ^{i−1} as the shape of T_{i−1}, distinguishing the corner added during this insertion if it takes the same position than the corner removed from T_{i}. 2.b. Otherwise, after removing i from T_{i}, multiply π by the transposition (i, j), and define μ^{i−1} as the shape of T_{i−1}.

The fact that these two constructions define a bijection follows immediately from its close relationship with the construction on oscillating tableaux defined by Sundaram [13] and Delest, Dulucq and Favreau [3, 5]. □

Example 6. The following Kronecker tableau belonging to KT_{(6),(2,2,2)}^{12}

×

corresponds to the sequence of partial standard tableaux μ^{0}, …, μ^{k}

∅ 1 2 2 3 4 2 3 4 2 4 2 6 4 7 2 6 8 4 2 7 8 4 7 8 10 4 7 8 4 10 8 12 4 10

and to the pair

T = 8 12 4 10 , π = (11, 7)(9, 2)(8, 6)(5, 3)(2, 1) · [(1), (2), … (12)]
= (4)(5, 3)(8, 6)(9, 2, 1)(10)(11, 7)(12).
⋄

To conclude this section, we derive from the above bijection an explicit formula and a generating function for the coefficients χ^{(n−1,1)})^{⊗k}|_{χ^{λ}} when n ≥ k + λ_{2}.

Proposition 2. Let k and n be two positive integers and λ a partition of n such that n ≥ k + λ_{2}. Then

(13)  χ^{(n−1,1)}^{⊗k}|_{χ^{λ}} = f\overline{λ} ∑_{m_{1}=0}^{|\overline{λ}|} (\binom{k}{m_{1}} ∑_{m_{2}=|\overline{λ}|−m_{1}}^{⌊(k−m_{1})/2⌋} \binom{m_{2}}{|\overline{λ}| − m_{1}}p_{2}(k − m_{1}, m_{2})) ,

where f\overline{λ} is the number of standard tableaux of shape \overline{λ} and p_{2}(k−m_{1}, m_{2}) is the number of set partitions of a set of k − m_{1} distinct integers into m_{2} parts of size at least 2.

Proof. From Proposition 1, it is sufficient to enumerate the number of Kronecker tableaux of length k, initial shape (n) and final shape λ. As n ≥ k + λ_{2}, it follows from Lemma 2 that this reduces to the enumeration of some couples (T, π) where T is a partial standard tableau of shape \overline{λ} and π is a permutation on the set \{1, …, k\}. Formula (13) follows if one denotes by m_{1} the number of fixed points of π and m_{2} the number of cycles of size at least 2 in π. □

Remark 2. For integers n and k, the numbers p_{2}(n, k) are known as associated Stirling numbers of second kind (reference A008299 in [17], see also [2, p. 222]). Such numbers are defined by the following recurrence: p_{2}(n, k) = 0 if n < 2k and p_{2}(n, k) = kp_{2}(n − 1, k) + (n − 1)p_{2}(n − 2, k − 1) if n ≥ 2k. The computation of p_{2}(n, k) can also be done by extracting the coefficient of y^{k}x^{n}/n! in e^{yp(x)} where p(x) = e^{x} − x − 1.

Corollary 1. Let ℓ be a positive integer, \overline{λ} = (λ_{2}, …, λ_{m}) an integer partition of ℓ and (n_{k})_{k≥ℓ} an infinite sequence of number such that n_{k} ≥ k + λ_{2} for every k ≥ ℓ. Then

(14)  ∑_{k≥ℓ} χ^{(n_{k}−1,1)}^{⊗k}|_{χ^{λ^{k}}} \frac{x^{k}}{k!} = \frac{f\overline{λ}}{ℓ!} e^{p(x)}(e^{x} − 1)^{ℓ},

where, for every k ≥ ℓ, λ^{k} is the integer partition obtained by adding the part n_{k} − ℓ to \overline{λ}.

Proof. It follows from the fact that n_{k} ≥ k + λ_{2}, Lemma 1, Propositions 1 and 2, that

∑_{k≥ℓ} χ^{(n_{k}−1,1)}^{⊗k}|_{χ^{λ^{k}}} \frac{x^{k}}{k!} = f\overline{λ} ∑_{k≥ℓ} ∑_{m_{1}=0}^{ℓ} (\frac{x^{k}}{k!} \binom{k}{m_{1}} ∑_{m_{2}=ℓ−m_{1}}^{⌊(k−m_{1})/2⌋} \binom{m_{2}}{ℓ − m_{1}}p_{2}(k − m_{1}, m_{2}))

= f\overline{λ} ∑_{m_{1}=0}^{ℓ} \frac{x^{m_{1}}}{m_{1}!} (∑_{k≥ℓ} ∑_{m_{2}=ℓ−m_{1}}^{⌊(k−m_{1})/2⌋} \binom{m_{2}}{ℓ − m_{1}}p_{2}(k − m_{1}, m_{2})\frac{x^{k−m_{1}}}{(k − m_{1})!})

= f\overline{λ} ∑_{m_{1}=0}^{ℓ} \frac{x^{m_{1}}}{m_{1}!} ( ∑_{m_{2}≥ℓ−m_{1}} \binom{m_{2}}{ℓ − m_{1}} ∑_{q≥0} p_{2}(q, m_{2})\frac{x^{q}}{q!} )

= f\overline{λ} ∑_{m_{1}=0}^{ℓ} \frac{x^{m_{1}}}{m_{1}!} ( ∑_{m_{2}≥ℓ−m_{1}} \binom{m_{2}}{ℓ − m_{1}} \frac{p(x)^{m_{2}}}{m_{2}!} )

= f\overline{λ} ∑_{m_{1}=0}^{ℓ} \frac{x^{m_{1}}}{m_{1}!} \frac{p(x)^{ℓ−m_{1}}}{(ℓ − m_{1})!} (∑_{m≥0} \frac{p(x)^{m}}{m!} )

= f\overline{λ} ∑_{m_{1}=0}^{ℓ} \frac{x^{m_{1}}}{m_{1}!} \frac{p(x)^{ℓ−m_{1}}}{(ℓ − m_{1})!}e^{p(x)}

= \frac{f\overline{λ}}{ℓ!} e^{p(x)}(e^{x} − 1)^{ℓ}.

□

Remark 3. J.-Y. Thibon observed in [16] that it is possible to obtain an algebraic proof for the generating function (14) using operators on symmetric functions defined in [14] and in references therein. His proof starts by observing that the left hand side of (14) can be written as exp^{⊗}[x(H(1)h_{1} − H(1))] where H(x) := ∑_{n≥0} h_{n}x^{n} and he expands this expression as follows:

exp^{⊗}[x(H(1)h_{1} − H(1))] = exp^{⊗}[xH(1)h_{1}] ⊗ exp^{⊗}[−xH(1)]

= e^{−x}H(1) exp^{⊗}[h_{1}(e^{x} − 1)]

= H(1)E(−1)^{⊥}e^{−x} exp^{⊗}[(h_{1} + 1)(e^{x} − 1)]

= exp^{⊗}[(e^{x} − x − 1)]⟨exp^{⊗}[(e^{x} − 1)h_{1}]⟩

= e^{p(x)} ∑_{k≥0} \frac{(e^{x} − 1)^{k}}{k!} ⟨h_{1}^{k}⟩

= e^{p(x)} ∑_{k≥0} \frac{(e^{x} − 1)^{k}}{k!} ∑_{\overline{λ}⊢k} f\overline{λ}⟨s\overline{λ}⟩ ,

where E(x) := ∑_{n≥0} e_{n}x^{n} and ⟨f⟩ = H(1)E(−1)^{⊥}f.

Let us call P the permutation representation derived from the group action of 𝔖_{n} on the set {1, 2, …, n} (see [12]) which is simply the well known representation of permutations as permutation matrices. The representation P is not irreducible and it is the direct sum of two irreducible representations: P = A^{(n−1,1)} ⊕A^{(n)} so that we have χ^{P} = χ^{(n−1,1)} + χ^{(n)}.

Corollary 2. Under the same conditions as in Corollary 1 we have

(15)  ∑_{k≥|\overline{λ}|} (χ^{P})^{⊗k}|_{χ^{λ^{k}}} \frac{x^{k}}{k!} = \frac{f\overline{λ}}{ℓ!} e^{e^{x}−1}(e^{x} − 1)^{ℓ},

Proof.

∑_{k≥|\overline{λ}|} (χ^{P})^{⊗k}|_{χ^{λ}} \frac{x^{k}}{k!} = ∑_{k≥|\overline{λ}|} (χ^{(n−1,1)} + 1)^{⊗k}|_{χ^{λ}} \frac{x^{k}}{k!}

= ( ∑_{k≥|\overline{λ}|} (χ^{(n−1,1)})^{⊗k}|_{χ^{λ}} \frac{x^{k}}{k!} ) ( ∑_{k≥|\overline{λ}|} \frac{x^{k}}{k!} )

= \frac{f\overline{λ}}{|\overline{λ}|!}e^{e^{x}−x−1}(e^{x} − 1)^{|\overline{λ}|} × e^{x}

= \frac{f\overline{λ}}{|\overline{λ}|!}e^{e^{x}−1}(e^{x} − 1)^{|\overline{λ}|}.

□

Remark 4. Observe that it follows from our combinatorial construction that every irreducible representation of 𝔖_{n} has a non zero multiciplity in (A^{(n−1,1)})^{⊗k} for k sufficiently large. Notice also that the generating functions that compute the multiciplity of a χ^{λ} in (14) and (15) do not depend on λ but only on the weight of \overline{λ}.

4. Conclusion

We have presented in this note a combinatorial interpretation of the multiplicity of any irreducible representation in a Kronecker power χ^{(n−1,1)}^{⊗k} in terms of sequences of Ferrers diagrams (Kronecker tableaux) that leads, when n is large enough with respect to k and \overline{λ}, to an enumeration formula and a generating function. Moreover, we now have a combinatorial model for the expansion of χ^{μ}^{⊗k} for any μ given by the differential operators U\overline{μ}. However, at this point, the problem of transforming this model into enumerative results in terms of a relationship between n, k, μ and λ is still open.

Our approach could also be extended to the more general case of the computation of χ^{(n−1,1)}^{⊗k} ⊗ χ^{μ}|_{χ^{λ}} for arbitrary μ. This would require the use of a generalization of the oscillating tableaux of Sundaram which already exists and are called skew oscillating tableaux in [4]. However, this construction leads to an intricate expression for the enumeration of Kronecker tableaux of initial shape μ with more than one part, and we were not able to find a compact generating function similar to the one given in Corollary 1.

Acknowledgement. The authors wish to thank Jean-Yves Thibon for his helpful remarks, and Marni Mishna and Cédric Lamathe for interesting discussions.

References

[1] C. Bessenrodt and A. Kleshchev. On Kronecker products of complex representations of the symmetric and alternating groups. Pacific J. Math., 190(2):201–223, 1999.

[2] L. Comtet. Advanced combinatorics. D. Reidel Publishing Co., 1974.

[3] M. Delest, S. Dulucq and L. Favreau. An analogue to the Robinson-Schensted correspondance for oscillating tableaux. Sémin. Lothar. Comb., 20:B20b, 1988.

[4] S. Dulucq and B.E. Sagan. La correspondance de Robinson-Schensted pour les tableaux oscillants gauches. Discrete Math., 139(1–3): 129–142, 1995.

[5] L. Favreau. Combinatoire des tableaux oscillants et des polynômes de Bessel. Ph.D. thesis, LaBRI, Université Bordeaux I (France), 1991.

[6] A. Garsia and J. Remmel. Shuffles of permutations and the Kronecker product. Graphs Combin., 1(3): 217–263, 1985.

[7] A. Lascoux. Produits de Kronecker de représentations du groupe symétrique. In Séminaire d’Algèbre Paul Dubreil et Marie-Paule Malliavin, 32ème année (Paris, 1979). Volume 789 of Lecture Notes in Math., pages 319–329, Springer, 1980.

[8] D.E. Littlewood. The Kronecker product of symmetric group representations. J. London Math. Soc., 31: 89–93, 1956.

[9] I.G. Macdonald. Symmetric Functions and Hall Polynomials. Second edition. The Clarendon Press, Oxford University Press, 1995.

[10] F.D. Murnaghan. The analysis of the Kronecker products of Schur functions of hook shapes. J. Algebra, 120:100–118, 1938.

[11] F.D. Murnaghan. The analysis of the Kronecker products of irreducible representations of the symmetric group. Amer. J. Math., 60: 761–784, 1938.

[12] B.E. Sagan. The symmetric group. Representations, combinatorial algorithms, and symmetric functions. Second edition. Volume 203 of Graduate Texts in Mathematics, Springer-Verlag, 2001.

[13] S. Sundaram. The Cauchy identity for Sp(2n). J. Combin. Theory Ser. A, 53(2):209–238, 1990.

[14] T. Scharf, J.-Y. Thibon and B.G. Wybourne. Reduced notation, inner plethysms and the symmetric group. J. Phys. A, 26(24):7461–7478, 1993.

[15] J.-Y. Thibon. Hopf algebras of symmetric functions and tensor products of symmetric group representations. Internat. J. Algebra Comput., 1(2):207–221, 1991

[16] J.-Y. Thibon. Personnal communication, October 2005.

[17] On-line Encyclopedia of Integer Sequences.

URL http://www.research.att.com/~njas/sequences

Cégep du Vieux Montréal and LaCIM, UQÀM, CP 8888, succ. Centre-ville H3C 3P8, Montréal, QC, Canada

E-mail address: goupil@math.uqam.ca

Computer Science Department and LaCIM, UQÀM, CP 8888, succ. Centre-ville H3C 3P8, Montréal, QC, Canada

E-mail address: chauve@lacim.uqam.ca