ASYMPTOTICS OF THE NUMBER OF

k-WORDS WITH AN ℓ-DESCENT

Amitai Regev^{∗} Department of Mathematics The Pennsylvania State University University Park, PA 16802, U.S.A E-mail: regev@math.psu.edu

and Department of Theoretical Mathematics The Weizmann Institute of Science Rehovot 76100, Israel E-mail: regev@wisdom.weizmann.ac.il

Submitted: December , 1997; Accepted: February 25, 1998

Abstract. The number of words w = w_{1} ⋯ w_{n}, 1 ≤ w_{i} ≤ k, for which there are 1 ≤ i_{1} < ⋯ < i_{ℓ} ≤ n and w_{i_{1}} > ⋯ > w_{i_{ℓ}}, is given, by the Schensted-Knuth correspondence, in terms of standard and semi-standard Young tableaux. When n → ∞, the asymptotics of the number of such words is calculated.

Typeset by AMS-TEX

∗Work partially supported by N.S.F. Grant No. DMS-94-01197.

The Main Results.

Let k, n > 0 be integers and let W (k; n) = {w_{1} ⋯ w_{n} | 1 ≤ w_{i} ≤ k for all 1 ≤ i ≤ n} denote the set of words of length n on the alphabet {1, ⋯, k}. A word w = w_{1} ⋯ w_{n} ∈ W (k, n) is said to have a descent of length ℓ if there exist indices 1 ≤ i_{1} < ⋯ < i_{ℓ} ≤ n such that w_{i_{1}} > ⋯ > w_{i_{ℓ}} (trivially, such words exist if and only if ℓ ≤ k).

Let W (k, ℓ; n) denote the set of words in W (k; n) having descent ≤ ℓ, and denote w(k, ℓ; n) = |W (k, ℓ; 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} ≃_{n→∞} b_{n} (or simply a_{n} ≃ b_{n}) if lim_{n→∞} \frac{a_{n}}{b_{n}} = 1.

The main result here is

Theorem 1. Let 1 ≤ ℓ ≤ k, then

w(k, ℓ; n) ≃_{n→∞} \frac{1!2! ⋯ (ℓ − 1)!}{(k − ℓ)! ⋯ (k − 1)!} · (\frac{1}{ℓ})^{ℓ(k−ℓ)} · n^{ℓ(k−ℓ)} · ℓ^{n}

Remark. \frac{1!···(ℓ−1)!}{(k−ℓ)!···(k−1)!} = [\frac{k!!}{ℓ!!(k−ℓ)!!}]^{−1}, where m!! =^{def} 1!2! ⋯ (m − 1)!

Standard and Semistandard Tableaux.

Let λ ⊢ n (i.e. λ is a partition of n). A tableau of shape λ, filled with 1, ⋯, n, is standard if the numbers in it are increasing both in rows and in columns. Let d_{λ} denote the number of such tableaux. It is well known that d_{λ} = deg(χ_{λ}), where χ_{λ} is the corresponding irreducible character of the symmetric group S_{n}.

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

The numbers w(k, ℓ; n) are given by

Theorem 2. Let ∧_{ℓ}(n) = {(λ_{1}, λ_{2}, ⋯) ⊢ n | λ_{ℓ+1} = 0}. Then

w(k, ℓ; n) = ∑_{λ∈∧_{ℓ}(n)} s_{k}(λ) · d_{λ} .

Formulas for calculating d_{λ}’s and s_{k}(λ)’s are well known. Here we shall need the following formula:

Let λ = (λ_{1}, λ_{2}, ⋯). If λ_{k+1} > 0 then s_{k}(λ) = 0. Assume λ_{k+1} = 0. Then

s_{k}(λ) = [1!2! ⋯ (k − 1)!]^{−1} · ∏_{1≤i<j≤k}(λ_{i} − λ_{j} + j − i)  (∗)

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

The proof of Theorem 2:

Apply the Schensted-Knuth correspondence [K] to w ∈ W (k; n) : w → (P_{λ}, Q_{λ}), where P_{λ} and Q_{λ} are tableaux of same shape λ, Q_{λ} is standard and P_{λ} is k-semistandard. This gives a bijection

W (k; n) ↔ {(P_{λ}, Q_{λ}) | λ ∈ ∧_{k}(n), P_{λ} is k-semistandard, Q_{λ} is standard}.

Moreover, let w ↔ (P_{λ}, Q_{λ}) under this correspondence, then w has a descent of length ≥ r if and only if λ_{r} ≩ 0. It clearly follows that the Schensted-Knuth correspondence gives a bijection

W (k, ℓ; n) ↔ {(P_{λ}, Q_{λ}) | λ ∈ ∧_{ℓ}(n), P_{λ} is k-semistandard, Q_{λ} is standard}.

Hence

w(k, ℓ; n) = ∑_{λ∈Λ_{ℓ}(n)} s_{k}(λ)d_{λ}

Q.E.D.

Remark. Let 1 ≤ ℓ ≤ k and let λ ∈ ∧_{ℓ}(n), then it is easy to verify that (∗) implies that

s_{k}(λ) = a · b · c  (∗∗)

where a = [(k − ℓ)! ⋯ (k − 1)!]^{−1}, b = ∏_{1≤i≤ℓ} [ ∏_{ℓ+1≤j≤k}(λ_{i} + j − i)] and

c = ∏_{1≤i<j≤ℓ}(λ_{i} − λ_{j} + j − i).

The Proof of Theorem 1.

Here the results of [C.R] are applied. Let λ ∈ ∧_{ℓ}(n), 1 ≤ ℓ ≤ k, and write:

λ = (λ_{1}, ⋯, λ_{ℓ}) = (λ_{1}, ⋯, λ_{k}), where λ_{ℓ+1} = ⋯ = λ_{k} = 0.

Also write λ_{j} = \frac{n}{ℓ} + c_{j}\sqrt{n}. By the notations of [C.R], the factors b and c of (∗∗) satisfy

b ≈ ∏_{1≤i≤ℓ} (\frac{n}{ℓ})^{k−ℓ} = (\frac{n}{ℓ})^{ℓ(k−ℓ)}

and

c ≈ [ ∏_{1≤i<j≤ℓ}(c_{i} − c_{j})] (\sqrt{n})^{\frac{ℓ(ℓ−1)}{2}} .

Thus

s_{k}(λ) ≈ [(k − ℓ)! ⋯ (k − 1)!ℓ^{ℓ(k−ℓ)}]^{−1} · [ ∏_{1≤i<j≤ℓ}(c_{i} − c_{j})] · n^{ℓ(k−ℓ)+ \frac{ℓ(ℓ−1)}{4}} .

Apply now [C.R. Theorem 2] with β = 1 (also ℓ replacing k and s_{k}(λ) replacing f(λ)):

\begin{matrix}w(k, ℓ; n) =_{Thm 1} ∑_{λ∈∧_{ℓ}(n)} s_{k}(λ)d_{λ} ≃ \\ ≃ [(k − ℓ)! ⋯ (k − 1)! · ℓ^{ℓ(k−ℓ)}]^{−1} · (\frac{1}{\sqrt{2π}} )^{ℓ−1} · ℓ^{\frac{1}{2} ℓ^{2}} · n^{ℓ(k−ℓ)} · ℓ^{n} · I_{ℓ}, \end{matrix}  (∗ ∗ ∗)

where

I_{ℓ} = ∫ ⋯ ∫_{\begin{matrix}x_{1}+···+x_{ℓ}=0 \\ x_{1}≥···≥x_{ℓ} \end{matrix}} [ ∏_{1≤i<j≤ℓ}(x_{i} − x_{j})]^{2} exp (−\frac{ℓ}{2} ∑_{j=1}^{ℓ} x_{j}^{2}) d^{(ℓ−1)}x .

\underline{Special Case}: Let ℓ = k. Then w(k, k; n) = k^{n}. Cancelling k^{n} from both sides of (∗ ∗ ∗) implies that

I_{k} = [1!2! ⋯ (k − 1)!]\sqrt{2π}^{k−1} · (\frac{1}{k} )^{\frac{1}{2} k^{2}}

(Note: by [R, §4] I_{k} can also be calculated by the Mehta-Selberg integral).

In particular,

I_{ℓ} = [1!2! ⋯ (ℓ − 1)!]\sqrt{2π}^{ℓ−1} · (\frac{1}{ℓ})^{\frac{1}{2} ℓ^{2}} .

Substituting for I_{ℓ} in (∗ ∗ ∗) implies that

w(k, ℓ; n) ≃ \frac{1!2! ⋯ (ℓ − 1)!}{(k − ℓ)! ⋯ (k − 1)!} · (\frac{1}{ℓ})^{ℓ(k−ℓ)} · n^{ℓ(k−ℓ)} · ℓ^{n}

which completes the proof of Theorem 1. Q.E.D.

Acknowledgement. I am thankful to Dr. H. Wilf for suggesting this problem.

References

[C.R] P. S. Cohen, A. Regev, Asymptotics of combinatorial sums and the central limit theorem, SIAM J.

Math. Anal., Vol 19, No 5 (1980) 1204–1215.

[K] D. E. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, Mass., 1968.

[R] A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. in Math. 41 (1981), 115–136.