\magnification=\magstep1
\input amstex
\documentstyle{amsppt}
\TagsOnRight
\hsize=6.5 truein
\vsize 9 true in


\font\eightrm = cmr8
\def\pf{\hfill Q.E.D.}
\def\c{\cite}
\def\fr{\frac}
\def\C{\Bbb C}
\def\deaf{\overset{\text{def}}\to{=}}

\topmatter
\title
Asymptotics of the Number of $k$-words With An $\ell$-descent
\ \ \ \  \\
\endtitle
\author
{\bf Amitai Regev}{$^*$}  \\
{\rm Department of Mathematics}  \\
{\rm The Pennsylvania State University}  \\
{\rm University Park, PA 16802, U.S.A } \\
{\it E-mail: regev\@math.psu.edu}\\
\ \ \\
{\rm and}
\ \ \\
{\rm Department of Theoretical Mathematics}  \\
{\rm The Weizmann Institute of Science } \\
{\rm Rehovot 76100, \ Israel } \\
{\it E-mail: regev\@wisdom.weizmann.ac.il} \\ \\
{\rm Submitted: December , 1997;~~Accepted: February 25, 1998}
\endauthor
\endtopmatter

\font\smcp=cmcsc8
\headline={\ifnum\pageno>1 {\smcp the electronic 
 journal of combinatorics 3 (1998),
  \#R15\hfill\folio} \fi}

\document

%\footnote"{}"{$^*${\rm Work partially supported by N.S.F. Grant 
%No. DMS-94-01197.}}

\vbox{\vskip 0.5in}

\baselineskip 13pt


{\leftskip 60pt\rightskip 60pt
{{\bf Abstract}. \rm The number of words $w = w_1\cdots w_n$, 
$1 \leq w_i \leq k$, for which there are $1 \leq i_1 < \cdots
< i_{\ell} \leq n$ and $w_{i_1} > \cdots > w_{i_{\ell}}$, is
given, by the Schensted-Knuth correspondence, in terms of
standard and semi-standard Young tableaux.  When $n \to \infty$,
the asymptotics of the number of such words is calculated.\par}}

\par\vfill\noindent
\def\hl{\leaders \hrule height 3pt depth -2.5pt\hfill}
{\hbox to 100pt{\hl}}\par
{\eightrm $^*${Work partially supported by N.S.F. Grant 
No. DMS-94-01197.}}

\newpage

\baselineskip 15pt

\subhead
The Main Results
\endsubhead

Let $k,n > 0$ be integers and let $W(k;n) = \big\{w_1\cdots
w_n\;\big|\; 1 \leq w_i \leq k$ for all $1 \leq i \leq n\big\}$ denote
the set of words of length $n$ on the alphabet $\{1,\cdots,k\}$.  A
word $w = w_1 \cdots w_n \in W(k,n)$ is said to have a descent of
length $\ell$ if there exist indices $1 \leq i_1 < \cdots < i_{\ell}
\leq n$ such that $w_{i_1} > \cdots > w_{i_{\ell}}$ (trivially, such
words exist if and only if $\ell \leq k$).

Let $W(k,\ell;n)$ denote the set of words in $W(k;n)$ having
descent $\leq \ell$, and denote $w(k,\ell;n) = |W(k,\ell;n)|$.
Thus $W(k;n) = W(k,k;n)$, and $w(k,k;n) = k^n$.

Recall: given two sequences $\{a_n\}$ and $\{b_n\}$ of real numbers,
we denote $a_n \underset{n\rightarrow\infty}\to\simeq b_n$ (or simply
$a_n \simeq b_n$) if $\displaystyle{\lim_{n\rightarrow\infty}}
\fr{a_n}{b_n} = 1$.

The main result here is

\proclaim
{Theorem 1}  Let $1 \leq \ell \leq k$, then 
$$
	w(k,\ell;n)\underset{n\rightarrow \infty}\to\simeq
	\fr{1!2!\cdots (\ell - 1)!}{(k - \ell)!\cdots (k - 1)!}
	\cdot \left(\fr1{\ell}\right)^{\ell(k-\ell)} \cdot 
	n^{\ell(k - \ell)} \cdot \ell^n
$$
\endproclaim

\remark
{Remark}  $\fr{1! \cdots (\ell - 1)!}{(k - \ell)! \cdots (k - 1)!}
= \left[ \fr{k!!}{\ell!!(k - \ell)!!}\right]^{-1}$, where $m!!\deaf
1!2!\cdots (m - 1)!$
\endremark

\demo
{\it Standard and Semistandard Tableaux}
\enddemo

Let $\lambda \vdash n$ (i.e. $\lambda$ is a partition of $n$).
A tableau of shape $\lambda$, filled with $1,\cdots,n$, is 
standard if the numbers in it are increasing both in rows and
in columns.  Let $d_{\lambda}$ denote the number of such tableaux.
It is well known that $d_{\lambda} = \deg(\chi_{\lambda})$, where
$\chi_{\lambda}$ is the corresponding irreducible character of
the symmetric group $S_n$.

A $k$-tableau of shape $\lambda$ is a tableau filled with $1,\cdots,k$
possibly with repetitions; it is semi-standard if the numbers are
weakly increasing in rows and strictly increasing in columns.  Let
$s_k(\lambda)$ denote the number of such $k$-tableaux.  It is well
known that $s_k(\lambda)$ is the degree of a corresponding irreducible
character of $GL(k,\C)$ (or of $SL(k,\C)$).

The numbers $w(k,\ell;n)$ are given by 

\proclaim
{Theorem 2}  Let $\wedge_{\ell}(n) = \left\{(\lambda_1,\lambda_2,\cdots)
\vdash n\;\big|\; \lambda_{\ell + 1} = 0\right\}$.  Then
$$
	w(k,\ell;n) = \sum_{\lambda \in \wedge_{\ell}(n)}
	s_k(\lambda) \cdot d_{\lambda}\,.
$$
\endproclaim

{\it Formulas} for calculating $d_{\lambda}$'s and $s_k(\lambda)$'s
are well known.  Here we shall need the following formula:

Let $\lambda = (\lambda_1,\lambda_2,\cdots)$.  If $\lambda_{k+1} > 0$
then $s_k(\lambda) = 0$.  Assume $\lambda_{k+1} = 0$.  Then
$$
	s_k(\lambda) = [1!2!\cdots (k-1)!]^{-1}\cdot 
	\prod_{1\leq i < j \leq k} (\lambda_i - \lambda_j + j - i)
\tag"{($*$)}"
$$	

We turn now to the proofs of Theorems 1 and 2, starting with

{\bf The proof of Theorem 2}:  

Apply the Schensted-Knuth correspondence \c{K} to $w \in W(k;n):w
\to (P_{\lambda},Q_{\lambda})$, where $P_{\lambda}$ and $Q_{\lambda}$
are tableaux of same shape $\lambda$, $Q_{\lambda}$ is standard and
$P_{\lambda}$ is $k$-semistandard.  This gives a bijection
$$
	W(k;n) \leftrightarrow \{(P_{\lambda},Q_{\lambda})\;\big|\;
	\lambda \in \wedge_k(n),\;P_{\lambda} \text{ is } k
	\text{-semistandard}, \; Q_{\lambda}\text{ is standard}\}.
$$
Moreover, let $w \leftrightarrow (P_{\lambda},Q_{\lambda})$ under
this correspondence, then $w$ has a descent of length $\geq r$ if
and only if $\lambda_r \gneqq 0$.  It clearly follows that the
Schensted-Knuth correspondence gives a bijection 
$$
	W(k,\ell;n) \leftrightarrow \{(P_{\lambda},Q_{\lambda})\;\big|\;
	\lambda \in \wedge_{\ell}(n),\;P_{\lambda} \text{ is } k
	\text{-semistandard}, \; Q_{\lambda}\text{ is standard}\}.
$$
Hence
$$
	w(k,\ell;n) = \sum_{\lambda \in \Lambda_{\ell}(n)}
	s_k(\lambda) d_{\lambda}
$$
\pf

\remark
{Remark}  Let $1 \leq \ell \leq k$ and let $\lambda \in \wedge_{\ell}(n)$,
then it is easy to verify that ($*$) implies that 
$$
	s_k(\lambda) = a \cdot b\cdot c 
\tag"{($**$)}"
$$
where $a = [(k - \ell)! \cdots (k - 1)!]^{-1}$, 
$b = \displaystyle{\prod_{1 \leq i \leq \ell}} \left[
\displaystyle{\prod_{\ell + 1 \leq j \leq k}} (\lambda_i + j - i)\right]$
and \newline
$c = \displaystyle{\prod_{1 \leq i < j \leq \ell}}
(\lambda_i - \lambda_j + j - i)$.
\endremark

\subhead
The Proof of Theorem 1
\endsubhead

Here the results of \c{C.R} are applied.  Let $\lambda \in
\wedge_{\ell}(n)$, $1 \leq \ell \leq k$, and write:
$$
	\lambda = (\lambda_1,\cdots,\lambda_{\ell}) = (\lambda_1,
	\cdots,\lambda_k), \text{ where } \lambda_{\ell+1} =
	\cdots = \lambda_k = 0.
$$
Also write $\lambda_j = \fr{n}{\ell} + c_j \sqrt{n}$.  By the
notations of \c{C.R}, the factors $b$ and $c$ of ($**$)
satisfy
$$
	b \approx \prod_{1 \leq i \leq \ell}\left(\fr{n}{\ell}\right)^{k-\ell}
	=\left(\fr{n}{\ell}\right)^{\ell(k-\ell)}
$$
and 
$$
	c \approx \left[\prod_{1 \leq i < j \leq \ell}
	(c_i - c_j)\right] (\sqrt{n})^{\fr{\ell(\ell - 1)}{2}}.
$$
Thus
$$
	s_k(\lambda) \approx [(k - \ell)! \cdots 
	(k - 1)!\ell^{\ell(k - \ell)}]^{-1} \cdot \left[
	\prod_{1 \leq i < j \leq \ell} (c_i - c_j) \right] 
	\cdot n^{\ell(k - \ell) 
	+ \fr{\ell(\ell - 1)}{4}}\;.
$$

Apply now \c{C.R. Theorem 2} with $\beta = 1$ (also $\ell$
replacing $k$ and $s_k(\lambda)$ replacing $f(\lambda)$):
$$
\aligned
	& w(k,\ell;n) \underset{\text{Thm 1}}\to{=} 
	\sum_{\lambda\in\wedge_{\ell}(n)} s_k(\lambda) d_{\lambda}
	\simeq   \\
	& \simeq [(k - \ell)! \cdots (k - 1)! \cdot \ell^{\ell(k - \ell)}]^{-1}
	\cdot \left( \fr1{\sqrt{2\pi}} \right)^{\ell - 1}\cdot
	\ell^{\fr12 \ell^2} \cdot n^{\ell(k - \ell)} \cdot \ell^n
	\cdot I_{\ell}, 
\endaligned
\tag"{($***$)}"
$$
where
$$
	I_{\ell} = \underset{\Sb x _1 + \cdots + x_{\ell}=0
	\\ x_1 \geq \cdots \geq x_{\ell}\endSb}\to{\int \cdots \int} 
	\left[ \prod_{1 \leq i < j \leq \ell} (x_i - x_j)\right]^2
	\exp \left( - \fr{\ell}{2} \sum_{j=1}^{\ell} x_j^2\right)
	d^{(\ell - 1)} x\,.
$$

\underbar{\bf Special Case}:  Let $\ell = k$.  Then $w(k,k;n) = k^n$.
Cancelling $k^n$ from both sides of $(***)$ implies that
$$
	I_k = [1!2! \cdots(k - 1)!] \sqrt{2\pi}^{k-1} \cdot
	\left(\fr1{k}\right)^{\fr12 k^2}
$$
(Note: \ by \c{R, $\S4$} $I_k$ can also be calculated by the
Mehta-Selberg integral).

In particular,
$$
	I_{\ell} = [1!2!\cdots (\ell - 1)!] \sqrt{2\pi}^{\ell-1}
	\cdot \left(\fr1{\ell}\right)^{\fr12 \ell^2}\,.
$$
Substituting for $I_{\ell}$ in $(***)$ implies that
$$
	w(k,\ell;n) \simeq \fr{1!2!\cdots(\ell - 1)!}{(k - \ell)!\cdots
	(k - 1)!}\; \cdot\; \left(\fr1{\ell}\right)^{\ell(k - \ell)}
	\;\cdot\; n^{\ell(k - \ell)} \cdot \ell^n
$$
which completes the proof of Theorem 1.
\pf

\subhead
{Acknowledgement}
\endsubhead
I am thankful to Dr. H. Wilf for suggesting this problem.


\Refs

\widestnumber\key{C.R}

\ref
  \key C.R
  \by P. S. Cohen, A. Regev
  \paper Asymptotics of combinatorial sums and the central limit
	theorem
  \jour SIAM J. Math. Anal.
  \finalinfo Vol 19, No 5	(1980) 1204--1215
\endref

\ref
  \key K
  \by D. E. Knuth
  \paper The Art of Computer Programming
  \finalinfo Vol. 3, Addison-Wesley, Reading, Mass., 1968
\endref

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

\endRefs

\enddocument