\documentclass[12pt]{amsart}

\usepackage{latexsym,amssymb,amsmath}

\usepackage{eufrak}

\textwidth15.6cm
\textheight22.8cm
\hoffset-2truecm
\voffset-.5truecm

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{lemma}{Lemma}%[section]
\newtheorem{proposition}{Proposition}%[section]
\newtheorem{corollary}{Corollary}%[section]
\newtheorem{definition}{Definition}%[section]
\newtheorem{example}{Example}%[section]
\newtheorem{observation}{Observation}%[section]
\newtheorem{remark}{Remark}%[section]

\def\tr{\operatorname{tr}}
\def\Bbb{\mathbb}
\def\a{\alpha}
\def\b{\beta}
\def\c{\chi}
\def\g{\gamma}
\def\d{\delta}
\def\l{\lambda}
\def\L{\Lambda}
\def\m{\mu}
\def\n{\nu}
\def\o{\omega}
\def\p{\pi}
\def\pp{\EuFrak{p}}
\def\r{\rho}
\def\s{\sigma}
\def\t{\tau}
\def\tc{\tilde c}
\def\eps{\varepsilon}
\def\x{{\bf x}}
\def \C {\mathcal C}

\def\S{\EuFrak{S}}

% Drawing Young tableaux and Ferrers diagrams
\usepackage{youngtab}
\Yautoscale1
\Yinterspace5pt

\newcommand{\nil}{\mbox{}}
\def\ten{10}
\def\eleven{11}
\def\twelve{12}
\def\thirteen{13}

                                %
                                %=======================================================
                                %
                                %Fin du preambule
                                %
                                %=======================================================
                                %

\title[Combinatorial operators for Kronecker powers]{Combinatorial operators for Kronecker powers of representations of $\S_n$}


\author{Alain Goupil$^{1}$ and Cedric Chauve$^{2}$} 
\address{ C\'egep du Vieux Montr\'eal and LaCIM, UQ\`AM,  CP 8888,
  succ. Centre-ville H3C 3P8, Montr\'eal, QC, Canada} 
\email{goupil@math.uqam.ca}
\address{Computer Science Department and LaCIM, UQ\`AM, CP 8888,
  succ. Centre-ville H3C 3P8, Montr\'eal, QC, Canada}
\email{chauve@lacim.uqam.ca}


\begin{document}

\footnotetext[1]{Work partially supported by a grant from NSERC.}
\footnotetext[2]{Work partially supported by a grant from UQ\`AM.}

\newbox\Widm
\setbox\Widm\vbox{
\vskip.5cm
\parindent0pt
\leftskip8cm\small\it
Dans ce monde il n'existe que deux trag\'edies~: ne pas obtenir ce que
l'on veut
et obtenir ce que l'on veut.
La derni\`ere est un vrai drame.

\medskip
Oscar Wilde

\vskip.5cm
\leftskip0cm
En math\'ematiques, quand on obtient ce qu'on veut, on en fait un
coquillage
pour tenter de conserver un moule de la pens\'ee \'eph\'em\`ere qui l'a
engendr\'e.
Nous d\'edions cet article \`a Xavier-G\'erard Viennot et \`a ses coquillages
pleins de reliefs.

\vskip.5cm
}

\dedicatory{\box\Widm}

\begin{abstract}
  We present combinatorial operators for the expansion of the
  Kronecker product of irreducible representations of the symmetric
  group $\S_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 {\it Kronecker tableaux}.  Their combinatorial
  analysis leads to enumerative results for the multiplicity of
  irreducible representations in the Kronecker powers of the forms
  ${\c^{(n-1,1)}}^{\otimes k}$ and $P^{\otimes k}$ where $P$ is the
  permutation representation of $\S_n$.
\end{abstract}

\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 54 \rms (2006), Article~B54j\hfill}
\def\thepage{}
%
%

%====================================================================
% Introduction
%====================================================================
\section{Introduction}
\label{sec:intro}

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 $\S_n$. Given two linear
representations  
\begin{eqnarray*}
  {\begin{matrix} A:\S_n\rightarrow Aut(V)\\
      \ \s\,\mapsto\, A(\s)
    \end{matrix}}
  \qquad
  {\begin{matrix} B:\S_n\rightarrow Aut(W)\\
      \ \s\,\mapsto\, B(\s)
    \end{matrix}}
\end{eqnarray*}
which associate linear operators to permutations $\s\in\S_n$, the
Kronecker product of $A$ and $B$, denoted $A\otimes B$, is the
representation of $\S_n$ defined by 
\begin{eqnarray*}
  {\begin{matrix} A\otimes B:\S_n\rightarrow Aut(V\otimes W)\\ 
      \phantom{A\otimes B \S} \s\,\mapsto\, A(\s)\otimes B(\s)
    \end{matrix}}
\end{eqnarray*} 
which is the action on the tensor product $V\otimes W$ of vector
spaces  $V$ and $W$ by means of the tensor product  $A(\s)\otimes
B(\s)$ of the linear operators  $A(\s)$ and  $B(\s)$.   

The irreducible representations of $\S_n$ are the representations
which are indecomposable as direct sums of representations.
They are indexed with the partitions $\l$ of $n$:
\begin{eqnarray*}
  {\begin{matrix}
      A^\l:\S_n\rightarrow Aut(V) \\
      \ \ \ \s\mapsto A^\l(\s).
    \end{matrix}}
\end{eqnarray*}
The Kronecker product $A^\l\otimes A^\m$ of two  irreducible
representations of $\S_n$ is in general not an irreducible
representation of $\S_n$ and the fundamental problem of expanding it
as a direct sum of irreducible representations   
\begin{eqnarray*}
  A^\l\otimes A^\m=\sum_{\a\vdash n}t_{\l,\m}^\a A^\a
\end{eqnarray*} 
goes  back  to the foundation  of the representation theory. This
problem was studied by Murnaghan \cite{Mu,Mu2}, Littlewood \cite{Li}
and more recently by Lascoux \cite{La}, Garsia and Remmel \cite{GR},
Thibon et al.\ \cite{STW,Th2} and others (see \cite{BK} and
references therein).   

To obtain the decomposition coefficients $t_{\l,\m}^\a$, one can use
the characters of the corresponding representations.   
The character of a representation $A$ of $\S_n$ is the map $\c^A$
which sends permutations $\s\in \S_n$ to  the traces of $A(\s)$:  
\begin{eqnarray*}
  {\begin{matrix} \c^A:\S_n\rightarrow \mathbb{C}
      \\
      \phantom{A\otimes B BBBB} \s\,\mapsto\, \tr(A(\s)).
    \end{matrix}
  }
\end{eqnarray*} 
The fact that the character of the Kronecker product $A\otimes B$ of
two representations is obtained by multiplying the traces of the
linear operators $A(\s)$ and $B(\s)$: 
\begin{eqnarray}
  \label{eq1}
  {\begin{matrix} \c^{A\otimes B}:\S_n\rightarrow \mathbb{C}
      \\
      \phantom{A\otimes B \S A\otimes B \S BBBB }  \s\,\mapsto\,
      \tr(A(\s)) \tr( B(\s)) 
    \end{matrix}
  }
\end{eqnarray} 
is a straightforward consequence of the definition of tensor product
of linear operators.  Hence one can use property (\ref{eq1}) of
characters and the character table, indexed by integer partitions of
$n$ (see Table \ref{tab:char} for example) to compute the characters
of a Kronecker product of two irreducible representations. 

Let us recall that character values $\c^A(\s_{1}),\,\c^A(\s_{2})$ on
two permutations $\s_1,\s_2$ in the same conjugacy class $C_\m$ are
always equal. Therefore we use the notation $\c^\l_\m$ for the value
of the irreducible character $\c^\l$ on any element of the conjugacy
class $C_\m$.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL ALAIN GOUPIL AND CEDRIC CHAUVE}{\SMALL COMBINATORIAL
OPERATORS FOR KRONECKER PRODUCTS}
%
%

\begin{example} \label{ex1} \em
  Let Table \ref{tab:char} be the table of the irreducible characters 
  of $\S_4$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
                                %
                                %                             TABLE DES CARACTERES DE S4
                                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \begin{table}[htbp]
    \small
    \begin{center}
      \begin{tabular}{c|r|r|r|r|c}
        {$\l\setminus$}{$\m$} &{ $(4)$} & {$(3,1)$}
        & {$(2,2)$} & {$(2,1^2)$} & {$(1^4)$}
        \rule[-.16cm]{0cm}{.5 cm}\\
        \hline {$(4)$}  &{ $1$} & {$1$} & {$1$} & {$1$} & {$1$}
        \rule[-.16cm]{0cm}{.5 cm}\\ \hline
        {$(3,1)$}  &{ $-1$} & {$0$} & {$-1$} & {$1$} & {$3$}
        \rule[-.16cm]{0cm}{.5 cm}\\ \hline
        {$(2,2)$} &{ $0$}  &{ $-1$} &{ $2$} & {$0$} & {$2$}
        \rule[-.16cm]{0cm}{.5 cm}\\ \hline
        {$(2,1^2)$}  &{ $1$} & {$0$} & {$-1$} & {$-1$} & {$3$}
        \rule[-.16cm]{0cm}{.5 cm}\\ \hline
        {$(1^4)$} &{ $-1$} & {$1$} & {$1$} & {$-1$} & {$1$}
        \rule[-.16cm]{0cm}{.5 cm}
      \end{tabular}
      \smallskip
      \caption{Irreducible characters $\chi^\l_\m$ of $S_4$. \label{tab:char}}
    \end{center}
  \end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  
  The character of the Kronecker product $A^{(3,1)}\otimes 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
  \ref{tab:char} with itself and we obtain
  \begin{eqnarray*}
    \c^{(3,1)\otimes(3,1)}=(1,0,1,1,9)
  \end{eqnarray*} 
  Since Table \ref{tab:char}  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 
  $ 
    \c^{(3,1)\otimes(3,1)} = 
    \c^{(4)}+\c^{(3,1)}+\c^{(2,1,1)}+\c^{(2,2)}  
  $ 
  is true by adding the rows of Table \ref{tab:char} corresponding to
  the partitions in the right hand side.
  \hfill $\diamond$
\end{example}

More generally, the problem of computing the coefficients
$t_{\l,\m}^{\a}$ has a solution when one accepts to use the character
table $[\c^\l_\m]$ of $\S_n$:
\begin{eqnarray} 
  \label{eq3}
  t_{\l,\m}^{\a}=\c^\l\otimes \c^\m|_{\c^\a} = 
  \sum_{\g\vdash n}\frac{|C_\g|}{n!}\c^\l_\g\c^\m_\g\c^\a_\g  .
\end{eqnarray} 
Identity (\ref{eq3}) follows from the orthonormality of the characters
$\c^\l$ with respect to the standard scalar product in the group
algebra of $\S_n$ and from (\ref{eq1}).  But since the coefficients
$t_{\l,\m}^{\a}$ are positive integers, we find equation (\ref{eq3})
unsatisfactory and the goal of this paper is to contribute to other
avenues for computing the coefficients $t_{\l,\m}^{\a}$.
 
Our contribution is to expand $k$th tensor powers
${\chi^{(n-1,1)}}^{\otimes 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 ${\chi^{(n-1,1)}}^{\otimes k}$.
%% and deduce from this model several an explicit formula for
%% ${\c^{(n-1,1)}}^{\otimes k}| _{\c^{{{\l}} }}$ when $n \geq k+\l_2$
%% (Proposition \ref{prop:enumeration}) and two explicit formulas for
%% generating functions associated to thes enumbers (Corollaries
%% \ref{cor:gf} and \ref{cor:gf2}).
One outcome of this combinatorial model is the following exponential
generating function for the multiciplity of $\c^\l$ in
${\chi^{(n-1,1)}}^{\otimes k}$: 
\begin{equation}
  \sum_{k \geq |\overline{\l}|} 
  {\c^{(n_k-1,1)}}^{\otimes k}| _{\c^{\l^k}}
  \frac{x^k}{k!} 
  =  
  \frac{f^{{\overline{\l}}}} {|\overline{\l}|!}  e^{e^x-x-1}
  (e^x-1)^{|\overline{\l}|}, 
\end{equation}
where, $\overline{\l}=(\l_2,\l_3,\ldots$) is an integer partition of
weight $|\overline{\l}|$, and for every $k \geq |\overline{\l}|$, $n_k
\geq k+\l_2$ and $\l^k$ is the integer partition obtained by adding
the part $n_k-|\overline{\l}|$ to ${\overline{\l}}$.    
Now the permutation representation $P$ derived from the action of
$\S_n$ on the set $\{ 1,2,\ldots , n\}$ satisfies
$\c^P=\c^{(n-1,1)}+\c^{(n)}$ where $\c^{(n)}$ is the character of the
identity representation. So we also obtain a nice generating function
for the multiciplity in $(\c^P)^{\otimes k}$
\begin{equation}
  \sum_{k \geq |{\overline{\l}}|} 
  {(\c^{P})}^{\otimes k}| _{\c^{\l^k}}
  \frac{x^k}{k!} 
  =  
  \frac{f^{{\overline{\l}}}} {|\overline{\l}|!}  e^{e^x-1}
  (e^x-1)^{|\overline{\l}|}.
  %%   \sum_{k \geq |{\overline{\l}}|} 
  %%   {( \c^P)}^{\otimes k}| _{\c^{{{\l}} }}
  %%   \frac{x^k}{k!} 
  %%   =  
  %%   \frac{f^{{\overline{\l}}}} { |{\overline{\l}}|!}  e^{e^x-1}
  %% (e^x-1)^{|{\overline{\l}}|}, 
\end{equation}

%====================================================================
% Combinatorial operators
%====================================================================
\section{Combinatorial operators}
\label{sec:operators}

%--------------------------------------------------------------------
% Symmetric functions
%--------------------------------------------------------------------
\subsection{Symmetric functions} 
\label{sub:symfunc}

Let $\mathbb{Q}[\S_n]$ be the group algebra of the symmetric group
over the field $ \mathbb{Q}$  of rational numbers and let
$\mathcal{Z}_n$ be the center of this group algebra. The irreducible
characters of $S_n$ can be seen as elements of $\mathcal{Z}_n$ when
one writes
\begin{eqnarray*}
  \c^\l=\sum_{\s\in\S_n}\c^\l(\s)\s,
\end{eqnarray*} 
and the pointwise multiplication of two elements
$a=\sum_{\s\in\S_n}a_\s\s$ and $b=\sum_{\s\in\S_n}b_\s\s$ of
$\mathbb{Q}[\S_n]$ is defined by 
\begin{equation*}
  a\cdot b=\sum_{\s\in \S_n}(a_\s b_\s)\s.
\end{equation*}
In Example \ref{ex1} we have seen that pointwise multiplication of
characters gives the character of Kronecker product of the
corresponding representations: $\c^\l\cdot\c^\m=\c^{\l\otimes\mu}$. 

Let ${\x}=\{x_1,x_2,\ldots\}$ be a set of indeterminates,
$\L=\L_\mathbb{Q}[\x]$ the ring of symmetric functions in
$x_1,x_2,\ldots$ over the field $\mathbb{Q}$ and $\L^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 $\l =
(\l_1, \ldots, \l_m)$, one defines $h_\l(\x)=\prod_{i=1}^m
h_{\l_i}(\x)$, where $h_r(\x)$ is the $r$th homogeneous symmetric
function, and one denotes by $s_\l(\x)$ the Schur symmetric function
associated to $\l$ (see \cite{macdo}).  The sets
$\{h_\l(\x)\}_{\l\vdash n}$ and $\{ s_\l(\x)\}_{\l\vdash n}$ are
linear basis of $\L^n$. The Frobenius map $\mathcal{F}:
\mathcal{Z}_n\rightarrow \L^n$ is a vector space isomorphism which
sends the irreducible characters $\c^{\l}$ to the Schur functions
$s_\l$ : $\mathcal{F}(\c^{\l})=s_\l$.  Schur functions can be expanded
as determinants of homogeneous functions:
\begin{equation}
  \label{eq4}
  s_\l=\det(h_{\l_i-i+j})_{1\leq i,j\leq n}\,,
\end{equation}
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:  
\begin{equation*}
  s_{\nu^{(1)}}s_{\nu^{(2)}}\cdots s_{\nu^{(r)}} = 
  \sum_\m LR_{\nu^{(1)},\nu^{(2)},\ldots,\nu^{(r)}}^\m s_\m .
\end{equation*}
The adjoint operator to multiplication by $s_\g$ in $\L$ with respect
to the standard scalar product in $\L$  is denoted 
$s_\g^\perp$ and its action on the Schur function $s_\l$ is
 as follows:
\begin{align}
  \label{eq5}
  s_\g^\perp s_\l &= s_{\l/\g}= 
  \begin{cases} 
      \sum_\a LR_{\g,\a}^{\l}s_\a & \mbox{if $\gamma \subseteq \lambda$,}\\
      0 & \mbox{otherwise,}
    \end{cases}
  \\\label{eq6}
  \langle s_\g f,g \rangle &=
  \langle f,s_\g^\perp g \rangle \qquad \text{for all } f,g\in \L.
\end{align} 

Now let us define  in $\L^n$ the operation $f\odot g$ corresponding to
pointwise multiplication in $\mathbb{Q}[\S_n]$ by means of the Frobenius map:   
\begin{equation*}
  f\odot g = 
  \mathcal{F} (\mathcal{F}^{-1} (f)\cdot \mathcal{F}^{-1} (g)) \qquad
  \text{for all }f,\,g,\, \in \L^n. 
\end{equation*}

We shall call this operation\emph{ inner product} of symmetric
functions, and we have in particular 
\begin{equation}
  \label{eq7}
  s_\l\odot s_\m=\sum_\a t_{\l,\m}^\a s_\a,
\end{equation}
where the coefficients $t_{\l,\m}^\a $ are the same than in equation
(\ref {eq3}).  We can expand the inner product $h_\lambda\odot s_\mu$
in the basis \{$s_\a$\} as follows (see also \cite[1.7, Example~23
(d)]{macdo}):  
\begin{align}\label{eq8}
  h_\lambda\odot s_\mu ({\mathbf x}) & 
  =                                   
  \sum_{\{ \nu^{(1)}\vdash \lambda_1,\nu^{(2)}\vdash\lambda_2,\ldots,
    \nu^{(k)}\vdash \lambda_k\}} LR_{\nu^{(1)}\nu^{(2)}\cdots
    \nu^{(k)}}^\mu 
  s_{\nu^{(1)}} \cdots  s_{\nu^{(k)}} \\ 
  \label{eq9}
    &
  = 
  \sum_{\{\nu^{(2)}\vdash\lambda_2,\ldots, \nu^{(k)}\vdash
  \lambda_k\}}(s_{\nu^{(2)}}\cdots
  s_{\nu^{(k)}})(s_{\nu^{(2)}}^\perp\cdots s_{\nu^{(k)}}^\perp )
  s_\mu. 
\end{align}
To prove  identity (\ref{eq8})  in the language of $\l$-rings, it
suffices to notice that $(h_\lambda\odot s_\mu) [{\mathbf X}] =
h_\l[{\mathbf {X  Y}}]|_{s_\m[{\mathbf Y}]}$. Then (\ref{eq8}) follows
from the fact that
$$
h_\l[\mathbf {XY}] = 
\sum_\m\left(\sum_{\{\nu^{(1)}\vdash\l_1,\ldots,\nu^{(k)}\vdash\l_k \}}  
  LR_{\nu^{(1)}\cdots \nu^{(k)}}^\mu s_{\nu^{(1)}} [{\mathbf X}]
  \cdots  s_{\nu^{(k)}}[{\mathbf X}]\right) s_\m[{\mathbf Y}].
$$ 
Identity (\ref{eq9}) follows from (\ref{eq8}) and  (\ref{eq5}).


%--------------------------------------------------------------------
% Operator $U_{\overline{\l}}$
%--------------------------------------------------------------------
\subsection{The operators $U_{\overline{\l}}$}
\label{sub:op-Ul}

\begin{definition}\em 
  \label{def:ulambda}
  Let $\l=(\l_1, \ldots, \l_m)\vdash n$ be a partition of $n$, with
  $\l_1\geq \l_2\geq \ldots \geq\l_m$, and $\overline{\l}$ the
  truncated partition of  $\l$ defined by
  $\overline{\l} = (\l_2, \ldots, \l_m)$.
  One denotes by  $U_{\overline{\l}}$ the operator from $\L^n$ to
  $\L^n$ defined as follows:
  \begin{description}
  \item[a)] 
    Expand the determinant 
    \begin{equation} \label{det}
      \left|\begin{array}{cccc}
          1 & 1 & \ldots & 1 
          \\
          h_{\l_2-1} & h_{\l_2} & \ldots & h_{\l_2+r-2} 
          \\
          \vdots & \vdots & \ldots & \vdots 
          \\
          h_{\l_r-r+1} & h_{_r-r+2}\ldots & \ldots & h_{\l_r}
        \end{array}\right|
    \end{equation}
  \item [b)]
    Replace each term $h_\a=h_{\a_1}h_{\a_2}\cdots h_{\a_m}$ in the
    expansion of  (\ref{det})  by  
    \begin{equation*}
      \sum_{\nu^{(1)}\vdash \a_1,\ldots , \nu^{(m)}\vdash \a_m}
      (s_{\nu^{(1)}}\cdot s_{\nu^{(m)}}) (s_{\nu^{(1)}}^\perp\cdots
      s_{\nu^{(m)}}^\perp) 
    \end{equation*}
    to obtain the operator $U_{\overline{\l}}$.
  \end{description}
\end{definition}

\begin{theorem}
  For any partitions $\l$  and $\mu$ of $n$, we have
  \begin{align*}
    U_{\overline{\l}} s_\m &= s_\l\odot s_\m 
    \\
    &= \sum_{\a\vdash n}t_{\l,\m}^\a s_\a.
  \end{align*}
\end{theorem}

\begin{proof}
  This is a straightforward consequence of equations  (\ref{eq4}),
  (\ref{eq7}) and (\ref{eq9}).
\end{proof}

\begin{example}\label{ex2.1}\em
  The Kronecker product $\c^{(n-1,1)}\otimes 
  \c^\m$ is obtained by applying the operator $U_{(1)}$ on $s_\m$
  which is obtained by  expanding the determinant in Definition \ref{def:ulambda} a)
  and then writing the $h_\l$ in terms of Schur functions using
  Definition \ref{def:ulambda} b):  
  \begin{equation*}
    \left|\begin{array}{cc}
        1 & 1 
        \\
        h_0 & h_1
      \end{array}\right|
    =
    h_1-1\Rightarrow U_{(1)}=s_{(1)}s_{(1)}^\perp-1
  \end{equation*}
  Similarly the operator $U_{(2)}$ needed for the computation of
  $\c^{(n-2,2)}\otimes  \c^\m$ is obtained with the determinant
  \begin{equation*}
    \left|\begin{array}{cc}
        1 & 1 
        \\
        h_1 & h_2
      \end{array}\right|
    =
    h_2-h_1\Rightarrow U_{(2)}=s_{(2)}s_{(2)}^\perp +
    s_{(1,1)}s_{(1,1)}^\perp-s_{(1)}s_{(1)}^\perp
  \end{equation*}
  ~\hfill $\diamond$
\end{example}
       
\begin{remark}\em         
  The fact that the computation of $\c^{\l}\otimes\c^\m$ is independent
  of the  largest part of $\l$  was already observed by Murnaghan
  \cite{Mu2} and also described by Thibon \cite{Th2}, but the definition
  of the operators  $U_{\overline{\l}}$ seems to be new.  
\end{remark}

%==================================================================== 
% Section 3.  A combinatorial model and some consequences
%====================================================================
\section{
  A combinatorial model for $\c^{(n-1,1)\otimes k}$ and some
  consequences
}  
\label{sec:model}
We are now ready to present a combinatorial model for the
multiplicity of irreducible representations in any Kronecker power
$\c^{(n-1,1)\otimes k}$, in terms of paths in Young's lattice.  From
Example \ref{ex2.1}, it is immediate that the expansion of the
Kronecker power $\c^{(n-1,1)\otimes k}$ is obtained by the
application of the operator ${U_{(1)}}^k=(s_{(1)}s_{(1)}^\perp-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.

%--------------------------------------------------------------------
% Introduction of Kronecker tableaux
%--------------------------------------------------------------------
%\medskip
%\paragraph{\bf Kronecker tableaux and the operator $U_{(1)}$.}
When $\l = (\l_1, \ldots, \l_m)$ is an integer partition of $n$, we
call $n$ the weight of $\l$ and we write $|\l|=n$.  We recall that the
unique {\em Ferrers diagram} associated to $\l$ is formed of $m$
stacked rows of cells, ordered from bottom to top in increasing order
and such that the $i^{th}$ row contains $\l_i$ cells.  A cell of a
diagram $\l$ located at the right end of a row and having no cell
above it is called a {\em corner} of $\l$.  For example, in the
following Ferrers diagram, corresponding to the partition $(4,4,2,1)$,
the corners are indicated by $\bullet$.
$$
  \young(\bullet,\nil\bullet,\nil\nil\nil\bullet,\nil\nil\nil\nil)
$$ 
The unique corner of a Ferrers diagram located on a longest row is
called the {\em first corner} of the diagram.   

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

\begin{example}\label{ex3.1}\em
  $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)}$. 
  \hfill
  $\diamond$
\end{example}

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_\m$.  

\begin{definition}\em 
  \label{def:OST}
  Given a positive integer $k$ and partitions $\l$ and $\m$ of same
  weight, a {\em Kronecker tableau} $K$ of length $k$, initial shape
  $\mu$ and final shape $\l$ is a sequence $\n^0=\mu, \n^1, \ldots,
  \n^k=\l$ of Ferrers diagrams where, for every pair of consecutive
  diagrams $\n^i$ and $\n^{i+1}$, {\it either $\n^{i+1}$ differs from
    $\n^i$ by the position of a corner, or $\n^{i+1}=\n^i$ and one
    corner of $\n^{i+1}$, other than its first corner, is
    distinguished. }  One denotes by $KT_{\mu,\l}^k$ the set of {\em
    Kronecker tableaux} of length $k$, initial shape $\m$ and final
  shape $\l$. 
\end{definition}

\begin{example}\em
  \label{ex:OST}
  The following Kronecker tableau --- where a distinguished corner is 
  indicated by a $\times$ --- belongs to $KT^{9}_{(5),(3,2)}$
  $$
  \Yboxdim8pt
  \yng(5) \yng(1,4) \young(\times,\nil\nil\nil\nil) \yng(2,3)
  \yng(1,1,3)  \yng (1,2,2)
  \young(\times,\nil\nil,\nil\nil) \yng(1,1,1,2) \yng(1,2,2)
  \yng(2,3)  
  \Yautoscale1
  $$
\end{example}

\begin{proposition}
  \label{prop:OST-model}
  Let $k$ and $n$ be two positive integers and $\l$ a partition of
  $n$. Then  
  \begin{equation}
    \label{eq:OST-model}
    {\c^{(n-1,1)}}^{\otimes k}|_{\c^\l}
    = 
    |KT_{{(n)},{\l}}^k|.
  \end{equation}
\end{proposition}
\begin{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 $\l$ in this formal sum of diagrams is then
  given by the number of ways to obtain $\l$ 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)}^\perp-1$.
\end{proof}

Proposition~\ref{prop:OST-model} establishes a link between the
multiplicity of the irreducible character $ \chi^\l$ 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
$\c^{(n-1,1)\otimes k}$.
%--------------------------------------------------------------------
% Oscillating tableaux
%--------------------------------------------------------------------
The main tool we use is a combinatorial construction defined for a
family of paths in Young's lattice called {\em oscillating tableaux}
and introduced by Sundaram \cite{Su}, in a different algebraic
context (see also the work of Delest, Dulucq and Favreau \cite{DDF,Fa}
for a purely combinatorial point of view).  

Briefly, oscillating tableaux are paths in Young's lattice, that is
sequences of Ferrers diagrams, starting at $\emptyset$ and such that
{\em two consecutive diagrams differ by the addition or removal of
  exactly one corner}. 
\begin{example}\em
  \label{ex:OT}
  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$).
  $$
   \Yboxdim8pt
  \emptyset \yng(1) \yng(1,1) \yng(1,2) \yng(2) \yng(3) \yng(1,3)
  \yng(1,2) 
  $$
  \hfill $\diamond$
\end{example}

In Lemmas~\ref{lem:bijection1} and \ref{lem:bijection2} 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 \cite{Su,DDF} that will be
central in the proof of our main enumerative result, 
Proposition~\ref{prop:enumeration}.

\begin{lemma}
  \label{lem:bijection1}
  Let $n$ and $k$ be positive integers and $\l$ a partition of 
  $n$ such that $n \geq k + \l_2$. 
  There is a bijection between Kronecker tableaux of $KT_{(n),\l}^k$
  and sequences $\m^0, \ldots, \m^k$ of $k$ Ferrers diagrams such that
  $\m^0=\emptyset$, $\m^k=\overline{\l}$ and, for every pair $\m^i$
  and $\m^{i+1}$ of consecutive diagrams, either $\m^{i+1}$ is obtained
  from $\m^i$ by the addition or removal of one corner, or $\m^{i+1}$
  differs from $\m^i$ by the position of a corner, or $\m^{i+1}=\m^i$
  and $\m^{i+1}$ has one distinguished corner. 
\end{lemma}
\begin{proof}
  Let $K$ be a Kronecker tableau of $KT_{(n),\l}^k$ such that $n \geq
  k + \l_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 $\m^0, \ldots, \m^k$. 
  Conversely, consider a sequence of $k+1$ Ferrers diagrams
  $\m^0=\emptyset, \ldots, \m^k=\overline{\l}$. 
  By adding, for every diagram $\m^i$, a first row of length
  $n-|\m^i|$, one obtains a Kronecker tableau of $KT_{(n),\l}^k$. 
\end{proof}

The combinatorial construction we describe below relies partly on the
{\em Robinson-Schensted-Knuth (RSK) insertion and deletion
  algorithms}, and we first recall some basic facts about {\em
  standard tableaux} and these algorithms (see \cite{Sa} for
example for details on these algorithms).
\begin{itemize}
\item
  Given a positive integer $n$ and a Ferrers diagram $\alpha$ with at 
  most $n$ cells, a {\em partial standard tableau} of shape $\alpha$
  and labels in $[n]$ is a labelling of the cells of $\alpha$ with
  distinct integers chosen from $\{1, \ldots, n\}$, such that the
  labels are increasing in rows (from left to right) and columns
  (from bottom to top).  
\item
  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. 
\end{itemize}

\begin{lemma}
  \label{lem:bijection2}
  Let $n$ and $k$ be two positive integers and $\l$ a partition of $n$
  such that $n \geq k + \l_2$.  There is a bijection between the set
  $KT^k_{(n),\l}$ and the set of pairs $(T,\pi)$, where $T$ is a
  partial standard tableau of shape $\overline{\l}$ with labels in
  $\{1,2,\ldots ,k\}$ and $\pi$ is a permutation of $k$ such that:
  every cycle of $\pi$ that is not a fixed point is decreasing, every
  fixed point of $\pi$ is also the label of a cell of $T$ and every
  label of $T$ is either the greatest element of a cycle of $\pi$ or a
  fixed point of $\pi$.
\end{lemma}

\begin{proof}
  Let $K=\n^0, \ldots, \n^k$ be a Kronecker tableau of length $k$,
  initial shape $(n)$ and final shape $\l$, such that $n \geq k +
  \l_2$. Let $\m^0, \ldots, \m^k$ be the sequence of Ferrers diagrams
  corresponding to $K$ obtained by the construction of 
Lemma~\ref{lem:bijection1}.
  
  One can associate to $\m^0, \ldots, \m^k$ a sequence of partial
  standard tableaux $(T_0=\emptyset, \ldots,\break T_k=T)$ with entries in
  $\{1,2,\ldots ,k\}$ and a permutation $\pi$, such that the shape of
  $T_i$ is $\m^i$ for every $i$ and in each cycle of $\pi$ the
  elements can be presented in decreasing order. We proceed as
  follows. Start with setting $\pi$ as the identity permutation on
  $\{1,\ldots ,k\}$, and for $i$ from $1$ to $k$:
  %\begin{itemize}
  %\item
  \\ {\em 1.}  
  If $\m^{i}$ is obtained from $\m^{i-1}$ by the addition of a corner,
  then add to $T_{i-1}$ this corner, labelled with $i$, to obtain
  $T_i$.
  %\item
  \\ {\em 2.}
  If $\m^{i}$ is obtained from $\m^{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 $\pi$ by the transposition
  $(i,j)$. 
  %\item
  \\ {\em 3.} 
  If $\m^i$ differs from $\m^{i-1}$  by the position of a corner,
  or $\m^i=\m^{i-1}$ and $\m^{i-1}$ has a distinguished corner
  (therefore $\m^i$ and $\m^{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 $\m^i$ and label it
  with $i$.   
  If $j$ is the ejected label  then multiply $\pi$ by the
  transposition $(i,j)$.  
  %\end{itemize}

  The fact that in the permutation $\pi$ 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 $\m^k$ and a permutation $\pi$ of the set
  $\{1,\ldots , k\}$  with each non fixed point cycle in decreasing
  order such that each entry of $T$ is the greatest element of a cycle 
  of $\pi$ (including the fixed points).   
  Then perform the following steps, for $i$ from $k$ to $1$:
  %\begin{itemize}
  %\item
  \\ {\em 1.}
  If no cell of $T_i$ is labelled with $i$, there exists $j < i$ such
  that $\pi(i)=j$. Then insert the integer $j$ into the tableau $T_i$
  using the RSK insertion algorithm to obtain $T_{i-1}$ and define 
  $\m^{i-1}$ as the shape of $T_{i-1}$. 
  %\item
  \\ {\em 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$.
  \\ {\em 2.a.}
  If furthermore there exists $j < i$ such that $\pi(i)=j$, then
  insert the integer $j$ into the tableau $U$, using the RSK insertion 
  algorithm, to obtain $T_{i-1}$, and define $\m^{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$.
  \\ {\em 2.b.}
  Otherwise, after removing $i$ from $T_i$, multiply $\pi$ by the
  transposition $(i,j)$, and define $\m^{i-1}$  as the shape of
  $T_{i-1}$.  
  %\end{itemize}
  
  The fact that these two constructions define  a bijection follows
  immediately from its close relationship with the construction on
  oscillating tableaux defined by Sundaram \cite{Su} and Delest,
  Dulucq and Favreau \cite{DDF,Fa}.  
\end{proof}

\begin{example}\em
  \label{ex:bijection}
  The following Kronecker tableau belonging to $KT^{12}_{(6),(2,2,2)}$
\begin{multline*}
  \Yboxdim8pt
  \yng(6) \yng(1,5) \young(\times,\nil\nil\nil\nil\nil) \yng(2,4)
  \yng(1,2,3) \yng(1,1,4)  \yng (1,2,3)\\
  \Yboxdim8pt
 \yng(2,2,2) \yng(1,1,2,2)
  \yng(1,2,3) \yng(2,2,2) \yng(1,2,3) \yng(2,2,2)
  \Yautoscale1
\end{multline*}
  corresponds to the sequence of partial standard tableaux $\m^0,
  \ldots, \m^k$   
  $$
  \Yboxdim11pt
  \emptyset \young(1) \young(2) \young(23) \young(4,23) \young(4,2)
  \young(4,26)  \young(47,26) \young(8,4,27) \young(8,47)
  \young(8\ten,47)  \young(8,4\ten) \young(8\twelve,4\ten) 
  \Yautoscale1
  $$
  and to the pair
\begin{align*}
  \Yvcentermath1
  T = \young(8\twelve,4\ten),\  
  \pi &=(11,7)(9,2)(8,6)(5,3)(2,1)\cdot[(1),(2),\ldots(12)]\\
  &=(4)(5,3)(8,6)(9,2,1)(10)(11,7)(12).
\end{align*}
  \hfill $\diamond$
\end{example}

%--------------------------------------------------------------------
% Enumerative results
%-------------------------------------------------------------------- 
To conclude this section, we derive from the above bijection an
explicit formula and a generating function for the coefficients
$\c^{(n-1,1)})^{\otimes k}|_{\c^\l}$ when $n\geq k+\l_2$.

\begin{proposition}
  \label{prop:enumeration}
  Let $k$ and $n$ be two positive integers and $\l$ a partition of 
  $n$ such that $n\geq k+\l_2$.  Then
  \begin{equation}
    \label{eq:enumeration}    
    {\c^{(n-1,1)}}^{\otimes k}|_{\c^\l} =
    f^{\overline{\l}}
    \sum_{m_1=0}^{|\overline\l|}
    \left(
      \binom{k}{m_1}
      \sum_{m_2=|\overline\l|-m_1}^{\lfloor (k-m_1)/2 \rfloor}
    \binom{m_2}{|\overline\l|-m_1} p_2(k-m_1,m_2) 
    \right),
  \end{equation}
  where $f^{\overline{\l}}$ is the number of standard tableaux of shape
  $\overline{\l}$ 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$.
\end{proposition}

\begin{proof}
  From Proposition~\ref{prop:OST-model}, it is sufficient to enumerate 
  the number of Kronecker tabl\-eaux of length $k$, initial shape $(n)$  and final shape
  $\l$. As $n\geq k+\l_2$, it follows from Lemma~\ref{lem:bijection2}
  that this reduces to the enumeration of some couples $(T,\pi)$ where
  $T$ is a partial standard tableau of shape $\overline{\l}$ and $\pi$ is a
  permutation on the set $\{1,\ldots ,k\}$. 
 Formula (\ref{eq:enumeration}) follows if one denotes by $m_1$ the
  number of fixed points of $\pi$ and $m_2$ the number  of cycles of
  size at least $2$ in $\pi$. 
\end{proof}

\begin{remark}\em
  \label{rem:p2} 
  For  integers $n$ and $k$, the numbers $p_2(n,k)$ are known
  as  associated Stirling numbers of second kind (reference A008299
  in \cite{Sloane}, see also \cite[p. 222]{Comtet}). 
  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 \geq
  2k$. The computation of $p_2(n,k)$ can also be done by extracting
  the coefficient of $y^k x^n/n!$ in $e^{y p(x)}$ where $p(x) =
  e^x-x-1$. 
\end{remark}

\begin{corollary}
  \label{cor:gf}
  Let $\ell$ be a positive integer, $\overline{\l}=(\l_2,\ldots,
  \l_m)$ an integer partition of $\ell$ and $(n_k)_{k \geq \ell}$ an
  infinite sequence of number such that $n_k \geq k+\l_2$ for every $k 
  \geq \ell$. Then   
  \begin{equation}
    \label{eq:gf-main}
    \sum_{k \geq \ell} 
    {\c^{(n_k-1,1)}}^{\otimes k}| _{\c^{\l^k}}
    \frac{x^k}{k!} 
    =  
    \frac{f^{{\overline{\l}}}} {\ell!}  e^{p(x)} (e^x-1)^{\ell},
  \end{equation}
  where, for every $k \geq \ell$, $\l^k$ is the integer partition
  obtained by adding the part $n_k-\ell$ to ${\overline{\l}}$.  
\end{corollary}
\begin{proof}
  It follows from the fact that $n_k\geq k+\lambda_2$, 
Lemma~\ref{lem:bijection1}, Propositions~\ref{prop:OST-model} and
  \ref{prop:enumeration}, that 
  \begin{align*}
   \sum_{k \geq \ell} 
   {\c^{(n_k-1,1)}}^{\otimes k}|_{\c^{\l^k}} &\frac{x^k}{k!} 
    = 
    f^{{\overline{\l}}}
    \sum_{k \geq \ell} 
    \sum_{m_1=0}^\ell 
    \left(
      \frac{x^k}{k!}
      \binom{k}{m_1}
      \sum_{m_2=\ell-m_1}^{\lfloor (k-m_1)/2\rfloor } 
      \binom{m_2}{\ell-m_1}
      p_2(k-m_1,m_2) 
          \right)
    \\
%    \Longleftrightarrow
%    \sum_{k \geq \ell} {\c^{(n_k-1,1)}}^{\otimes
%    k}|_{\c^{(\overline{\l}^*)}} \frac{x^k}{k!}  
    & = 
    f^{{\overline{\l}}}
    \sum_{m_1 = 0}^\ell
    \frac{x^{m_1}}{m_1!}
    \left(
      \sum_{k \geq \ell}
      \sum_{m_2=\ell-m_1}^{\lfloor(k-m_1)/2\rfloor} 
      \binom{m_2}{\ell-m_1}
      p_2(k-m_1,m_2) 
      \frac{x^{k-m_1}}{(k-m_1)!}
    \right)
    \\
%    \Longleftrightarrow
%    \sum_{k \geq \ell} {\c^{(n_k-1,1)}}^{\otimes
%      k}|_{\c^{(\overline{\l}^*)}} \frac{x^k}{k!}  
    & = 
    f^{{\overline{\l}}}
    \sum_{m_1 = 0}^\ell
    \frac{x^{m_1}}{m_1!}
    \left(
      \sum_{m_2 \geq \ell-m_1}
      \binom{m_2}{\ell-m_1}
      \sum_{q \geq 0}
      p_2(q,m_2)
      \frac{x^{q}}{q!}
    \right)
    \\
%    \Longleftrightarrow
%    \sum_{k \geq \ell} {\c^{(n_k-1,1)}}^{\otimes
%      k}|_{\c^{(\overline{\l}^*)}} \frac{x^k}{k!}  
    & = 
   f^{{\overline{\l}}}
    \sum_{m_1 = 0}^\ell
    \frac{x^{m_1}}{m_1!}
    \left(
      \sum_{m_2 \geq \ell-m_1}
      \binom{m_2}{\ell-m_1}
      \frac{p(x)^{m_2}}{m_2!}
    \right)
    \\
%    \Longleftrightarrow
%    \sum_{k \geq \ell} {\c^{(n_k-1,1)}}^{\otimes
%      k}|_{\c^{(\overline{\l}^*)}} \frac{x^k}{k!}  
    & = 
   f^{{\overline{\l}}}
    \sum_{m_1 = 0}^\ell
    \frac{x^{m_1}}{m_1!}
    \frac{p(x)^{\ell-m_1}}{(\ell-m_1)!}
    \left(
      \sum_{m \geq 0}
      \frac{p(x)^{m}}{m!}
    \right)
      \\
%    \Longleftrightarrow
%    \sum_{k \geq \ell} {\c^{(n_k-1,1)}}^{\otimes
%      k}|_{\c^{(\overline{\l}^*)}} \frac{x^k}{k!}  
    & =  
   f^{{\overline{\l}}}
    \sum_{m_1 = 0}^\ell
    \frac{x^{m_1}}{m_1!}
    \frac{p(x)^{\ell-m_1}}{(\ell-m_1)!}
    e^{p(x)}
    \\
%    \Longleftrightarrow
%    \sum_{k \geq \ell} {\c^{(n_k-1,1)}}^{\otimes
%      k}|_{\c^{(\overline{\l}^*)}} \frac{x^k}{k!}  
    & = 
    \frac{f^{{\overline{\l}}}}{\ell!} e^{p(x)} (e^x-1)^{\ell}.
  \end{align*}  
\end{proof}
\begin{remark}\em
  \label{rem:p9}
J.-Y. Thibon observed in \cite{Th3}  that it is  possible to obtain an algebraic proof for the generating function  (\ref{eq:gf-main}) using operators on symmetric functions defined in \cite{STW} and in references therein. His proof starts by observing that the left hand side of (\ref{eq:gf-main}) can be written as $\exp^{\otimes}[x(H(1)h_1-H(1))]$ where $H(x):=\sum_{n\geq 0}h_nx^n$ and he expands this expression as follows:
\begin{align*}
\exp^{\otimes}[x(H(1)h_1-H(1))] & =  \exp^{\otimes}[xH(1)h_1]\otimes \exp^\otimes [-xH(1)] \\ 
& = e^{-x}H(1) \exp^{\otimes}[h_1(e^x-1)]\\ 
& = H(1) E(-1)^\perp e^{-x} \exp^{\otimes}[(h_1+1)(e^x-1)]\\ 
&=\exp^{\otimes}[(e^x-x-1)]\langle\exp^\otimes[(e^x-1)h_1] \rangle\\ 
&=e^{p(x)}\sum_{k\geq 0}\frac{(e^x-1)^k}{k!}\langle  h_1^k\rangle \\
&=e^{p(x)}\sum_{k\geq 0}\frac{(e^x-1)^k}{k!} \sum_{\overline{\l}\vdash k}f^{\overline{\l}}\langle s_{\overline{\l}}\rangle\,,
\end{align*}
where $E(x):=\sum_{n\geq 0}e_nx^n$ and $\langle f\rangle =H(1)E(-1)^\perp f$.
 \end{remark}
 
 Let us call $P$ the permutation representation derived from the group
 action of $\S_n$ on the set $\{ 1,2,\ldots , n\}$ (see \cite{Sa})
 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)}\oplus A^{(n)}$ so that we have
 $\c^P=\c^{(n-1,1)}+\c^{(n)}$.
\begin{corollary}
  \label{cor:gf2} Under the same conditions as in 
Corollary~\ref{cor:gf} we have  
 \begin{equation}
    \label{eq:gf-main2}
    \sum_{k \geq |{\overline{\l}}|} 
    {(\c^{P})}^{\otimes k}| _{\c^{\l^k}}
    \frac{x^k}{k!} 
    =  
    \frac{f^{{\overline{\l}}}} {\ell!}  e^{e^x-1}
    (e^x-1)^{\ell}, 
  \end{equation}
\end{corollary}
\begin{proof}
  \begin{align*}
    \label{eq:gf-main2p}
    \sum_{k \geq |{\overline{\l}}|} 
    {( \c^P)}^{\otimes k}| _{\c^{{{\l}} }}
    \frac{x^k}{k!} 
    &=    \sum_{k \geq |{\overline{\l}}|} 
    {( \c^{(n-1,1)}+1)}^{\otimes k}| _{\c^{{{\l}} }}
    \frac{x^k}{k!} 
    \\
    &=   \left(  \sum_{k \geq |{\overline{\l}}|}  
      {( \c^{(n-1,1)})}^{\otimes k}| _{\c^{{{\l}} }}
      \frac{x^k}{k!}\right)  \left(  \sum_{k \geq |{\overline{\l}}|}  
      \frac{x^k}{k!}\right)  
    \\
    &=  \frac{f^{{\overline{\l}}}} {|{\overline{\l}}|!}  e^{e^x-x-1}
    (e^x-1)^{|{\overline{\l}}|}\times e^x
    \\
    &= 
    \frac{f^{{\overline{\l}}}} {|{\overline{\l}}|!}  e^{e^x-1}
    (e^x-1)^{|{\overline{\l}}|}.
  \end{align*}
\end{proof}

\begin{remark}\em
  Observe that it follows from our combinatorial construction that every
  irreducible representation of $\S_n$ has a non zero multiciplity in
  $(A^{(n-1,1)})^{\otimes k}$ for $k$ sufficiently large. Notice also
  that the generating functions that compute the multiciplity of a
  $\c^\l$ in (\ref{eq:gf-main}) and (\ref{eq:gf-main2}) do not depend on
  $\l$ but only on the weight of $\overline{\l}$.
\end{remark}

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

Our approach could also be extended to the more general case of the
computation of ${\c^{(n-1,1)}}^{\otimes k} \otimes \c^\mu |_{\c^\l}$
for arbitrary $\mu$. This would require the use of a generalization of
the oscillating tableaux of Sundaram which already exists and are
called {\em skew oscillating tableaux} in \cite{DuSa}.  However, this
construction leads to an intricate expression for the enumeration of
Kronecker tableaux of initial shape $\mu$ with more than one part, and
we were not able to find a compact generating function similar to the
one given in Corollary~\ref{cor:gf}.
 
\bigskip
\noindent
{\bf Acknowledgement}. The authors wish to thank Jean-Yves Thibon for
his helpful remarks, and Marni Mishna and C\'edric Lamathe for
interesting discussions.   

%====================================================================
% Bibliography
%====================================================================
\begin{thebibliography}{99}
                
\bibitem{BK} 
  C.~Bessenrodt and A.~Kleshchev.
  \newblock On {K}ronecker products of complex representations of the
  symmetric and alternating  groups.  
  \newblock {\em Pacific J. Math.}, 190(2):201--223, 1999. 
  
%% \bibitem{ChDu}
%%   C.~Chauve and S.~Dulucq.
%%   \newblock A geometric version of the {R}obinson-{S}chensted
%%   Correspondence for skew oscillating tableaux.
%%   \newblock {\em Discrete Math.}, 246(1--3): 67--81, 2002.

\bibitem{Comtet}
  L.~Comtet.
  \newblock {\em Advanced combinatorics.}
  \newblock D.~Reidel Publishing Co., 1974.

\bibitem{DDF} 
  M.~Delest, S.~Dulucq and L.~Favreau.
  \newblock An analogue to the {R}obinson-{S}chensted correspondance for
  oscillating tableaux. 
  \newblock {\em S\'emin. Lothar. Comb.}, 20:B20b,
  1988. 

\bibitem{DuSa} 
  S.~Dulucq and B.E.~Sagan.
  \newblock La correspondance de {R}obinson-{S}chensted pour les
  tableaux oscillants gauches.  
  \newblock {\em Discrete Math.}, 139(1--3): 129--142, 1995. 

\bibitem{Fa}
  L.~Favreau.
  \newblock {\em Combinatoire des tableaux oscillants et des
    polyn\^omes de Bessel}. 
  \newblock Ph.D. thesis, LaBRI, Universit\'e Bordeaux I (France),
  1991. 

\bibitem{GR} 
  A.~Garsia and J. Remmel.
  \newblock Shuffles of permutations and the {K}ronecker product. 
  \newblock {\em Graphs Combin.}, 1(3): 217--263, 1985.

\bibitem{La} 
  A.~Lascoux.
  \newblock Produits de {K}ronecker de repr\'esentations du groupe
  sym\'etrique. 
  \newblock In {\em S\'eminaire d'Alg\`ebre Paul Dubreil et
    Marie-Paule Malliavin, 32\`eme ann\'ee (Paris, 1979)}.
  \newblock Volume 789 of {\em Lecture Notes in Math.}, pages
  319--329, Springer, 1980. 

\bibitem{Li} 
  D.E.~Littlewood.
  \newblock The {K}ronecker product of symmetric group
  representations. 
  \newblock {\em J. London Math. Soc.}, 31: 89--93, 1956. 

\bibitem{macdo} 
  I.G.~Macdonald.
  \newblock {\em Symmetric Functions and Hall Polynomials.} Second 
  edition.
  \newblock The Clarendon Press, Oxford University Press, 1995. 

\bibitem{Mu}
  F.D.~Murnaghan.
  \newblock The analysis of the {K}ronecker products of Schur
  functions of hook shapes.  
  \newblock {\em J. Algebra}, 120:100--118, 1938.
  
\bibitem{Mu2}
  F.D.~Murnaghan.
  \newblock The analysis of the {K}ronecker products of irreducible
  representations of the symmetric group.  
  \newblock {\em Amer. J. Math.}, 60: 761--784, 1938.
  
\bibitem{Sa}
  B.E.~Sagan.
  \newblock {\em The symmetric group. Representations, combinatorial 
    algorithms, and symmetric functions.} Second edition. 
  \newblock Volume 203 of {\em Graduate Texts in Mathematics},
  Springer-Verlag, 2001. 

\bibitem{Su} 
  S.~Sundaram.
  \newblock The Cauchy identity for Sp(2n).
  \newblock {\em J. Combin. Theory Ser. A}, 53(2):209--238, 1990.
  
\bibitem{STW} 
  T.~Scharf, J.-Y.~Thibon and B.G.~Wybourne. 
  \newblock Reduced notation, inner plethysms and the symmetric
  group. 
  \newblock {\em J. Phys. A}, 26(24):7461--7478, 1993.

\bibitem{Th2} 
  J.-Y.~Thibon.
  \newblock Hopf algebras of symmetric functions and tensor products
  of symmetric group representations. 
  \newblock {\em Internat. J. Algebra Comput.}, 1(2):207--221, 1991
 
 \bibitem{Th3} 
  J.-Y.~Thibon. 
  \newblock  Personnal communication, October 2005. 
 
\bibitem{Sloane}
  On-line Encyclopedia of Integer Sequences.\newline
  URL {\tt http://www.research.att.com/\~{}njas/sequences}

\end{thebibliography}

\end{document}
