%
% An algorithm for characters of Hecke algebras $H_n(q)$ of type $A_{n-1}$
% J. Van der Jeugt
% J. Phys. A: Math. Gen 24 (1991), 3719-3725.
%
(\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}
%
% definitions concerning Young frames
%
\def\mystrut{\hbox{\vrule height9.6pt depth2pt width0pt}}
\def\smallstrut{\hbox{\vrule height 8.6pt depth 1pt width 0pt}}
\def\verysmallstrut{\hbox{\vrule height 3pt depth 1pt width 0pt}}
\def\largestrut{\hbox{\vrule height 11.6pt depth 4pt width 0pt}}
\def\myrulefill{\leaders\hrule height1.4pt\hfill}
\def\norulefill{\leaders\hrule height0pt\hfill}
\def\myvrule{\vrule width1.4pt}
%
% definition for this paper
\def\char{\ch^\la_\rh (q)}
\def\t{{\bf t}}
%
\setlength{\topmargin}{0cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\evensidemargin}{0cm}
\setlength{\textheight}{22.5cm}
\setlength{\textwidth}{16cm}
%
% The Greek symbols defined by the first two letters of their name
%
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\de{\delta}
\def\ep{\epsilon}  \def\vep{\varepsilon}
\def\ze{\zeta}
\def\et{\eta}
\def\th{\theta}
\def\io{\iota}
\def\ka{\kappa}
\def\la{\lambda}
\def\rh{\rho}
\def\si{\sigma}
\def\ta{\tau}
\def\ph{\phi}
\def\ch{\raise 2pt\hbox{$\chi$}}  % raise this a bit
\def\ps{\psi}
\def\om{\omega}
\def\Ga{\Gamma}
\def\De{\Delta}
\def\Th{\Theta}
\def\La{\Lambda}
\def\Si{\Sigma}
\def\Ph{\Phi}
\def\Ps{\Psi}
\def\Om{\Omega}
%
\def\beq{\begin{equation}}
\def\eeq{\end{equation}}
\def\bea{\begin{eqnarray}}
\def\eea{\end{eqnarray}}
\def\beas{\begin{eqnarray*}}
\def\eeas{\end{eqnarray*}}
\def\nn{\nonumber}
%
% the end-of-proof box
\def\mybox{\hfill\llap{$\Box$}}
%
\def\Nat{\mathbb{N}}
\def\Zah{\mathbb{Z}}
\def\Real{\mathbb{R}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
%%
\begin{document}
\addtolength{\baselineskip}{3mm}
%
\title{An algorithm for characters of Hecke algebras $H_n(q)$ of
type $A_{n-1}$}
\author{
J.\ Van der Jeugt\thanks{Research Associate of the NFWO
(National Fund for Scientific Research of Belgium)} \\
{\normalsize Laboratorium voor Numerieke Wiskunde en Informatica,}\\
{\normalsize Rijksuniversiteit Gent, Krijgslaan 281-S9, B9000 Gent,
Belgium}}
%
\maketitle
%
\vskip 1cm
\noindent Classification numbers : 02.20
\vskip 2cm
\begin{abstract}
Recently the characters of irreducible representations of the Hecke
algebra $H_n(q)$ of type $A_{n-1}$ were identified with the transition
coefficients relating $q$-generalised power sum symmetric functions to
Schur functions (King and Wybourne 1990a,b). Using this result, we obtain
an easy combinatorial algorithm for calculating the characters.
\end{abstract}

\newpage

The complex Hecke algebras $H_n(q)$ of type $A_{n-1}$ have become objects
of great interest since the discovery of the Jones polynomial (Jones 1985,
1987) and the recognition of close connections between solvable problems
in statistical physics and corresponding problems in the theory of knots
and braids (Wadati {\sl et al} 1989). The traces of the Hecke algebras
$H_n(q)$ play an important role in applications, and they may be calculated
from explicit constructions of the irreducible representations of
$H_n(q)$ (Dipper and James 1987). Recently, a method was introduced
in order to calculate the traces directly, without first constructing
explicit representations (King and Wybourne 1990a,b). In this letter we
show that this direct method gives rise to an easy combinatorial
algorithm for calculating these traces.

The Hecke algebra $H_n(q)$, with $q$ an arbitrary but fixed complex
parameter, is generated by $g_i$ ($i=1,2,\ldots,n-1$) subject to the
relations
\begin{eqnarray*}
g_i^2 & = & (q-1)g_i + q \qquad\hbox{for}\qquad i=1,2,\ldots,n-1; \\
g_ig_{i+1}g_i & = & g_{i+1}g_ig_{i+1} \qquad\hbox{for}\qquad i=1,2,\ldots,n-1; \\
g_ig_j & = & g_jg_i \qquad\hbox{for}\qquad |i-j|\geq 2.
\end{eqnarray*}
It follows that for $q=1$ the Hecke algebra is the group algebra of
the symmetric group $S_n$, since each $g_i$ can be identified with the
transposition $s_i=(i,i+1)$.

A linear trace on the Hecke algebras was defined by Ocneanu. This theory
expresses the trace of any given element of the Hecke algebra as a linear
sum of traces of so-called minimal words $v$. Such a mininal word $v$
has a certain connectivity class $\rh=(\rh_1,\rh_2,\ldots,\rh_m)$,
where $\rh$ is a partition of $n$ (King and Wybourne 1990a,b). On the
other hand, an irreducible representation $\pi_\la$ of $H_n(q)$ is
also characterised by a partition $\la$ of $n$. Then it was shown by
King and Wybourne (1990a) that the trace of $v$ in the irreducible
representation $\pi_\la$, given by
$$
\hbox{tr}\,\pi_\la(v) = \char \,,
$$
where $\char$ are the Hecke algebra characters, is defined by the relation
\begin{equation}
p_\rh(q;\t) = \sum_\la \char s_\la(\t) \,.
\end{equation}
Herein, $s_\la(\t)$ is a Schur function (Macdonald 1979), and
$p_\rh(q;\t)$ is the $q$-generalised power sum symmetric function defined
by King and Wybourne (1990a)~:
$$
p_\rh(q;\t) = p_{\rh_1}(q;\t) p_{\rh_2}(q;\t) \cdots
$$
with
\begin{equation}
p_d(q;\t) = \sum_{\scriptstyle a,b=0 \atop \scriptstyle a+b+1=d}^{d-1}
 (-1)^b q^a s_{(a+1,1^b)}(\t)\,.
\end{equation}
For $q=1$, the functions $p_\rh(q;\t)$ are the ordinary power sum symmetric
functions, and hence it follows from (1) that in that case the Hecke algebra
characters $\char$ reduce to the
characters of the symmetric group $S_n$ (Macdonald 1979, p.~62).

It follows from (1) and (2) that the Hecke algebra characters $\char$
can be determined by calculating consecutive products of Schur functions
of the type $s_{(a+1,1^b)}(\t)$. This is essentially the method explained
in (King and Wybourne 1990a). In this letter we shall show that this method
can be simplified, leading to a combinatorial expression for $\char$.

We first introduce some new objects. Let $\la$ and $\mu$ be two partitions
with $\la\supset\mu$ (see Macdonald 1979 for the conventions and notations
concerning partitions). The skew diagram $\th=\la-\mu$ is called a
{\sl boundary strip} if it contains no $2\times 2$ block of squares. For
example, if $\la=(12,8,8,8,6,3,2,1)$ and $\mu=(9,7,7,5,4,1,1)$ then
$\th=\la-\mu$ is a boundary strip, corresponding to the shaded boxes in
the following Young diagram of $\la$~:
\begin{equation}
\vcenter
 {\offinterlineskip
 \halign{&\smallstrut\vrule#&\hbox to 9.6pt{\hss$#$\hss}\cr
  \multispan{25}\hrulefill\cr
  & && && && && && && && && &&*&&*&&*&\cr
  \multispan{25}\hrulefill\cr
  & && && && && && && &&*&\cr
  \multispan{17}\hrulefill\cr
  & && && && && && && &&*&\cr
  \multispan{17}\hrulefill\cr
  & && && && && &&*&&*&&*&\cr
  \multispan{17}\hrulefill\cr
  & && && && &&*&&*&\cr
  \multispan{13}\hrulefill\cr
  & &&*&&*&\cr
  \multispan7\hrulefill\cr
  & &&*&\cr
  \multispan5\hrulefill\cr
  &*&\cr
  \multispan3\hrulefill\cr
  }}
\end{equation}
The length of $\th$ is equal to the number of boxes of $\th$ and is
denoted by $|\th|$. In general $\th$ consists of $k$ connected parts
$\th^{(1)}$, $\th^{(2)}$, $\ldots$, $\th^{(k)}$, where $\th^{(1)}$ is
the top right part and $\th^{(k)}$ is the bottom left part. These connected
parts are the {\sl border strips} of $\th$ (Macdonald 1979, p.~31). In
example (3), $\th=\la-\mu$ consists of 4 parts or border strips. Denote
by $r(\th^{(j)})$ (resp.\ $c(\th^{(j)})$~) the number of rows (resp.\
columns) of $\th^{(j)}$ minus 1, and let
$$
r(\th) = \sum_{j=1}^k r(\th^{(j)}), \qquad
c(\th) = \sum_{j=1}^k c(\th^{(j)}).
$$
In example (3), we have $r(\th^{(1)})=0$, $r(\th^{(2)})=3$, $r(\th^{(3)})=1$,
$r(\th^{(4)})=0$, $c(\th^{(1)})=2$, $c(\th^{(2)})=3$, $c(\th^{(3)})=1$, and
$c(\th^{(4)})=0$, thus $r(\th)=4$ and $c(\th)=6$. Note that there exist
some simple relations~:
\begin{eqnarray}
(a)&& |\th|=r(\th) + \hbox{number of columns of }\th \,;  \nonumber\\
(b)&& |\th|=c(\th) + \hbox{number of rows of }\th \,;  \\
(c)&& |\th|=r(\th)+c(\th)+k \,. \nonumber
\end{eqnarray}

\noindent {\bf Definition.}
Let $\th=\la-\mu$ be a boundary strip consisting
of $k$ connected parts. Then
\begin{equation}
f_\th(q) =f_{\la-\mu}(q) = (-1)^{r(\th)} q^{c(\th)} (q-1)^{k-1} \,.
\end{equation}

\noindent {\bf Lemma.}
\begin{equation}
s_\mu(\t) \, p_d(q;\t) = \sum_\la f_{\la-\mu}(q) s_\la(\t) \,,
\end{equation}
where the summation is over all $\la$ such that $\la-\mu$ is a boundary
strip of length $d$.

\noindent {\sl Proof.} From (2) it follows that
\begin{equation}
s_\mu(\t)\, p_d(q;\t) = \sum_{b=0}^{d-1} (-1)^b q^{d-b-1} s_\mu(\t)
 s_{(d-b,1^b)} (\t) \,.
\end{equation}
The idea of the proof is as follows~: we use the Littlewood--Richardson
rule (Macdonald 1979, p.~68) to calculate $s_\mu s_{(d-b,1^b)}$, and
collect the terms in the rhs of (7) having the same $s_\la$. It is quite
remarkable that the $q$-dependent coefficient of $s_\la$ becomes such
a simple expression.

\noindent In order to calculate $s_\mu s_{(d-b,1^b)}$ one has to extend
the Young diagram of $\mu$ in all possible ways to the Young diagram of a
partition $\la$ such that $\la-\mu$ corresponds to a tableau $T$ consisting
of $(d-b)$ 1's, one 2, one 3, $\ldots$, one $b$, and one $b+1$, and
such that $w(T)$ is a lattice permutation (Macdonald 1979, p.~68).
Let us first investigate whether
$T$ can have a $2\times 2$ block of the form
$\vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
  \multispan5\hrulefill\cr
  &\al&&\be&\cr
  \multispan5\hrulefill\cr
  &\ga&&\de&\cr
  \multispan5\hrulefill\cr
  }}
$, with necessarily $\al\leq\be$, $\ga\leq\de$, $\al<\ga$ and $\be<\de$.
$\be$ can be any of the numbers $\{1,2,\ldots,b+1\}$, but since $w(T)$ must
be a lattice permutation and every number $>1$ appears only once in $T$,
it follows that all numbers less that $\be$ have been used
in previous rows and thus $\al=1$.
Then we must have $\ga>\be$ (since $\ga>1$ and all numbers $<\be$ have been
used), and $\de>\be$. But as $w(T)$ has to be a lattice permutation, we can
only have $\de=\be+1$. Then $\ga>\be$ and $\ga\leq\be+1$ lead to only one
possibility~: $\ga=\be+1$. This is forbidden since $\be+1$ can appear only
once. It follows that every term $s_\la$ in $s_\mu s_{(d-b,1^b)}$ is
such that $\la-\mu$ is a boundary strip.

\noindent The next task is to collect all the $q$-dependent coefficients
of a fixed $s_\la$ in the rhs of (7). Before we proceed with the general
proof, it is useful to consider an example. Let $\mu=(9,7,7,5,4,1,1)$,
$d=14$, and $\la=(12,8,8,8,6,3,2,1)$, as in figure~(3). We consider all
tableaux $T$ of shape $\th=\la-\mu$ of weight $(d-b,1^b)$ ($b=0,1,\ldots,
d-1$) such that $w(T)$ is a lattice permutation. For the first part of
$\th$, $\th^{(1)}$, there is only one possible filling of the boxes,
namely
$  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan{7}\hrulefill\cr
   &1&&1&&1&\cr
   \multispan{7}\hrulefill\cr
   }}
$. For the second part of $\th$, $\th^{(2)}$, there are two possible
choices for the number in the top right box of $\th^{(2)}$~: either 1
or else 2. Once the top right box of $\th^{(2)}$ has been filled, there
is no choice for the rest of $\th^{(2)}$, and so there are two possible
fillings of the boxes of $\th^{(2)}$, namely
$
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan6\norulefill&\multispan3\hrulefill\cr
   \multispan6\norulefill&&1&\cr
   \multispan6\norulefill&\multispan3\hrulefill\cr
   \multispan6\norulefill&&2&\cr
   \multispan2\norulefill&\multispan7\hrulefill\cr
   \multispan2\norulefill&&1&&1&&3&\cr
   \multispan9\hrulefill\cr
   &1&&4&\cr
   \multispan5\hrulefill\cr
   }}
$ and
$
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan6\norulefill&\multispan3\hrulefill\cr
   \multispan6\norulefill&&2&\cr
   \multispan6\norulefill&\multispan3\hrulefill\cr
   \multispan6\norulefill&&3&\cr
   \multispan2\norulefill&\multispan7\hrulefill\cr
   \multispan2\norulefill&&1&&1&&4&\cr
   \multispan9\hrulefill\cr
   &1&&5&\cr
   \multispan5\hrulefill\cr
   }}
$. One can proceed with $\th^{(3)}$ and $\th^{(4)}$, leading to the
following 8 possible fillings of $\th$~:
\begin{equation}
\vcenter
 {\offinterlineskip
 \halign{&\mystrut\hbox to 11.6pt{\hss$#$\hss}\cr
 &&&&&&&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan{7}\hrulefill\cr
   &1&&1&&1&\cr
   \multispan{7}\hrulefill\cr
   }}
 &&&&&&& \cr
 &&&&&&&&&&&&&&\cr
 &&&&&\swarrow&&&&\searrow&&&&&\cr
 &&&&&&&&&&&&&&\cr
 &&&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan6\norulefill&\multispan3\hrulefill\cr
   \multispan6\norulefill&&1&\cr
   \multispan6\norulefill&\multispan3\hrulefill\cr
   \multispan6\norulefill&&2&\cr
   \multispan2\norulefill&\multispan7\hrulefill\cr
   \multispan2\norulefill&&1&&1&&3&\cr
   \multispan9\hrulefill\cr
   &1&&4&\cr
   \multispan5\hrulefill\cr
   }}
 &&&&&&&&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan6\norulefill&\multispan3\hrulefill\cr
   \multispan6\norulefill&&2&\cr
   \multispan6\norulefill&\multispan3\hrulefill\cr
   \multispan6\norulefill&&3&\cr
   \multispan2\norulefill&\multispan7\hrulefill\cr
   \multispan2\norulefill&&1&&1&&4&\cr
   \multispan9\hrulefill\cr
   &1&&5&\cr
   \multispan5\hrulefill\cr
   }}
 &&&\cr
 \omit\verysmallstrut&\multispan{14}\norulefill\cr
 &&\swarrow&&\searrow&&&&&&\swarrow&&\searrow&&\cr
 \omit\verysmallstrut&\multispan{14}\norulefill\cr
 &
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan5\hrulefill\cr
   &1&&1&\cr
   \multispan5\hrulefill\cr
   &5&\cr
   \multispan3\hrulefill\cr
   }}
 &&&&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan5\hrulefill\cr
   &1&&5&\cr
   \multispan5\hrulefill\cr
   &6&\cr
   \multispan3\hrulefill\cr
   }}
 &&&&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan5\hrulefill\cr
   &1&&1&\cr
   \multispan5\hrulefill\cr
   &6&\cr
   \multispan3\hrulefill\cr
   }}
 &&&&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan5\hrulefill\cr
   &1&&6&\cr
   \multispan5\hrulefill\cr
   &7&\cr
   \multispan3\hrulefill\cr
   }}
 & \cr
 \omit\verysmallstrut&\multispan{14}\norulefill\cr
 &\swarrow\,\searrow&&&&\swarrow\,\searrow&&&&\swarrow\,\searrow&&&&\swarrow\,\searrow&\cr
 \omit\verysmallstrut&\multispan{14}\norulefill\cr
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan3\hrulefill\cr
   &1&\cr
   \multispan3\hrulefill\cr
   }}
  &&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan3\hrulefill\cr
   &6&\cr
   \multispan3\hrulefill\cr
   }}
  &&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan3\hrulefill\cr
   &1&\cr
   \multispan3\hrulefill\cr
   }}
  &&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan3\hrulefill\cr
   &7&\cr
   \multispan3\hrulefill\cr
   }}
  &&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan3\hrulefill\cr
   &1&\cr
   \multispan3\hrulefill\cr
   }}
  &&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan3\hrulefill\cr
   &7&\cr
   \multispan3\hrulefill\cr
   }}
  &&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan3\hrulefill\cr
   &1&\cr
   \multispan3\hrulefill\cr
   }}
  &&
  \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan3\hrulefill\cr
   &8&\cr
   \multispan3\hrulefill\cr
   }}
  \cr
 \omit\verysmallstrut&\multispan{14}\norulefill\cr
  q^9 && -q^8 && -q^8 && q^7 && -q^8 && q^7 && q^7 && -q^6 \cr
  }}
\end{equation}
Every path in this binary tree from the root to a leaf corresponds to
an allowed tableau $T$ of shape $\th$, and at each branch the numbers that
a part $\th^{(j)}$ is filled with are given. For each filling one can then
find the partition $(d-b,1^b)$ that it originates from, simply by taking the
largest number in the tableau and identifying it with $b-1$. Thus to every
filling, and hence to every leaf of the tree, there corresponds a
contribution $(-1)^b q^{d-b-1}$ from (7). These contributions have been
given in (8), and one sees that their sum is equal to $q^6(q-1)^3 =
(-1)^{r(\th)} q^{c(\th)} (q-1)^{k-1}$.

\noindent Let us now return to the proof of the general case. For
$\th^{(1)}$, the number in the top right box is 1. Suppose $\th^{(1)}$,
$\ldots$, $\th^{(j-1)}$ have been filled, and the numbers used in this
filling so far are $\{1,2,3,\ldots,p-1\}$. Then there are only two
possibilities for the number in the top right box of $\th^{(j)}$~:
either 1 or else $p$. Moreover, once the top right box of a connected
part $\th^{(j)}$ has been filled, there is no choice for the rest of the
boxes of $\th^{(j)}$, if we want to satisfy the lattice permutation rule.
It is one of the two following fillings~:
\begin{equation}
\vcenter
 {\offinterlineskip
 \halign{&\strut\vrule#&\hbox to 20pt{\hss$\scriptstyle#$\hss}\cr
  \multispan{14}\norulefill&\multispan3\hrulefill\cr
  \multispan{14}\norulefill&&1&\cr
  \multispan{14}\norulefill&\multispan3\hrulefill\cr
  \multispan{14}\norulefill&&p&\cr
  \multispan{14}\norulefill&\multispan3\hrulefill\cr
  \multispan{14}\norulefill&&p+1&\cr
  \multispan{14}\norulefill&\multispan3\hrulefill\cr
  \multispan{14}\norulefill&&\vdots&\cr
  \multispan6\norulefill&\multispan{11}\hrulefill\cr
  \multispan6\norulefill&&1&&\cdots&&1&&1&&p'&\cr
  \multispan6\norulefill&\multispan{11}\hrulefill\cr
  \multispan6\norulefill&&p'+1&\cr
  \multispan6\norulefill&\multispan3\hrulefill\cr
  \multispan6\norulefill&&\vdots&\cr
  \multispan9\hrulefill\cr
  &1&&\cdots&&1&&p"&\cr
  \multispan9\hrulefill\cr
  &p"+1&\cr
  \multispan3\hrulefill\cr
  &\vdots&\cr
  \multispan3\hrulefill\cr
  }}
\qquad\hbox{or}\qquad
\vcenter
 {\offinterlineskip
 \halign{&\strut\vrule#&\hbox to 20pt{\hss$\scriptstyle#$\hss}\cr
  \multispan{14}\norulefill&\multispan3\hrulefill\cr
  \multispan{14}\norulefill&&p&\cr
  \multispan{14}\norulefill&\multispan3\hrulefill\cr
  \multispan{14}\norulefill&&p+1&\cr
  \multispan{14}\norulefill&\multispan3\hrulefill\cr
  \multispan{14}\norulefill&&p+2&\cr
  \multispan{14}\norulefill&\multispan3\hrulefill\cr
  \multispan{14}\norulefill&&\vdots&\cr
  \multispan6\norulefill&\multispan{11}\hrulefill\cr
  \multispan6\norulefill&&1&&\cdots&&1&&1&&p'+1&\cr
  \multispan6\norulefill&\multispan{11}\hrulefill\cr
  \multispan6\norulefill&&p'+2&\cr
  \multispan6\norulefill&\multispan3\hrulefill\cr
  \multispan6\norulefill&&\vdots&\cr
  \multispan9\hrulefill\cr
  &1&&\cdots&&1&&p"+1&\cr
  \multispan9\hrulefill\cr
  &p"+2&\cr
  \multispan3\hrulefill\cr
  &\vdots&\cr
  \multispan3\hrulefill\cr
  }}  \,.
\end{equation}
It follows that there are $2^k$ possible fillings of $\th$, with $k$
the number of connected parts of $\th$, i.e.~there are $2^k$ tableaux $T$
of shape $\th=\la-\mu$ with weight $(d-b,1^b)$ ($b=0,1,\ldots,d-1$) and
such that $w(T)$ is a lattice permutation. Each filling corresponds to
a path from the root to a leaf in a
binary tree of depth $k$, where every vertex at depth $j$ is associated with
a filling of $\th^{(j)}$; in (9) the two possibilities are respectively
the left and the
right successor of the vertex associated with $\th^{(j-1)}$.
From (9) it follows that
\begin{equation}
\vbox{
\hbox{for every vertex of the tree which is not a leaf, the number of 1's in the}
\hbox{left successor is one more than the number of 1's in the right successor.}
}
\end{equation}
To determine the $q$-dependent coefficient corresponding to a filling,
one counts the number of 1's appearing in all the $\th^{(j)}$ for a path
in the binary tree starting at the root and ending in a leaf; this number
of 1's is $d-b=|\th|-b$, and thus the coefficient associated to the leaf
is $(-1)^b q^{d-b-1}$. Consider the path to the leftmost leaf of the tree~:
the total number of 1's is equal to the number of columns of $\th$, so it
follows from (4a) that the coefficient corresponding to this leaf is
$(-1)^{r(\th)} q^{|\th|-r(\th)-1}$, which is equal to
$(-1)^{r(\th)} q^{c(\th)+k-1}$ according to (4c). Consider next the path
to the rightmost leaf of the tree~: the total number of 1's is equal to
the number of columns of $\th$ minus $(k-1)$, so the coefficient is
$(-1)^{r(\th)+k-1} q^{c(\th)}$. For an arbitrary leaf, let the path consist
of $i$ steps to the left and $k-1-i$ steps to the right in any order.
Then it follows from (10) that the coefficient associated with this leaf
is $(-1)^{r(\th)+k-1-i} q^{c(\th)+i}$. Therefore the sum of all coefficients
at the leaves of the tree is $(-1)^{r(\th)} q^{c(\th)}(q-1)^{k-1}$.
\mybox

Applying the Lemma for $\mu=0$, and successively for $p_{\rh_1}(q;\t)$,
$p_{\rh_2}(q;\t)$, $\ldots$, and comparing with (1), one finds

\noindent {\bf Theorem.} 
Let $\rh=(\rh_1,\rh_2,\ldots,\rh_m)$ and $\la$ be
partitions of $n$, then
\begin{equation}
\char = \sum_S \prod_{i=1}^m f_{\la^{(i)}-\la^{(i-1)}}(q) \,,
\end{equation}
summed over all sequences of partitions $S=(\la^{(0)},\la^{(1)},\ldots,
\la^{(m)})$ with $0=\la^{(0)}\subset\la^{(1)}\subset \cdots \subset
\la^{(m)}=\la$ such that $\la^{(i)}-\la^{(i-1)}$ is a boundary strip
of length $\rh_i$.

\noindent {\bf Example}. Let $n=4$ and $\rh=(2,2)$. The following gives a
list of all possible diagrams built with two boundary strips of length 2.
The notation is such that the boxes of $\la^{(i)}-\la^{(i-1)}$ are
labelled by the number $i$ (do not confuse this labelling with the filling
of the tableaux in the proof of the Lemma)~:
$$
\begin{array}{cccccccc}
 \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan9\hrulefill\cr
   &1&&1&&2&&2&\cr
   \multispan9\hrulefill\cr
   }}
&
 \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan7\hrulefill\cr
   &1&&1&&2&\cr
   \multispan7\hrulefill\cr
   &2&\cr
   \multispan3\hrulefill\cr
   }}
&
 \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan5\hrulefill\cr
   &1&&1&\cr
   \multispan5\hrulefill\cr
   &2&&2&\cr
   \multispan5\hrulefill\cr
   }}
&
 \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan5\hrulefill\cr
   &1&&1&\cr
   \multispan5\hrulefill\cr
   &2&\cr
   \multispan3\hrulefill\cr
   &2&\cr
   \multispan3\hrulefill\cr
   }}
&
 \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan7\hrulefill\cr
   &1&&2&&2&\cr
   \multispan7\hrulefill\cr
   &1&\cr
   \multispan3\hrulefill\cr
   }}
&
 \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan5\hrulefill\cr
   &1&&2&\cr
   \multispan5\hrulefill\cr
   &1&&2&\cr
   \multispan5\hrulefill\cr
   }}
&
 \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan5\hrulefill\cr
   &1&&2&\cr
   \multispan5\hrulefill\cr
   &1&\cr
   \multispan3\hrulefill\cr
   &2&\cr
   \multispan3\hrulefill\cr
   }}
&
 \vcenter
  {\offinterlineskip
  \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan3\hrulefill\cr
   &1&\cr
   \multispan3\hrulefill\cr
   &1&\cr
   \multispan3\hrulefill\cr
   &2&\cr
   \multispan3\hrulefill\cr
   &2&\cr
   \multispan3\hrulefill\cr
   }}
\\
q^2 & q(q-1) & q^2 & -q & -q & 1 & -(q-1) & 1
\end{array}
$$
The $q$-coefficient written underneath each sequence of 2 boundary strips
of length 2
is $\prod_{i=1}^2 f_{\la^{(i)}-\la^{(i-1)}}(q)$. Thus we obtain for
$\rh=(2,2)$~:
$$
\begin{tabular}{c|c}
$\la$ & $\char$ \\
\hline
(4) & $q^2$ \\
(3,1) & $q^2-2q$ \\
(2,2) & $q^2+1$ \\
(2,1,1) & $-2q+1$ \\
(1,1,1,1) & $1$
\end{tabular}
$$

The expressions for $\char$ for special values of $\la$ or $\rh$
are easily obtained from (11)~:
\begin{eqnarray*}
\ch^{(n)}_\rh(q) & = & \prod_{i=1}^m q^{\rh_i-1} = q^{|\rh|-l(\rh)}
\qquad (m=l(\rh)=\hbox{length of }\rh) ; \\
\ch^{(1^n)}_\rh(q) & = & \prod_{i=1}^m (-1)^{\rh_i-1} = (-1)^{|\rh|-l(\rh)} ;\\
\ch^\la_{(n)}(q) & = & \cases{(-1)^b q^{n-b-1}, & if $\la=(n-b,1^b)$,\cr
                              0 & otherwise;\cr} \\
\ch^\la_{(1^n)}(q) & = & \ch^\la_{(1^n)} = \hbox{number of standard Young
tableaux of shape $\la$}.
\end{eqnarray*}
These special cases, together with other examples, can be verified using
the tables of King and Wybourne (1990b).

Finally, it should be noted that a result similar to~(11) has been
obtained by A.~Ram (1990), using very different techniques. The existence
of this preprint was pointed out to the author after the completion of
the present manuscript.

\vskip 1cm
\noindent REFERENCES
\vskip 2mm
\noindent
Dipper R and James G (1987) {\sl Proc.\ London Math.\ Soc.} (3) {\bf 54} 57
\vskip 2mm
\noindent
Jones VF (1985) {\sl Bull.\ Amer.\ Math.\ Soc.} {\bf 12} 103
\vskip 2mm
\noindent
 --- (1987) {\sl Ann.\ Math.} {\bf 126} 335
\vskip 2mm
\noindent
King RC and Wybourne BG (1990a) ``Characters of Hecke algebras $H_n(q)$
of type $A_{n-1}$,'' University of Southampton preprint, submitted to
{\sl J.\ Phys.\ A~: Math.\ Gen.}
\vskip 2mm
\noindent
 --- (1990b) ``Representations and traces of Hecke algebras $H_n(q)$
of type $A_{n-1}$,'' University of Southampton preprint, submitted to
{\sl J.\ Math.\ Phys.}
\vskip 2mm
\noindent
Macdonald I (1979) {\sl Symmetric functions and Hall polynomials} (Oxford~:
Clarendon Press)
\vskip 2mm
\noindent
Ram A (1990) ``A Frobenius formula for the characters of the Hecke algebras,''
University of California (San Diego) preprint
\vskip 2mm
\noindent
Wadati M, Deguchi T and Akutsu Y (1989) {\sl Phys.\ Rep.\ C} {\bf 180} 247

%
\end{document}