On Longest Increasing Subsequences in Words in Which All Multiplicities are Equal

Ferenc Balogh Department of Mathematics John Abbott College 21275 Lakeshore Road Sainte-Anne-de-Bellevue, PQ H9X 3L9 Canada

            ferenc.balogh@johnabbott.qc.ca

Abstract

Gessel’s famous Bessel determinant formula gives the generating function of the number of permutations without increasing subsequences of a given length. Ekhad and Zeilberger proposed the challenge of finding a suitable generalization for permutations of multisets in which all multiplicities are equal, that is, to count words of length rn from an alphabet consisting of n letters in which each letter appears exactly r times and which have no increasing subsequences of length d.

In this paper we present such a generating function expressible as a multiple integral of the product of a Gessel-type Toeplitz determinant with the exponentiated cycle index polynomial of the symmetric group on r elements.

1 Introduction and statement of results

For positive integers n, d, and r, let A_{d,r}(n) denote the number of words from the alphabet {1, 2, …, n} of length rn such that

• each letter appears exactly r times,

• there are no (strictly) increasing subsequences of length d.

For example, out of the \frac{6!}{2!2!2!} = 90 words from the alphabet \{1, 2, 3\} in which each letter has multiplicity 2, there are 43 words with no increasing subsequences of length 3 (shown highlighted in Table 1).

The goal of this paper is to find generating functions for the numbers (A_{d,r}(n))_{n≥0}, with d and r fixed.

Note that the special case r = 1 (each letter appears only once) corresponds to the problem of determining the length of the longest increasing subsequence of a random permutation. For a detailed history of this problem and its many beautiful connections with representation theory, analysis, and probability theory, see Romik’s book [17].

Our starting point is the following observation by Ekhad and Zeilberger [7]: the Robinson-Schensted-Knuth (RSK) correspondence [18] implies that A_{d+1,r}(n) can be written as a sum over partitions λ of weight |λ| equal to rn and of length ℓ(λ) at most d in the following form:

A_{d+1,r}(n) = ∑_{\begin{matrix}|λ|=rn \\ ℓ(λ)≤d \end{matrix}} f_{λ}g_{λ}^{(r)},  (1)

where f_{λ} is the number of standard Young tableaux of shape λ, and g_{λ}^{(r)} is the number of semi-standard Young tableaux of shape λ whose content is 1^{r}2^{r} ⋯ n^{r}. Note that the original formula of Ekhad and Zeilberger [7] had a misprint that was found and corrected by Chapuy [5].

For r = 1 the quantity g_{λ}^{(1)} reduces to f_{λ} and hence

A_{d+1,1}(n) = ∑_{\begin{matrix}|λ|=n \\ ℓ(λ)≤d \end{matrix}} f_{λ}^{2}.  (2)

Gessel [9] found the following remarkable generating function for the sequence (A_{d+1,1}(n))_{n≥0}:

∑_{n=0}^{∞} \frac{A_{d+1,1}(n)}{(n!)^{2}}x^{2n} = det(G_{d}(x)),  (3)

where G_{d}(x) is the d × d Toeplitz matrix

(G_{d}(x))_{ij} = I_{|i−j|}(2x), 1 ≤ i, j ≤ d,  (4)

and the entries I_{m}(u) are modified Bessel functions with integer parameters. The functions I_{m}(u) are given by the generating function [16, Eq. 10.35.1].

∑_{m=−∞}^{∞} I_{m}(u)z^{m} = exp (\frac{u}{2} (\frac{1}{z} + z)) .  (5)

1 1 2 2 3 3  1 1 2 3 2 3  1 1 2 3 3 2  1 1 3 2 2 3  1 1 3 2 3 2  1 1 3 3 2 2  1 2 1 2 3 3  1 2 1 3 2 3  1 2 1 3 3 2  1 2 2 1 3 3
1 2 2 3 1 3  1 2 2 3 3 1  1 2 3 1 2 3  1 2 3 1 3 2  1 2 3 2 1 3  1 2 3 2 3 1  1 2 3 3 1 2  1 2 3 3 2 1  1 3 1 2 2 3  1 3 1 2 3 2
1 3 1 3 2 2  1 3 2 1 2 3  1 3 2 1 3 2  1 3 2 2 1 3  1 3 2 2 3 1  1 3 2 3 1 2  1 3 2 3 2 1  1 3 3 1 2 2  1 3 3 2 1 2  1 3 3 2 2 1
2 1 1 2 3 3  2 1 1 3 2 3  2 1 1 3 3 2  2 1 2 1 3 3  2 1 2 3 1 3  2 1 2 3 3 1  2 1 3 1 2 3  2 1 3 1 3 2  2 1 3 2 1 3  2 1 3 2 3 1
2 1 3 3 1 2  2 1 3 3 2 1  2 2 1 1 3 3  2 2 1 3 1 3  2 2 1 3 3 1  2 2 3 1 1 3  2 2 3 1 3 1  2 2 3 3 1 1  2 3 1 1 2 3  2 3 1 1 3 2
2 3 1 2 1 3  2 3 1 2 3 1  2 3 1 3 1 2  2 3 1 3 2 1  2 3 2 1 1 3  2 3 2 1 3 1  2 3 2 3 1 1  2 3 3 1 1 2  2 3 3 1 2 1  2 3 3 2 1 1
3 1 1 2 2 3  3 1 1 2 3 2  3 1 1 3 2 2  3 1 2 1 2 3  3 1 2 1 3 2  3 1 2 2 1 3  3 1 2 2 3 1  3 1 2 3 1 2  3 1 2 3 2 1  3 1 3 1 2 2
3 1 3 2 1 2  3 1 3 2 2 1  3 2 1 1 2 3  3 2 1 1 3 2  3 2 1 2 1 3  3 2 1 2 3 1  3 2 1 3 1 2  3 2 1 3 2 1  3 2 2 1 1 3  3 2 2 1 3 1
3 2 2 3 1 1  3 2 3 1 1 2  3 2 3 1 2 1  3 2 3 2 1 1  3 3 1 1 2 2  3 3 1 2 1 2  3 3 1 2 2 1  3 3 2 1 1 2  3 3 2 1 2 1  3 3 2 2 1 1

Table 1: This 10 × 9 lexicographic array lists the words from the alphabet {1, 2, 3} with all multiplicities equal to 2. The highlighted words have no increasing subsequences of length 3, there are A_{3,2}(3) = 43 of them.

The determinant formula (3) played a crucial role in the subsequent developments of the asymptotic analysis of large permutations, most notably it lead to the famous Baik–Deift– Johansson theorem [2]. There are many related results for increasing subsequences of words (also referred to as permutations of multisets) [1, 3, 4, 10, 11, 15, 19].

Ekhad and Zeilberger [7] proposed the challenge to generalize (3) for multiple occurrences r > 1. This goal is fully accomplished in the main result of this paper.

For the sake of comparison with the general formulae to be presented, one can write Gessel’s generating function (3) in a slightly different Toeplitz determinant form:

∑_{n=0}^{∞} \frac{A_{d+1,1}(n)}{(n!)^{2}}(v\overline{v})^{n} = det(G̃_{d}(x)),  (6)

where

(G̃_{d}(x))_{ij} = φ_{i−j}(v, v̄), 1 ≤ i, j ≤ d,  (7)

and the entries φ_{m}(v, v̄) are the Laurent series coefficients at z = 0 of the formal Toeplitz symbol

φ(v, v̄; z) = ∑_{m=−∞}^{∞} φ_{m}(v, v̄)z^{m} = exp (\frac{v}{z} + \overline{v}z) .  (8)

The variables v and \overline{v} above are complex-valued bookkeeping indeterminates. Following common practice in complex variables, v and \overline{v} are treated as independent variables, and \overline{v} is not identified by the complex conjugate of v by default. Whenever the context dictates that we make \overline{v} equal to the complex conjugate of v, this will be stated explicitly.

The Laurent series coefficients φ_{m}(v, \overline{v}) in (8) are well-defined: by splitting the exponent of the right hand side of (8) into positive and negative parts, taking the exponentials separately, and collecting the z terms results in a meaningful formal power series in v and \overline{v}:

φ_{m}(v, \overline{v}) = [z^{m}] exp (\frac{v}{z} ) exp (\overline{v}z) = [z^{m}] ∑_{k,l=0}^{∞} \frac{v^{k}\overline{v}^{l}z^{l−k}}{k!l!} = \begin{cases}∑_{j=0}^{∞} \frac{v^{j}\overline{v}^{j+m}}{j!(j + m)!}, & if m > 0; \\ ∑_{j=0}^{∞} \frac{v^{j}\overline{v}^{j}}{(j!)^{2}} , & if m = 0; \\ ∑_{j=0}^{∞} \frac{v^{j−m}\overline{v}^{j}}{(j − m)!j!}, & if m < 0. \end{cases} (9)

It is easy to see that φ_{m}(x, x) = I_{|m|}(2x), and therefore (6) reduces to (3) with v = \overline{v} = x.

Before stating the main result, recall that the cycle index polynomial of the symmetric group S_{r} is the multivariate polynomial

Cyc_{r}(t_{1}, …, t_{r}) = \frac{1}{r!} ∑_{|μ|=r} |C_{μ}| ∏_{i=1}^{ℓ(μ)} t_{μ_{i}}  (10)

in the indeterminates t_{1}, …, t_{r}, where the sum is over partitions μ of weight |μ| = r, C_{μ} ⊂ S_{r} is the conjugacy class consisting of permutations of cycle type μ and ℓ(μ) stands for the length (number of parts) of the partition μ. For example, for r = 1, 2, 3 the cycle index polynomials are

Cyc_{1}(t_{1}) = t_{1},
Cyc_{2}(t_{1}, t_{2}) = \frac{1}{2} (t_{1}^{2} + t_{2}) ,
Cyc_{3}(t_{1}, t_{2}, t_{3}) = \frac{1}{6} (t_{1}^{3} + 3t_{1}^{2}t_{2} + 2t_{3}) .  (11)

Note that the cycle index polynomial Cyc_{r} is a weighted homogeneous polynomial of degree r in the natural grading deg(t_{j}) = j. In what follows, we use the abbreviated notation t = (t_{1}, t_{2}, …).

Theorem 1. The sequence (A_{d+1,r}(n))_{n≥0} has the formal series generating function

∑_{n=0}^{∞} \frac{A_{d+1,r}(n)}{(rn)!n!}(v\overline{v})^{rn} = \frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} det(T_{d}(v, t)) · exp (v̄^{r}\overline{Cyc_{r}(t)}) ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j}), (12)

where T_{d}(v, t) is the Toeplitz matrix

(T_{d}(v, t))_{ij} = φ_{i−j}(v, t), 1 ≤ i, j ≤ d,  (13)

associated with the formal Toeplitz symbol

φ(v, t; z) = ∑_{m=−∞}^{∞} φ_{m}(v, t)z^{m} = exp (\frac{v}{z} + ∑_{j=1}^{r} t_{j}z^{j}) ,  (14)

and dA stands for the area measure in the complex plane.

Remark 2. In terms of the independent bookkeeping variables v and v̄, the Toeplitz determinant det(T_{d}(v, t)) and the exponentiated cycle index polynomial exp (\overline{v}^{r}\overline{Cyc_{r}(t)}) can both be expanded into formal power series, and the coefficients of the resulting product series

det(T_{d}(v, t)) exp (\overline{v}^{r}\overline{Cyc_{r}(t)}) = ∑_{k,l=0}^{∞} F_{k}(t)\overline{G_{l}(t)}v^{k}v̄^{l}

are products of weighted homogeneous polynomials in t and \overline{t} and therefore their integrals with respect to multiple planar Gaussian measures in (12) are well-defined.

Remark 3. I am grateful to M. Bertola for the following observation:

\frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} t_{1}^{k_{1}} ⋯ t_{r}^{k_{r}} · \overline{t_{1}^{l_{1}} ⋯ t_{r}^{l_{r}}} ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j}) = ∏_{j=1}^{r} δ_{k_{j}l_{j}}k_{j}!

= ⟨t_{1}^{k_{1}} ⋯ t_{r}^{k_{r}}, t_{1}^{l_{1}} ⋯ t_{r}^{l_{r}}⟩,  (15)

where ⟨·, ·⟩ is Macdonald’s scalar product on symmetric functions [13, Eq. (4.7)], written in terms of the normalized power sum variables t_{i} = p_{i}/i. Therefore we can rephrase (12) as

∑_{n=0}^{∞} \frac{A_{d+1,r}(n)}{(rn)!n!}(v\overline{v})^{rn} = ⟨det(T_{d}(v, t)), exp (v̄^{r} Cyc_{r}(t))⟩ .  (16)

Remark 4. The last integral with respect to t_{r} in (12) can be replaced by the direct evaluation

t̄_{r} = \frac{v̄^{r}}{r} .  (17)

This follows from the integral identity

\frac{1}{π} ∫_{ℂ} P (t_{r}) exp (\frac{v̄^{r}}{r} t̄_{r} − |t_{r}|^{2}) dA(t_{r}) = P (\frac{v̄^{r}}{r} ) ,  (18)

valid for all polynomials P (t). The 1/r factor in (17) comes from

[t_{r}] Cyc_{r}(t) = \frac{1}{r!} |C_{(r)}| = \frac{(r − 1)!}{r!} = \frac{1}{r}.  (19)

In particular, the generating function (12) for r = 1 reduces to Gessel’s Toeplitz determinant formula (6) in terms of Bessel functions.

Remark 5. For the case of double occurrences r = 2, there is a quadrature identity

\frac{1}{π^{2}} ∫_{ℂ} ∫_{ℂ} Q(t_{1}, t_{2})e^{\frac{v̄^{2}}{2} (t̄_{1}^{2}+t̄_{2})−|t_{1}|^{2}−|t_{2}|^{2}}dA(t_{1})dA(t_{2}) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} Q (v̄x, \frac{v̄^{2}}{2} ) e^{− \frac{x^{2}}{2}} dx (20)

for polynomials Q(t_{1}, t_{2}), assuming that |v̄^{2}/2| < 1. Therefore, for r = 2 our general formula (12) reduces to

∑_{n=0}^{∞} \frac{A_{d+1,2}(n)}{(2n)!n!}(v\overline{v})^{2n} = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} det(T̂_{d}(v, \overline{v}, x))e^{− \frac{x^{2}}{2}} dx,  (21)

where T̂_{d}(v, \overline{v}, t) is the d × d Toeplitz determinant associated with the symbol

φ(v, v̄, x; z) = exp (\frac{v}{z} + v̄xz + \frac{v̄^{2}}{2} z^{2}) .  (22)

By setting v̄ = 1 one can further simplify (21) to the integral involving the Toeplitz determinant of the simplified symbol

φ(v, x; z) = exp (\frac{v}{z} + xz + \frac{1}{2}z^{2}) .  (23)

Remark 6. The numbers (A_{d+1,r}(n))_{n≥0} can be given a natural probabilistic interpretation described as follows. Consider the uniform measure on the set of words of length rn in n letters with each letter appearing exactly r times, and let L_{n,r}(w) denote the length of the longest increasing subsequence in a random word w, interpreted itself as a random variable. By the definition of A_{d+1,r}(n) we have

Prob (L_{n,r}(w) ≤ d) = \frac{A_{d+1,r}(n)}{\frac{(rn)!}{(r!)^{n}}},  (24)

and hence a slightly adapted version of (12) can be interpreted as the “Poissonization” of the distributions of L_{n,r}:

e^{− \frac{|v|^{2r}}{r!}} ∑_{n=0}^{∞} Prob (L_{n,r}(w) ≤ d) \frac{1}{n!} (\frac{|v|^{2r}}{r!} )^{n}

= \frac{e^{− \frac{|v|^{2r}}{r!}}}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} det(T_{d}(v, t)) · exp (v̄^{r}\overline{Cyc_{r}(t)}) ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j}). (25)

Note that it is natural here to identify \overline{v} with the complex conjugate of v in (25).

In this probabilistic context, the formula (25) may turn out to be useful in a subsequent asymptotic analysis of the probabilities Prob (L_{n,r}(w) ≤ d) as n → ∞ and d → ∞ simultaneously, possibly via the Toeplitz–Fredholm techniques of Borodin, Okounkov, and Olshanski [4], combined with Johansson’s de-Poissonization lemma [12].

1.1 Outline

In Sec. 2 an integral representation of g_{λ}^{(r)} is given in terms of the Schur polynomial s_{λ} associated with the partition λ, which in turn leads to an integral formula for A_{d+1,r}(n). Gessel’s general Toeplitz determinant for length-restricted Cauchy–Littlewood-type sums over partitions is recalled in Sec. 3 and it is employed to complete the proof of Theorem 1. In Sec. 4 we illustrate how the abstract generating function can be used in practice to calculate A_{d+1,r}(n) for small values of d, r, and n by using standard symbolic computer algebra software.

2 The Kostka coefficients g_{λ}^{(r)} as integrals of Schur polynomials

Following the standard approach in the theory of symmetric functions [13], one defines the Schur polynomials s_{λ} ∈ ℂ[t_{1}, t_{2}, t_{3}, …] in the normalized power sum variables t = (t_{1}, t_{2}, …) via the Jacobi-Trudi formula

s_{λ}(t) = det (h_{λ_{i}−i+j}(t))_{1≤i,j≤ℓ(λ)} ,  (26)

where the polynomials h_{k}(t) (the complete symmetric polynomials) are obtained from the generating function

∑_{k=0}^{∞} h_{k}(t)z^{k} = exp (∑_{j=1}^{∞} t_{j}z^{j}) ,  (27)

with h_{k}(t) = 0 for negative values of k. The polynomial h_{k}(t) is a weighted homogeneous polynomial of degree k in the natural grading deg(t_{j}) = j. Therefore s_{λ}(t) is also a weighted homogeneous polynomial of degree |λ| and hence it has the scaling property

s_{λ} (at_{1}, a^{2}t_{2}, a^{3}t_{3}, …) = a^{|λ|}s_{λ}(t_{1}, t_{2}, t_{3}, …).  (28)

It is well-known [13] that the number of standard Young tableaux of shape λ is given by the special evaluation

f_{λ} = |λ|!s_{λ} (1, 0, 0, …) .  (29)

As pointed out by Chapuy [5], the coefficient g_{λ}^{(r)} is the Kostka number K_{λ,(r^{n})} associated with the pair of partitions λ and (r^{n}), that is, g_{λ}^{(r)} is the coefficient of m_{(r^{n})} in the expansion of s_{λ} in the monomial symmetric function basis (m_{μ})_{μ} of ℂ[t]:

g_{λ}^{(r)} = [x_{1}^{r}x_{2}^{r} ⋯ x_{n}^{r}] s_{λ}(t_{1}(x), t_{2}(x), …),  (30)

where

t_{j}(x) = \frac{1}{j} ∑_{i=1}^{n} x_{i}^{j}  j = 1, 2, …  (31)

are the normalized power sum symmetric polynomials in the variables x_{1}, …, x_{n}.

In what follows, the coefficient representation (30) of g_{λ}^{(r)} will be rewritten as an r-fold integral of the Schur polynomial associated with λ in terms of the normalized power sum variables. To proceed in this direction we need the following basic but important

Proposition 7. Let P (t_{1}, t_{2}, …, t_{r}) be a polynomial in the indeterminates t_{1}, …, t_{r} and consider the polynomial

P (t_{1}(x), t_{2}(x), …, t_{r}(x)) ∈ ℂ[x_{1}, …, x_{n}]  (32)

in the indeterminates x_{1}, …, x_{n}, where t_{k}(x) are the normalized power sum symmetric polynomials (31) in x. The following integral identity holds:

[x_{1}^{r}x_{2}^{r} ⋯ x_{n}^{r}]P (t_{1}(x), t_{2}(x), …, t_{r}(x))

= \frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} P (u_{1}, …, u_{r})\overline{h_{r} (u_{1}, \frac{u_{2}}{2} , …, \frac{u_{r}}{r} , 0, 0, …)}^{n} ∏_{j=1}^{r} e^{−|u_{j}|^{2}}dA(u_{j}), (33)

where h_{r} (u_{1}, \frac{u_{2}}{2} , …, \frac{u_{r}}{r} , 0, 0, …) is the complete symmetric polynomial of degree r evaluated at (u_{1}, \frac{u_{2}}{2} , …, \frac{u_{r}}{r} , 0, 0, …) and dA is the area measure in the complex plane.

Remark 8. Chapuy [5] found a multiple integral formula for g_{λ}^{(r)} involving h_{r}^{n}, expressed in terms of the original indeterminates x_{j}. Our identity (33), expressed in terms of the normalized power sum symmetric polynomials t_{k}(x), has essentially the same combinatorial content. However, as it will be shown below, our choice of parametrization turns out to be more advantageous in finding a generating function for the numbers A_{d+1,r}(n).

Remark 9. The symmetric function h_{r}^{n} appears in a closely related problem on the enumeration of a certain class of integer matrices: Everett and Stein [8] cite the following “classical result” attributed to MacMahon [14]: the number of n×n matrices with non-negative integer entries whose row and column sums are all equal to r is given by the coefficient of m_{(r^{n})} in the expansion of h_{r}^{n} in the monomial symmetric function basis.

Proof of Lemma 7. For r-tuples of non-negative integers (k_{1}, k_{2}, …, k_{r}), let

a_{k_{1},...,k_{r}}^{n,r} = [x_{1}^{r}x_{2}^{r} ⋯ x_{n}^{r}]t_{1}(x)^{k_{1}} ⋯ t_{r}(x)^{k_{r}}.  (34)

The exponential generating function of the numbers a_{k_{1},...,k_{r}}^{n,r} can be calculated as follows:

∑_{k_{1},...,k_{r}=0}^{∞} a_{k_{1},...,k_{r}}^{n,r} ∏_{j=1}^{r} \frac{u_{j}^{k_{j}}}{k_{j}!} = [x_{1}^{r}x_{2}^{r} ⋯ x_{n}^{r}] ∑_{k_{1},...,k_{r}=0}^{∞} ∏_{j=1}^{r} \frac{(t_{j}(x)u_{j})^{k_{j}}}{k_{j}!}

= [x_{1}^{r}x_{2}^{r} ⋯ x_{n}^{r}] exp (∑_{j=1}^{r} t_{j}(x)u_{j})

= [x_{1}^{r}x_{2}^{r} ⋯ x_{n}^{r}] ∏_{i=1}^{n} exp (∑_{j=1}^{r} \frac{x_{i}^{j}}{j} u_{j})

= ∏_{i=1}^{n}[x_{i}^{r}] exp (∑_{j=1}^{r} \frac{x_{i}^{j}}{j} u_{j})

= (h_{r} (u_{1}, \frac{u_{2}}{2} , …, \frac{u_{r}}{r} , 0, 0, …))^{n} .  (35)

Since

\frac{1}{π} ∫_{ℂ} z^{k}\overline{z}^{l}e^{−|z|^{2}}dA(z) = δ_{kl}k!  (36)

for all k, l ≥ 0, we have

\frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} u_{1}^{k_{1}} ⋯ u_{r}^{k_{r}} \overline{(h_{r} (u_{1}, \frac{u_{2}}{2} , …, \frac{u_{r}}{r} , 0, 0, …))^{n}} ∏_{j=1}^{r} e^{−|u_{j}|^{2}}dA(u_{j})

= a_{k_{1},...,k_{r}}^{n,r} = [x_{1}^{r}x_{2}^{r} ⋯ x_{n}^{r}]t_{1}(x)^{k_{1}} ⋯ t_{r}(x)^{k_{r}} (37)

for all r-tuples (k_{1}, k_{2}, …, k_{r}), and hence (33) follows by taking linear combinations. Corollary 10. For a partition of weight |λ| = rn we have

g_{λ}^{(r)} = \frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} s_{λ}(t_{1}, …, t_{r}, 0, …)\overline{(h_{r} (t_{1}, \frac{t_{2}}{2} , …, \frac{t_{r}}{r} , 0, …))^{n}} ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j}). (38)

Note that for a pair of weighted homogeneous polynomials P and Q,

\frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} P (t_{1}, …, t_{r})\overline{Q(t_{1}, …, t_{r})} ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j}) = 0 unless deg P = deg Q. (39)

Since s_{λ} and h_{r}^{m} are weighted homogeneous polynomials with deg(s_{λ}) = |λ| and deg(h_{r}^{n}) = rm we have

\frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} s_{λ}(t_{1}, …, t_{r}, 0, …)\overline{(h_{r} (t_{1}, \frac{t_{2}}{2} , …, \frac{t_{r}}{r} , 0, …))^{m}} ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j}) = δ_{|λ|,rm}g_{λ}^{r}.

(40)

Remark 11. For example, for r = 1, 2, 3 we have

h_{1} (u_{1}, 0, …) = u_{1}
h_{2} (u_{1}, \frac{u_{2}}{2} , 0, …) = \frac{1}{2}u_{1}^{2} + \frac{1}{2}u_{2}
h_{3} (u_{1}, \frac{u_{2}}{2} , \frac{u_{3}}{3} , 0, …) = \frac{1}{6}u_{1}^{3} + \frac{1}{2}u_{1}^{2}u_{2} + \frac{1}{3}u_{3}.

The general formula [13, Eq. (2.14′)] is

h_{r} (u_{1}, \frac{u_{2}}{2} , …, \frac{u_{r}}{r} , 0, …) = ∑_{|μ|=r} \frac{1}{z_{μ}} ∏_{i=1}^{ℓ(μ)} u_{μ_{i}},  (41)

where z_{μ} is the standard constant factor

z_{μ} = ∏_{i≥1} i^{m_{i}} · m_{i}!  (42)

in which m_{i} = m_{i}(μ) is number of parts of the partition μ equal to i. Note that

|C_{μ}| = \frac{r!}{z_{μ}} and |μ| = r,  (43)

where C_{μ} is the conjugacy class of permutations of cycle type μ in the symmetric group S_{r}. Hence h_{r} (u_{1}, \frac{u_{2}}{2} , …, \frac{u_{r}}{r} , 0, 0, …) can be written alternatively as the cycle index polynomial of S_{r}:

h_{r} (u_{1}, \frac{u_{2}}{2} , …, \frac{u_{r}}{r} , 0, …) = \frac{1}{r!} ∑_{|λ|=r} |C_{λ}| ∏_{i=1}^{ℓ(λ)} u_{λ_{i}} = Cyc_{r}(u_{1}, u_{2}, …, u_{r}).  (44)

By taking into account (40) and (44) we obtain the following:

Corollary 12.

\frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} s_{λ}(t) exp (v̄^{r}\overline{Cyc_{r}(t)}) ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j}) = \begin{cases}\frac{v̄^{rn}}{n!} g_{λ}^{(r)}, & if |λ| = rn; \\ 0, & otherwise. \end{cases}  (45)

By the RSK formula (1) this leads to an integral representation of A_{d+1,r}(n):

Lemma 13. The following identity holds for all non-negative integers d, r, and n:

\frac{A_{d+1,r}(n)}{(rn)!n!}(v\overline{v})^{rn} = \frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} ( ∑_{\begin{matrix}|λ|=rn \\ ℓ(λ)≤d \end{matrix}} s_{λ}(v, 0, …)s_{λ}(t)) exp (v̄^{r}\overline{Cyc_{r}(t)}) ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j}).

(46)

Proof. By using the scaled version of (29) of the form

\frac{f_{λ}}{|λ|!}v^{|λ|} = s_{λ}(v, 0, 0, …),  (47)

we obtain

\frac{A_{d+1,r}(n)}{(rn)!n!}(v\overline{v})^{rn} = ∑_{\begin{matrix}|λ|=rn \\ ℓ(λ)≤d \end{matrix}} \frac{f_{λ}}{|λ|!}v^{|λ|} · \frac{g_{λ}^{(r)}}{n!} v̄^{rn}

= ∑_{\begin{matrix}|λ|=rn \\ ℓ(λ)≤d \end{matrix}} s_{λ}(v, 0, …) · \frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} s_{λ}(t) exp (v̄^{r}\overline{Cyc_{r}(t)}) ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j})

= \frac{1}{π^{r}} \underbrace{∫_{ℂ}⋯∫_{ℂ}}_{r} ( ∑_{\begin{matrix}|λ|=rn \\ ℓ(λ)≤d \end{matrix}} s_{λ}(v, 0, …)s_{λ}(t)) exp (v̄^{r}\overline{Cyc_{r}(t)}) ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j}).

(48)

3 Gessel’s Toeplitz determinant identity and the proof of the main theorem

Recall Gessel’s determinant formula [9]: the length-restricted Cauchy–Littlewood-type sum of products of Schur functions can be written as

∑_{ℓ(λ)≤d} s_{λ}(t)s_{λ}(s) = det(G_{d}(t, s)),  (49)

where t = (t_{1}, t_{2}, …), s = (s_{1}, s_{2}, …), and G_{d}(t, s) is the d × d Toeplitz determinant associated with the symbol

φ(t, s; z) = exp (∑_{k=1}^{∞} t_{k}z^{k} + ∑_{k=1}^{∞} s_{k}z^{−k}) = ∑_{m=−∞}^{∞} φ_{m}(t, s)z^{m}.  (50)

This “master identity”, combined with the integral representation for A_{d+1,r}(n) is sufficient to prove the main result of this paper.

Proof of Theorem 1. Gessel’s determinantal formula (49) with

t = (t_{1}, …, t_{r}, 0, , 0 …) and s = (v, 0, 0, …)  (51)

gives

∑_{ℓ(λ)≤d} s_{λ}(v, 0, …)s_{λ}(t_{1}, …, t_{r}, 0, …) = det(T_{d}(v, t))  (52)

where T_{d}(v, t) is the d × d Toeplitz determinant associated with the symbol

φ(v, t; z) = ∑_{m=−∞}^{∞} φ_{m}(v, t)z^{m} = exp (\frac{v}{z} + ∑_{j=1}^{r} t_{j}z^{j}) .  (53)

Therefore

\frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} det(T_{d}(v, t)) · exp (v̄^{r}\overline{Cyc_{r}(t)}) ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j})

= \frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} ( ∑_{ℓ(λ)≤d} s_{λ}(v, 0, …)s_{λ}(t_{1}, …, t_{r}, 0, …)) · exp (v̄^{r}\overline{Cyc_{r}(t)}) ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j})

= \frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} ∑_{n=0}^{∞} ( ∑_{\begin{matrix}ℓ(λ)≤d \\ |λ|=rn \end{matrix}} s_{λ}(v, 0, …)s_{λ}(t_{1}, …, t_{r}, 0, …)) · exp (v̄^{r}\overline{Cyc_{r}(t)}) ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j}),

(54)

where in the last step we used the simple observation that, by (45), a partition λ gives a non-trivial contribution to the integral only if its weight |λ| is divisible by r. The proof is concluded by comparing (54) with the integral representation (46) of A_{d+1,r}(n).

4 Calculation of A_{d+1,r}(n) using symbolic computer algebra

The purpose of this section is to illustrate that the generating function (12) can be used to calculate A_{d+1,r}(n) for small values of d, r, and n using basic symbolic computer algebra. There was no attempt made to optimize the algorithms used in the symbolic computation; our goal was simply to demonstrate that the generating function is not only a compact and abstract formula, but it can also be put to work in practice. This also provides numerical evidence that the series (12) does give the integer values it is supposed to, which is, after all, the most rewarding part of finding a generating function.

Below we use the short-hand notation t_{r} = (t_{1}, …, t_{r}). It is easy to see that the Laurent series coefficients of the Toeplitz symbol φ(v, t_{r}; z) are

φ_{m}(v, t_{r}) = ∑_{k=0}^{∞} h_{k+m}(t_{r})\frac{v^{k}}{k!} m = 0, 1, 2, …  (55)

φ_{−m}(v, t_{r}) = ∑_{k=m}^{∞} h_{k−m}(t_{r})\frac{v^{k}}{k!} m = 1, 2, …,  (56)

where h_{k}(t_{r}) are the complete symmetric polynomials in t_{r}. We can define the truncated Toeplitz entries

φ_{m}^{(N)}(v, t_{r}) = ∑_{k=0}^{rN} h_{k+m}(t_{r})\frac{v^{k}}{k!} m = 0, 1, 2, …  (57)

φ_{−m}^{(N)}(v, t_{r}) = ∑_{k=m}^{rN} h_{k−m}(t_{r})\frac{v^{k}}{k!} m = 1, 2, …  (58)

so that

φ_{m}(v, t_{r}) = φ_{m}^{(N)}(v, t_{r}) + O (v^{rN+1}) .  (59)

For small values of d the Toeplitz determinant with O (v^{rN+1})-truncated entries can be evaluated, and it can be further simplified by eliminating the terms of O (v^{rN+1}). We note that the evaluation of the determinant can be done much more efficiently by employing the division-free algorithm suggested by Ekhad, Shar, and Zeilberger [6].

The expansion of the second factor e^{\overline{v}^{r} Cyc_{t}(\overline{t}_{1},...,\overline{t}_{r})} in the integral formula (12) in \overline{v} is of the form

exp (\overline{v}^{r} Cyc_{t}(\overline{t}_{1}, …, \overline{t}_{r})) = E_{r}^{(N)}(t̄_{1}, t̄_{2}/2, …, t̄_{r}/r; v̄) + O (v̄^{rN+r}) ,  (60)

where

E_{r}^{(N)}(t̄_{1}, t̄_{2}/2, …, t̄_{r}/r; v̄) = ∑_{k=0}^{N} h_{r}(t̄_{1}, t̄_{2}/2, …, t̄_{r}/r, 0, 0)^{k} \frac{v̄^{kr}}{k!} .  (61)

Therefore, by replacing the Toeplitz determinant and the exponential factor with their truncated forms in the integral (12), we get

\frac{1}{π^{r}} \underbrace{∫_{ℂ} ⋯ ∫_{ℂ}}_{r} det (T_{d}^{(N)}(v, t_{r})) E_{r}^{(N)}(t̄_{1}, t̄_{2}/2, …, t̄_{r}/r; v̄) ∏_{j=1}^{r} e^{−|t_{j}|^{2}}dA(t_{j})

= ∑_{n=0}^{N} \frac{A_{d+1,r}(n)}{(rn)!n!}(v\overline{v})^{rn} + O ((v\overline{v})^{rN+r}) . (62)

That is, the terms of order at most rN in the product v\overline{v} can be trusted from the integral of the truncated expression.

The computation of area integrals can be implemented easily by using polar coordinates

\frac{1}{π} ∫_{ℂ} F (t)e^{−|t|^{2}}dA(t) = 2 ∫_{0}^{∞} (\frac{1}{2πi} ∮_{|u|=1} F (ru)\frac{du}{u}) e^{−r^{2}}rdr.  (63)

The contour integrals are computed by taking residues at u = 0 (as F (t) in the integrand is always a polynomial in t in our setting).

This simple method was implemented in Maple, and we obtained the values shown in Tables 2, 3, and 4. These all coincide with the numbers presented in the various appendices to Zeilberger’s online journal entry [7].

\begin{matrix}n\d & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 6 & 6 & 6 & 6 \\ 3 & 1 & 43 & 90 & 90 & 90 \\ 4 & 1 & 352 & 1879 & 2520 & 2520 \\ 5 & 1 & 3114 & 47024 & 102011 & 113400 \\ 6 & 1 & 29004 & 1331664 & 5176504 & 7235651 \\ 7 & 1 & 280221 & 41250519 & 307027744 & 592616287 \\ 8 & 1 & 2782476 & 1367533365 & 20472135280 & 58255807971 \\ 9 & 1 & 28221784 & 47808569835 & 1496594831506 & 6585311137855 \\ 10 & 1 & 291138856 & 1744233181074 & 117857270562568 & 832218817076725 \end{matrix}

Table 2: The calculated values of A_{d+1,2}(n).

\begin{matrix}n\d & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 20 & 20 & 20 & 20 \\ 3 & 1 & 374 & 1680 & 1680 & 1680 \\ 4 & 1 & 8124 & 173891 & 369600 & 369600 \\ 5 & 1 & 190893 & 21347262 & 117392909 & 168168000 \\ 6 & 1 & 4727788 & 2977892253 & 46121962742 & 117108036719 \\ 7 & 1 & 121543500 & 455912368540 & 21198300356500 & 105795227339731 \\ 8 & 1 & 3212914524 & 74876841353159 & 11003612776114008 & 115061550940847029 \end{matrix}

Table 3: The calculated values of A_{d+1,3}(n).

5 Conclusion and outlook

In this paper we presented the generating function (12) to solve the challenge posed by Ekhad and Zeilberger [7] to generalize Gessel’s determinant formula (3) for r = 1 to arbitrary values

\begin{matrix}n\d & 1 & 2 & 3 & 4 \\ 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 70 & 70 & 70 \\ 3 & 1 & 3199 & 34650 & 34650 \\ 4 & 1 & 173860 & 16140983 & 63063000 \\ 5 & 1 & 10203181 & 8854463421 & 142951955371 \\ 6 & 1 & 631326526 & 5532980565456 & 389426248416626 \end{matrix}

Table 4: The calculated values of A_{d+1,4}(n).

of the multiplicity r. The key step in constructing such a generating function was to express the Kostka coefficient g_{λ}^{(r)} as an integral of the Schur function s_{λ}, and use Gessel’s “master identity” to sum up the resulting Cauchy–Littlewood-type terms under the integrals.

We expect that the general formula (12) may be useful to find the associated linear differential equation with polynomial coefficients for the generating function, or equivalently, to find the recurrence relation with polynomial coefficients for A_{d+1,r}(n) for arbitrary values of r in a closed form.

Moreover, one can easily construct generating functions analogous to (12) for words with different types of multiple occurrences in its letters.

It may also be interesting to investigate the asymptotic distribution obtained from a fine-tuned scaling limit of the probability Prob (L_{n,r}(w) ≤ d) as n, d → ∞.

6 Acknowledgments

Many thanks to Doron Zeilberger for posting the challenge of generalizing Gessel’s generating function, his encouragement and kind feedback on a previous version of this manuscript, along with a generous donation to the OEIS in my name (see https://oeisf.org/donate/# 2015). I am grateful to Marco Bertola for his interest in this project and helpful discussions, and, in particular, for pointing out the standard scalar product interpretation (16) of the integral formulae. The thoughtful comments and suggestions of the anonymous referee helped a lot to improve the manuscript and made the paper much easier to read.

This work was supported in part by the Fonds de recherche du Québec—Nature et technologies (FRQNT) via the research grant Matrices Aléatoires, Processus Stochastiques et Systèmes Intégrables. The author acknowledges the excellent working conditions at Concordia University and the Centre des Recherches Mathématiques (CRM) in Montreal.

References

[1] D. Aldous and P. Diaconis. Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc. 36 (1999), 413–432.

[2] J. Baik, P. Deift, and K. Johansson, On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc. 12 (1999), 1119– 1178.

[3] J. Baik and E. M. Rains, Algebraic aspects of increasing subsequences, Duke Math. J. 109 (2001), 1–65.

[4] A. Borodin, A. Okounkov, and G. Olshanski, Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000), 481–515.

[5] G. Chapuy, The asymptotic number of 12 … d-avoiding words with r occurrences of each letter 1, 2, …, n, arxiv preprint arXiv:1412.6070, 2014. Available at http://arxiv.

org/abs/1412.6070.

[6] S. B. Ekhad, N. Shar, and D. Zeilberger. The number of 1 … d-avoiding permutations of length d + r for SYMBOLIC d but numeric r, arxiv preprint arXiv:1504.02513, 2015.

Available at http://arxiv.org/abs/1504.02513.

[7] S. B. Ekhad and D. Zeilberger. The generating functions enumerating 12 … d-avoiding words with r occurrences of each of 1, 2, …, n are D-finite for all d and all r, arxiv preprint arXiv:1412.2035, 2014. Available at http://arxiv.org/abs/1412.2035.

[8] C. J. Everett and P. R. Stein, The asymptotic number of integer stochastic matrices, Discrete Math. 1 (1971/72), 55–72.

[9] I. M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), 257–285.

[10] A. R. Its, C. A. Tracy, and H. Widom, Random words, Toeplitz determinants, and integrable systems. I, in Random Matrix Models and their Applications, Math. Sci. Res. Inst. Publ., Vol. 40, Cambridge Univ. Press, 2001, pp. 245–258.

[11] A. R. Its, C. A. Tracy, and H. Widom, Random words, Toeplitz determinants and integrable systems. II, Phys. D 152/153 (2001), 199–224.

[12] K. Johansson, The longest increasing subsequence in a random permutation and a unitary random matrix model, Math. Res. Lett. 5 (1998), 63–82.

[13] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford Univ. Press, 1995.

[14] P. A. MacMahon, Combinatory Analysis, Chelsea Publ., 1960.

[15] P. van Moerbeke, Random and integrable models in mathematics and physics, in Random Matrices, Random Processes and Integrable Systems, CRM Ser. Math. Phys., Springer, 2011, pp. 3–130.

[16] F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds. NIST Digital Library of Mathematical Functions, http://dlmf.nist.gov/, Release 1.1.9 of 2023-03-15.

[17] D. Romik, The Surprising Mathematics of Longest Increasing Subsequences, Cambridge Univ. Press, 2015.

[18] R. P. Stanley, Enumerative Combinatorics. Vol. 2, Cambridge Univ. Press, 1999.

[19] C. A. Tracy and H. Widom, On the distributions of the lengths of the longest monotone subsequences in random words, Probab. Theory Related Fields 119 (2001), 350–380.

2020 Mathematics Subject Classification: Primary 05A15; Secondary 05E05, 05A05. Keywords: longest increasing subsequence, random permutation of multiset, random word, Schur function, Toeplitz determinant.

(Concerned with sequences \underline{A220097}, \underline{A266734}, \underline{A266735}, \underline{A266737}, \underline{A266741}, \underline{A267479}, and \underline{A267480}.)

Received October 18 2015; revised versions received June 15 2023; June 27 2023. Published in Journal of Integer Sequences, July 24 2023.

Return to Journal of Integer Sequences home page.