% An AMSTeX file for a 9 page document
\input amstex
\TagsOnRight
\magnification\magstep1
\hsize=6 true in
\vsize=9 true in
\documentstyle{amsppt}%\nologo
\newcount\refcount
\advance\refcount 1
\def\newref#1{\xdef#1{\the\refcount}\advance\refcount 1}
\newref\AldousDiaconis
\newref\BarbaschVogan
\newref\CohenRegev
\newref\DS
\newref\Hammersley
\newref\Johansson
\newref\Kirillovetal
\newref\KnuthIII
\newref\Mehta
\newref\Odlyzko
\newref\mythesis
\newref\Regev
\newref\Sagan
\newref\Schutzenberger
\newref\StantonWhite
\newref\Weyl
\newref\White


\def\Tr{\mathop{\roman{Tr}}\nolimits}
\title
Increasing subsequences and the classical groups
\endtitle
\author
E. M. Rains
\endauthor
\affil
AT\&T Research
\endaffil
\address
AT\&T Research, 180 Park Avenue, Florham Park, NJ 07932-0971
\endaddress
\email
rains\@research.att.com
\endemail
\date Submitted: November 24, 1997; Accepted: January 30, 1998 \enddate
\abstract
We show that the moments of the trace of a random unitary matrix have
combinatorial interpretations in terms of longest increasing subsequences
of permutations.  To be precise, we show that the $2n$-th moment of
the trace of a random $k$-dimensional unitary matrix is equal to the
number of permutations of length $n$ with no increasing subsequence
of length greater than $k$.  We then generalize this to other expectations
over the unitary group, as well as expectations over the orthogonal and
symplectic groups.  In each case, the expectations count objects with
restricted ``increasing subsequence'' length.

\endabstract
\subjclass Primary 05E15, Secondary 05A15 05A05\endsubjclass
\endtopmatter
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 5
(1998), \#R12\hfill\folio} \fi}
\document

\head
Introduction
\endhead

Much work has been done in the combinatorial literature on the
``increasing subsequence problem'', that of studying the distribution
of the length of the longest increasing subsequence of a random
permutation.  The problem was first considered by Hammersley
(\cite{\Hammersley}); good summaries can be found in \cite{\AldousDiaconis} and
\cite{\Odlyzko}, which gives an alternate proof of Theorem 1.1.  This
problem is also closely connected to the representation theory of
$S_n$, particularly the theory of Young tableaux.  The representation
theory aspects are covered in \cite{\Sagan}; section 5.1.4 in \cite{\KnuthIII}
gives a good treatment of the more elementary Young tableaux results.

The results reported here arose from the observation that a certain partial
sum of characters of the symmetric group that occurs naturally in the
increasing subsequence problem also appears when calculating certain
expectations over the unitary group.  In particular, it turns out that the
distribution of the length of the longest increasing subsequence can be
expressed exactly in terms of the moments of the trace of a random
(uniformly distributed) unitary matrix.  This correspondence generalizes
both to other moments for the unitary group, and to the moments of the
trace of a random orthogonal or symplectic matrix.  In each case, the
moments count objects (colored permutations, signed permutations, or
fixed-point-free involutions) with restricted increasing subsequence
length.

Section 1 states and proves the connection between the classical
increasing subsequence problem and the unitary group. Section 2
extends this to other increasing subsequence problems connected to the
unitary group, including an increasing subsequence problem for signed
permutations (the hyperoctahedral group).  Section 3 gives the
corresponding results for the other classical groups.  Finally,
section 4 proves an alternate form of theorem 1.1, originally given in
\cite{\Odlyzko}.

This work is taken from section 5 of the author's Ph.D. thesis (\cite{\mythesis}).

\head
1. The classical increasing subsequence problem
\endhead

In \cite{\DS}, Diaconis and Shashahani give the following result:
$$
E_{U\in U(k)}\left(\left|\Tr(U)^n\right|^2\right)=n!,
$$
for $n\le k$, where the expectation is taken with respect to Haar measure.
A natural question is then: what happens for $n>k$?  By refining their
methods, one can prove the following:

\proclaim{Theorem 1.1}
Define
$$
f_{nk}=E_{U\in U(k)}\left(\left|\Tr(U)^n\right|^2\right).
\xdef\eqI{{1.1}}
\tag\eqI
$$
Then $f_{nk}$ is the number of permutations $\pi$ of $\{1\ldots n\}$ such
that $\pi$ has no increasing subsequence of length greater than $k$.
(An increasing subsequence is a sequence $i_1<i_2<\ldots<i_m$ such that
$\pi(i_1)<\pi(i_2)<\ldots<\pi(i_m)$.)
\endproclaim

\demo{Proof}
As in \cite{\DS}, we can think of this as an inner product of $\Tr(U)^n$
with itself; since the nonzero Schur functions are orthonormal with respect
to this inner product, we can simplify things by expanding
$\Tr(U)^n=p_{1^n}(U)$ (a power-sum symmetric function) into Schur
functions.  In general, for any expression of the form
$E_{U\in U(k)}(p_\lambda(U)\overline{p_\mu(U)})$,
we can expand the power-sum functions into Schur functions, getting the
following formula:
$$
\align
E_{U\in U(k)}\left(p_\lambda(U)\overline{p_\mu(U)}\right)&=
\sum_{\nu,\kappa\vdash n} \chi^\nu_\lambda \chi^\kappa_\mu E_{U\in
U(k)} \left(s_\nu(U) s_\kappa(U)\right)\\
&=
  \sum_{{\nu\vdash n}\atop{\ell(\nu)\le k}}
     \chi^\nu_\lambda \chi^\nu_\mu,
\xdef\eqII{{1.2}}
\tag\eqII
\endalign
$$
where $\chi^\nu_\lambda$ is the character of the symmetric group with label
$\nu$ evaluated at a permutation of cycle type $\lambda$.
In particular, for $\lambda=\mu=1^n$, we get
$$
E_{U\in U(k)}\left(\left|p_{1^n}(U)\right|^2\right)=
  \sum_{{\lambda\vdash n}\atop{\ell(\lambda)\le k}}
    \left(\chi^\lambda_{1^n}\right)^2.
\xdef\eqIII{{1.3}}
\tag\eqIII
$$
Thus, we are left with the purely combinatorial question of evaluating the
sum on the right.

Recall that $\chi^\lambda_{1^n}$ is equal to the number of Young
tableaux of shape $\lambda$.  Thus (\eqIII) is counting the
number of pairs of Young tableaux with the same shape, with size $n$,
and with width at most $k$.  But, by Schensted's correspondence, this
is exactly equal to the number of permutations of $S_n$ with longest
increasing subsequence of length at most $k$, and the theorem is proved.
\qed\enddemo

(Notation remark: in the sequel, $f_{nk}$ will refer to the combinatorial
quantity, rather than to the formula over $U(k)$; similar remarks apply to
the generalizations of $f_{nk}$ defined below)

\head
2. Other increasing subsequence problems
\endhead

Given this result, it is natural to investigate the possibility of
generalizing Theorem 1.1 to give combinatorial interpretations of
other similar formulae on $U(k)$.  By (\eqII), this boils down to
finding combinatorial interpretations of
$$
\sum_{{\nu\vdash n}\atop{\ell(\nu)\le k}}
  \chi^\nu_\lambda \chi^\nu_\mu.
$$
Now, \cite{\White} and \cite{\StantonWhite} give a generalization of
Schensted's correspondence connecting ``hook permutations'' and pairs
of rim-hook tableaux of the same shape, analogous to Schensted's
correspondence, including, in some special cases, an increasing
subsequence style result.

Let $S^{(m)}_n$ be the set of functions from $\{1\ldots n\}$ to $\{1\ldots
n\}\times\{1\ldots m\}$ such that the function yields a permutation when
projected onto the first component.  In other words, the elements of
$S^{(m)}_n$ are essentially colored permutations.  (This is a special case
of Stanton and White's concept of a hook permutation; the general
definition is unnecessary for our purposes.)  Then \cite{\StantonWhite}
gives a bijection between $S^{(m)}_n$ and pairs of rim-hook tableaux of the
same shape and content $m^k$.

Let us define an increasing subsequence of $\pi\in S^{(m)}_n$ as a
sequence $i_1<i_2<\ldots<i_k$ such that the first components of
$\pi(i_j)$ are increasing in $j$, and such that the second components
of $\pi(i_j)$ are all equal.  If $p$ is the second component, then the
length of the increasing subsequence is defined to be $m(k-1)+p$.

\proclaim{Lemma 2.1}
For $\pi\in S^{(m)}_n$, the length of the longest
increasing subsequence of $\pi$ is equal to the width of the rim-hook tableaux
corresponding to $\pi$.
\endproclaim

\demo{Proof}
Theorem 36 of \cite{\StantonWhite} gives only that $\lceil
{l\over m}\rceil=\lceil {w\over m}\rceil$, where $l$ is the length of
the longest increasing subsequence, and $w$ is the width of the
rim-hook tableaux.  However, it is straightforward to get this slight
refinement using essentially the same proof.
\qed\enddemo

Then, using (\eqII) and the Murnaghan-Nakayama formula for the characters
of the symmetric group (where we remark that the sign of a rim-hook tableau
of content $m^k$ depends only on its shape, so can be ignored), we have
immediately

\proclaim{Theorem 2.2}
Define
$$
f^{(m)}_{nk}=E_{U\in U(k)}\left(\left|\Tr(U^m)^n\right|^2\right).
$$
Then $f^{(m)}_{nk}$ is the number of $\pi\in S^{(m)}_n$ such that
$\pi$ has no increasing subsequence of length greater than $k$.
\endproclaim

\demo{Remark}
\cite{\DS} gives the following formula:
$$
E_{U\in U(k)} \left(\left|\Tr(U^m)^n\right|^2\right)=m^n n!,
$$
for $k\ge mn$. This also follows from theorem 2.2; if $k\ge mn$, then
no element of $S^{(m)}_n$ has an increasing subsequence of length
greater than $k$.  Thus $f^{(m)}_{nk}=|S^{(m)}_n|=m^n n!$.
\enddemo

For other values of $\lambda$, (or, especially, when $\lambda\ne\mu$), we
encounter a major difficulty in finding a combinatorial interpretation of
the character sum $(\eqII)$.  The problem is that the Murnaghan-Nakayama
formula is, in general, an alternating sum.  This causes problems with the
generalized Schensted correspondence; when counting pairs of tableaux, it
is necessary to consider signs.  In order to make the total character sum
work out, Stanton and White's construction needs to pair up all pairs with
opposite signs with pairs having the same signs.  This pairing,
unfortunately, does not respect shape.  Thus, only in those cases in which
the signs in the Murnaghan-Nakayama formula are constant for each shape can
we expect a nice result as above.  (At least for $k$ small; in the case
$|\lambda|,|\mu|\le k$, \cite{\DS} gives a closed form for $E_{U\in
U(k)}(p_\lambda(U)\overline{p_\mu(U)})$.)  The signs in the case
$\lambda=\mu=m^n$ are constant, as we mentioned above; the only remaining
case (as far as the author knows) with constant signs is
$\lambda=\mu=2^n1$, so it is natural to look for a combinatorial
interpretation in this case.

Define $B_n$ to be the hyperoctahedral group, defined as the group
of permutations $\rho$ of $\{-n,-n+1,\ldots,-1,1,\ldots,n-1,n\}$ such
that $\rho(-x)=-\rho(x)$.  An element of $B_n$ is determined by two
data: $|\rho(|x|)|$, which permutes $\{1,2,\ldots,n\}$, and the sign
of $\rho(i)$ for $1\le i\le n$.  This gives a bijection between $B_n$
and the wreath product $Z_2\wr S_n$; thus, $|B_n|=2^n n!$.  The
order-preserving map between $\{-n,-n+1\ldots,-1,1,\ldots,n-1,n\}$ and
$\{1,2,\ldots n\}$ gives an imbedding of $B_n$ in $S_{2n}$; the
defining relation of $B_n$ becomes $\rho(2n+1-x)=2n+1-\rho(x)$.  For
our purposes, we also need an imbedding of $B_n$ in $S_{2n+1}$.  This
is done by adding $0$ to the set $B_n$ permutes (naturally,
$\rho(0)=0$); we get a permutation on $\{1,2,\ldots 2n+1\}$ by a
translation.  The defining relation in that case is
$\rho(2n+2-x)=2n+2-\rho(x)$.

\proclaim{Theorem 2.3}
Define
$$
\align
b_{(2n)k}&=E_{U\in U(k)}\left(\left|Tr(U^2)^n\right|^2\right)\\
b_{(2n+1)k}&=E_{U\in U(k)}\left(\left|Tr(U^2)^nTr(U)\right|^2\right).
\endalign
$$
Then $b_{Nk}$ is equal to the number of elements of $B_{\lfloor{N\over
2}\rfloor}$ that have no increasing subsequence of length greater than
$k$, considered as an element of $S_N$.  
\endproclaim

\demo{Proof}
A ``domino tableau'' is defined (see, for instance, \cite\Kirillovetal) as
a rim-hook tableau with content $2^n$; every value appears in two
neighboring positions.  Similarly we define an ``almost-domino tableau'' as
a rim-hook tableau with content $2^n1$.  Using the Murnaghan-Nakayama
formula, we have that $\chi^\nu_{2^n}$ is equal (up to sign) to the number
of domino tableaux of size $2n$, and $\chi^\nu_{2^n1}$ is equal (again up
to sign) to the number of almost-domino tableaux of size $2n+1$.  Thus, we
need to relate domino or almost-domino tableaux to the hyperoctahedral
group.

We associate to each element of $B_n$ a pair of tableaux of size $N$
of the same shape, by applying the Schensted correspondence to the
corresponding element of $S_N$.  In order to count these tableaux,
then, we need a more useful characterization of them.  Since
$B_n\subset S_N$ is characterized as the subgroup of $\rho$ such that
$N+1-\rho(N+1-x)=\rho(x)$, we need to understand how this
transformation acts on tableaux.  This action can be stated in terms
of a certain dualization operation on tableaux (due to
Sch\"utzenberger \cite{\Schutzenberger}).  The dual of a tableau is
defined as follows:

Let $D_1$ be the following operation on tableaux: delete the top-left
element of the tableaux, then move the lesser of the element
immediately below and the element immediately to the right into the
vacated spot, and continue until the edge of the tableaux is reached.
For example:
$$
\matrix
1&3&5\\
2&4\\
6
\endmatrix\to\matrix
&3&5\\
2&4\\
6
\endmatrix\to\matrix
2&3&5\\
&4\\
6
\endmatrix\to\matrix
2&3&5\\
4\\
6
\endmatrix
$$
To construct the dual of a tableaux, apply operation $D_1$
repeatedly until the tableaux is empty; the dual tableaux has a $1$ in
the last position vacated, a $2$ in the second-to-last position
vacated, etc.  Clearly, then the dual of a tableaux has the same
shape.  Furthermore, we have the following lemma (\cite{\KnuthIII}, section
5.1.4, theorem D):

\proclaim{Lemma 2.4}
Let $\pi\in S_N$ correspond to the pair of Young tableaux $(T_1,T_2)$.  Then
the pair of tableaux corresponding to $x\mapsto N+1-\pi(N+1-x)$ is
$(T_1^*,T_2^*)$, where $T^*$ is the dual of $T$.
\endproclaim

(Note that it follows immediately from this that $(T^*)^*=T$).

Thus, under the Schensted correspondence in $S_N$, $B_n$ corresponds
to the set of pairs of self-dual tableaux.  The following result is
known (proposition 17 in \cite{\BarbaschVogan}; see also
\cite{\Kirillovetal}):

\proclaim{Lemma 2.5}
There is a bijection between the set of self-dual tableaux of shape $\lambda$
and the set of domino (almost-domino) tableaux of shape $\lambda$.
\endproclaim

Theorem 2.3 follows immediately.
\qed\enddemo

\demo{Remark}
We have two interpretations of $E_{U\in U(k)}(|\Tr(U^2)^n|^2)$, namely
the combinatorial versions of $f^{(2)}_{nk}$ and $b_{(2n)k}$.  It is unclear
whether there is a simpler proof that these two combinatorial quantities are
the same; unfortunately, the natural bijection between $S^{(2)}_n$ and $B_n$
does not preserve increasing subsequence length.
\enddemo

\demo{Remark}
Again, \cite{\DS} gives theorem 2.3, in the
special case $k\ge N$.
\enddemo

\head
3. The other classical groups
\endhead

The above results can be extended, in the simpler cases, to the orthogonal
and symplectic groups, using some facts on the expectations of Schur
functions over these groups.  In particular, for any partition $\lambda$,
$E_{O\in O(k)} (s_{\lambda}(O))$ is either 1 or 0; its value is 1 if and
only if $\lambda$ has at most $k$ elements, each of which is even.  This
follows from the fact that only those representations of $U(n)$ contain a
copy of the trivial representation when restricted to $O(n)$.  Similarly,
$E_{S\in Sp(2k)} (s_{\lambda}(S))$ is 1 if and only if $\lambda$ has at
most $2k$ elements, and every number appears an even number of times in
$\lambda$ (alternatively, every element of the transpose $\lambda'$ of
$\lambda$ is even).  A straightforward modification of the first part of
the proof of theorem 1.1 gives:

\proclaim{Lemma 3.1}
$E_{O\in O(k)} (\Tr(O)^n)$ is equal to the number of Young tableaux of
size $n$ of width at most $k$ with each column of even length.
\endproclaim

\noindent And similarly for the symplectic group:

\proclaim{Lemma 3.2}
$E_{S\in Sp(k)} (\Tr(S)^n)$ is equal to the number of Young tableaux
of size $n$ of width at most $2k$ with each row of even length.
\endproclaim

It remains then to interpret this number in a more straightforward
way.  Now, just as there is a correspondence between pairs of Young
tableaux and permutations, there is a similar correspondence between
single Young tableaux and involutions (take the permutation
corresponding to the pair $(T,T)$). Furthermore, the following is
known (\cite{\KnuthIII}, exercise 5.1.4.4):

\proclaim{Lemma 3.3}
Let $\pi$ be an involution with $k$ fixed points.  Then the tableau
corresponding to $\pi$ has exactly $k$ columns of odd length.
\endproclaim

Thus a tableau with {\it no} odd columns corresponds to a permutation
with no fixed points.  Putting this together with the increasing
subsequence result used in theorem 1.1, we get:

\proclaim{Theorem 3.4}
$E_{O\in O(k)} (Tr(O)^n)$ is equal to the number of fixed-point-free
involutions of length $n$ with no increasing subsequence of length
greater than $k$.  Similarly, $E_{S\in Sp(2k)} (Tr(S)^n)$ is equal to
the number of fixed-point-free involutions of length $n$ with no {\it
decreasing} subsequence of length greater than $2k$.
\endproclaim

\demo{Proof}
The result for the orthogonal group follows easily from the
above.  For the symplectic case, it suffices to note that if one
transposes the tableaux being counted, one ends up counting tableaux
of height at most $2k$ where each column has even length.  But the
height of a tableaux gives the length of the longest decreasing
subsequence of the corresponding permutation, and, as already
established, tableaux with even-length columns correspond to
fixed-point-free involutions.  The desired result follows
immediately.
\qed\enddemo

\demo{Remark}
It should be noted that the above methods can also give combinatorial
interpretations of $E_{O(k)} (Tr(O^2)^n)$ and $E_{Sp(2k)}
(Tr(S^2)^n)$, given by replacing $n$ by $2n$ in theorem 3.4 and adding
the condition that the fixed-point-free involutions must also be
elements of the hyperoctahedral group, as embedded above.  However,
there is apparently no immediate extension to $E_{O(k)} (Tr(O^m)^n)$
and $E_{Sp(2k)} (Tr(S^m)^n)$.
\enddemo

\demo{Remark}
Again, \cite{\DS} give a formula for $E_{O\in O(k)} (p_\lambda(O))$ and
$E_{S\in Sp(2k)} (p_\lambda(S))$, for $k$ sufficiently large compared to
$|\lambda|$, using properties of the Brauer algebra; proofs of their
results along the above lines are given as theorems 6.2 and 6.4 of
\cite{\mythesis}.
\enddemo

\head
4. An alternate form
\endhead

One possible application of (\eqI) and its generalizations is
that it may be easier to get asymptotics for trace formulae on $U(n)$
than for the associated combinatorial quantities; one can write
explicit integrals for the trace formulae.  \cite{\Odlyzko} contains
preliminary work in an attempt to use a related formula to prove
asymptotic formulae for $f_{nk}$, which is a quantity of some interest
to combinatorialists.  They use the following formula (which they
derived independently):

\proclaim{Corollary 4.1}
$$
f_{nk}={2^{2n}(n!)^2\over (2\pi)^k k! (2n)!} I(n,k),
$$
where
$$
I(n,k)=\int^{\pi}_{-\pi}\ldots\int^{\pi}_{-\pi}
\left(\sum_{1\le j\le k} \cos(\theta_j)\right)^{2n} 
\prod_{1\le j\ne l\le k} \left|e^{i\theta_j}-e^{i\theta_l}\right|
d\theta_1 \ldots d\theta_k.
$$
\endproclaim

\demo{Proof}
Noting that the density of Haar measure on $U(k)$ in terms of the
$\theta_j$ is given by
$$
{1\over 2\pi}^k {1\over k!}
\prod_{1\le j\ne l\le k} \left|e^{i\theta_j}-e^{i\theta_l}\right|
$$
(see, for example, \cite{\Weyl}), we can immediately rewrite $I(n,k)$ as
an expectation over $U(k)$:
$$
I(n,k)=(2\pi)^k k!
E_{U\in U(k)} \left(\left(\sum_{1\le j\le k} \cos(\theta_j)\right)^{2n}\right).
$$
Writing
$$
\sum_{1\le j\le k} \cos(\theta_j)={1\over 2}\left(\sum_{1\le j\le k} (
e^{i\theta_j}+e^{-i\theta_j})\right),
$$
we get
$$
I(n,k) = {(2\pi)^k k!\over 2^{2n}}
E_{U\in U(k)}\left(\left(\Tr(U)+\overline{\Tr(U)}\right)^{2n}\right).
$$
We can expand this using the binomial theorem.  Since Haar measure on
$U(k)$ is invariant under change of phase, it follows that the only
term that contributes to the expectation is the
$\Tr(U)^n\overline{\Tr(U)^n}$ term; consequently, we have
$$
I(n,k)={(2\pi)^k k!\over 2^{2n}} {2n!\over n!^2} E_{U\in U(k)}
\left(\left|\Tr(U)^n\right|^2\right).
$$
The result follows immediately from theorem 1.1.
\qed\enddemo

\demo{Remarks}
(1) Zeilberger (personal communication) has reported a third
independent proof of corollary 4.1, using Schenstead's correspondence
and a variant of the hook formula.
(2) One can similarly rewrite the other trace formulae to use sums of
cosines in place of the traces; it is not entirely clear which form
would be more convenient for doing asymptotics.
\enddemo

Johansson has recently used this formula to give another proof that the
mean of the length of the longest increasing subsequence of a random
permutation of length $N$ is asymptotically $2\sqrt{N}$ \cite\Johansson.
He also has similar results for the quantities of theorem 2.2 (personal
communication), as well as heuristics for the variance.

It is also worth remarking that Regev (\cite{\Regev,\CohenRegev}) has
considered the asymptotics of $f_{nk}$ for $k$ fixed, as well as the
(combinatorial) quantities of theorem 3.4.  Regev finds that these
quantities (as well as a number of generalizations) are asymptotically
given by certain multiple integrals (which can then be explicitly
evaluated).  In the cases of particular interest to us, the resulting
multiple integrals turn out to be integrals appearing in the theory of
random matrices (related to the Gaussian matrix ensembles).  Consequently,
it should be possible to derive Regev's asymptotic formula for $f_{nk}$
from theorem 1.1, together with standard results from random matrix theory
relating the behavior of the eigenvalues of random unitary matrices to the
behavior of the eigenvalues of Gaussian Hermitian matrices \cite\Mehta.

\head Acknowledgements \endhead
The greatest thanks are due to P. Diaconis (the author's thesis
advisor), for his many suggestions of problems (one of
which appears in the present work).

Thanks are also due to the following people and institutions, in no
particular order: A. Odlyzko, for many helpful comments; AT\&T
Bell Laboratories (Murray Hill) and the Center for Communications
Research (Princeton) for generous summer support; the Harvard
University Mathematics Department and the National Science Foundation,
for generous support for the rest of the year.  Also, thanks are due,
for helpful comments, to N. Bergeron, M. Grassl, M. Rojas, R.
Stanley, and D. Stroock.  Last, but not least, the author owes thanks
to W. Woyczynski, both for introducing him to probability theory
and for introducing him to Prof. Diaconis; the thesis of which this
work is a part would be very different, had either introduction not
been made.

\Refs
\ref\no\AldousDiaconis
\by
Aldous, D. and Diaconis, P.
\paper
Hammersley's interacting particle process and longest increasing
subsequences
\jour
Prob. Th. and Rel. Fields
\vol 103
\yr 1995
\issue 2
\pages 199--213
\endref

\ref\no\BarbaschVogan
\by
Barbasch, D. and Vogan, D.
\paper
Primitive ideals and orbital integrals in complex classical groups
\jour
Math. Ann.
\vol 259
\yr 1982
\pages 153--199
\endref

\ref\no\CohenRegev
\by
Cohen, P. S. and Regev, A.
\paper
Asymptotics of combinatorial sums and the central limit theorem
\jour
SIAM J. Math. Anal.
\vol 19
\issue 5
\yr 1988
\pages 1204--1215
\endref

\ref\no\DS
\by
Diaconis, P. and Shahshahani, M.
\paper
On the Eigenvalues of Random Matrices
\jour
J. Appl. Prob.
\vol 31
\yr 1994
\pages 49--61
\endref

\ref\no\Hammersley
\by
Hammersley, J. M.
\paper
A few seedlings of research
\inbook
Proc. Sixth Berkeley Symp. Math. Statist. and Probability
\vol 1
\pages 345--394
\publ University of California Press
\publaddr Berkeley, Calif.
\yr 1972
\endref

\ref\no\Johansson
\by
Johansson, K.
\paper
The longest increasing subsequence in a random permutation and a unitary
random matrix model
\toappear
\endref

\ref\no\Kirillovetal
\by
Kirillov, A. N.,  Lascoux, A., Leclerc, B., and Thibon, J-Y.
\paper
S\'eries g\'en\'eratrices pour les tableaux de dominos
\jour
C. R. Acad. Sci. Paris S\'er. I Math.
\vol 318
\yr 1994
\issue 5
\pages 395--400
\endref

\ref\no\KnuthIII
\by
Knuth, D. E.
\book 
The Art of Computer Programming, {\rm vol. 3:}
Sorting and Searching
\bookinfo 2nd. ed.
\publ Addison Wesley
\publaddr Reading, Mass.
\yr 1973
\endref

\ref\no\Mehta
\by
Mehta, M. L.
\book Random Matrices
\bookinfo 2nd ed.
\publ Academic Press
\publaddr Boston, Mass.
\yr 1991
\endref

\ref\no\Odlyzko
\by
Odlyzko, A. M., Poonen, B., Widom, H. and Wilf, H. S.
\paper
On the distribution of longest increasing subsequences in random
permutations
\paperinfo in preparation
\endref

\ref\no\mythesis
\by
Rains, E. M.
\book Topics in Probability on Compact Lie Groups
\bookinfo Ph.D. thesis
\publ Harvard University
\publaddr Cambridge, Mass.
\yr 1995
\endref

\ref\no\Regev
\by
Regev, A.
\paper
Asymptotic values for degrees associated with strips of young diagrams
\jour
Adv. in Math.
\vol 41
\pages 115--136
\yr 1981
\endref

\ref\no\Sagan
\by
Sagan, B.
\book
The Symmetric Group: Representations, Combinatorial Algorithms, and
Symmetric Functions
\publ Wadsworth \& Brooks/Cole
\publaddr Pacific Grove, Calif.
\yr 1991
\endref

\ref\no\Schutzenberger
\by
Sch\"utzenberger, M. P.
\paper
Quelqes remarques sur une construction de Schensted
\jour Math. Scand.
\vol 12
\yr 1963
\pages 117--128
\endref

\ref\no\StantonWhite
\by
Stanton, D. W. and White, D. E.
\paper
A Schensted Algorithm for Rim Hook Tableaux
\jour J. Comb. Th., series A
\vol 40
\yr 1985
\pages 211--247
\endref

\ref\no\Weyl
\by
Weyl, H.
\book Classical Groups
\publ Princeton University Press
\publaddr Princeton, N.J.
\yr 1942
\endref

\ref\no\White
\by
White, D. E.
\paper
A Bijection Proving Orthogonality of the Characters of $S_n$
\jour Adv. in Math.
\vol 50
\yr 1983
\pages 160--186
\endref
\endRefs


\enddocument