Asymptotics of the Number of $k$-words With An $\ell$-descent

Amitai Regev


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.

Full Text: PDF