ON LATTICE PATH COUNTING BY MAJOR AND DESCENTS

C. Krattenthaler S. G. Mohanty

Abstract. n-dimensional lattice paths which do not touch the hyperplanes x_{i}−x_{i+1} = −1, i = 1, 2, …, n − 1, and x_{n} − x_{1} = −1 − K are enumerated by McMahon’s major index and variations of the major index. A formula involving determinants is obtained. For n = 2 we also present a formula for counting these lattice paths simultaneously by major and descents.

Consider n-dimensional lattice paths consisting of positive unit steps. In the sequel they are called simply paths for short. Any path p from μ μ μ to λ λ λ may be represented by the pair (μ μ μ, π), where μ μ μ is the initial point of p and π is the multiset permutation of {1^{λ_{1}−μ_{1}}, 2^{λ_{2}−μ_{2}}, …, n^{λ_{n}−μ_{n}}} which comes out of p by successively writing i for a step in x_{i}-direction. For example, the path p_{0}: (2, 1, 0) → (3, 1, 0) → (3, 1, 1) → (3, 2, 1) → (3, 3, 1) → (4, 3, 1) → (4, 4, 1) → (5, 4, 1) → (5, 4, 2) in this representation reads ((2, 1, 0), 13221213).

The number of descents of a multiset permutation π = π_{1}π_{2} … π_{L}, des π, is

des π = |{i : π_{i} > π_{i+1}, 1 ≤ i ≤ L − 1}| .

The major of a multiset permutation π, maj π, is the sum of the positions where a descent occurs,

maj π = ∑_{i=1}^{L−1} iχ(π_{i} > π_{i+1}) .

(χ is the usual truth function.) For example, for π_{0} = 13221213 we have des π_{0} = 3 and maj π_{0} = 2 + 4 + 6 = 12. These definitions are extended to paths p = (μ μ μ, π) by maj p = maj π and des p = des π.

It was McMahon who introduced these two notions in his treatise on generating functions for plane partitions [7]. His idea of computing plane partition generating functions with the help of counting “lattice permutations” by major and descents, was formalized and generalized by Stanley in his thesis (cf. [9]). In particular, Stanley’s theorem [9, Corollaries 5.3 and 5.7] implies that the generating function for plane partitions of the skew shape λ λ λ/μ μ μ, λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} and μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{n}, can

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 05A15; Secondary 05A10, 05A30.

Key words and phrases. Lattice paths, major index, descents.

be computed by solving the problem of counting n-dimensional lattice paths from μ μ μ to λ λ λ which do not touch any of the hyperplanes

(1)  x_{i} − x_{i+1} = −1,  i = 1, 2, …, n − 1 .

Besides, another theorem of Stanley [9, Proposition 8.2] implies that the generating function for plane partitions of shape λ λ λ/μ μ μ with parts bounded by m can be computed by counting the same family of paths with respect to maj and des. While the case of major counting has been solved completely [4], for the case of counting simultaneously by major and descents we have only a solution for n = 2. In fact, a more general theorem is given below (Theorem C). Yet, the existence of a simple formula for the generating function for plane partitions with bounded parts (see e.g. [2, Theorem 16]) strongly suggests that there should be also a simple formula for counting n-dimensional paths which do not touch any of the hyperplanes in (1) by major and descents.

In this paper we encounter the more general problem of counting paths from μ μ μ to λ λ λ which do not touch any of the hyperplanes in (1) and do not touch the additional hyperplane

(2)  x_{n} − x_{1} = −1 − K ,

where K is some positive integer, by major and descents. While the case of counting by only major is solved completely (Theorem A), and this result is even generalized to statistics which are variations of the major statistics (Theorem B), for counting by both major and descents we are only able to give a formula for n = 2 (Theorem C), as mentioned above.

The cardinality of the family of paths under consideration has been previously computed by Filaseta [1]. His theorem comes out of Theorem A by setting q = 1.

For sake of brevity we do not give proofs of our results. Detailed proofs of Theorems A and B can be found in [5], the proof of Theorem C is given in [6].

We use the usual multidimensional notation. If λ λ λ = (λ_{1}, λ_{2}, …, λ_{n}) and μ μ μ = (μ_{1}, μ_{2}, …, μ_{n}), then |λ λ λ| = λ_{1}+λ_{2}+⋯+λ_{n}, and λ λ λ−μ μ μ = (λ_{1}−μ_{1}, λ_{2}−μ_{2}, …, λ_{n}−μ_{n}). If λ_{i} ≥ μ_{i} for all i = 1, 2, …, n, we write λ λ λ ≥ μ μ μ.

Let q be an indeterminate. The q-notations we use are [α] = (1 − q^{α}), [m]! =

[m] · [m − 1] ⋯ [1], [0]! = 1, and [ \begin{matrix}|λ λ λ| \\ λ & λ & λ \end{matrix} ] = [|λ λ λ|]!/[λ_{1}]! [λ_{2}]! ⋯ [λ_{n}]!.

Let K be an arbitrary fixed positive integer and let K_{n} denote the set of all n-tuples λ λ λ of integers with

λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} ≥ λ_{1} − K .

Theorem A. Let λ λ λ,μ μ μ ∈ K_{n} and λ λ λ ≥ μ μ μ. The generating function ∑ q^{maj p}, where the sum is over all lattice paths from μ μ μ to λ λ λ which do not touch any one of the hyperplanes in (1) and (2), is given by

∑_{u u u∈U_{n}}[|λ λ λ − μ μ μ|]! det_{1≤s,t≤n} (q^{T (s,t,u u u,μ μ μ)}/[λ_{s} − s − μ_{t} + t − (K + n)u_{s}]!) ,

where U_{n} is the set of all n–tuples u u u of integers with u_{1} + ⋯ + u_{n} = 0, and

T (s, t,u u u,μ μ μ) = (μ_{t} − t)(s − t) + (n − 1)u_{s}(μ_{t} − t) + (K + n)((n − 1)\frac{u_{s}^{2}}{2} + su_{s}) .

This result generalizes Theorem 1 of [4].

Let τ be a fixed permutation of [1, n]. We extend τ to multiset permutations π = π_{1}π_{2} … π_{L} which satisfy π_{i} ∈ {1, 2, …, n} by

τ(π) = τ(π_{1})τ(π_{2}) … τ(π_{L}) .

The action of τ on a path p = (μ μ μ, π) then is defined by τ(p) = (μ μ μ, τ(π)). Now we introduce the following permutation-indexed statistics:

maj_{τ} p := maj τ(p) .

Obviously, maj_{id} is identically with the major (= greater) index, while for τ_{0} given by τ_{0}(i) = n + 1 − i the statistics maj_{τ_{0}} coincides with McMahon’s lesser index [7, p. 136]. The next theorem is the maj_{τ} -analogue of Theorem A.

Theorem B. Let λ λ λ,μ μ μ ∈ K_{n} and λ λ λ ≥ μ μ μ. The generating function ∑ q^{maj_{τ} p}, where the sum is over all lattice paths from μ μ μ to λ λ λ which do not touch any one of the hyperplanes in (1) and (2), is given by

∑_{u u u∈U_{n}}[|λ λ λ − μ μ μ|]! det_{1≤s,t≤n} (q^{T_{τ} (s,t,u u u,μ μ μ)}/[λ_{s} − s − μ_{t} + t − (K + n)u_{s}]!) .

The exponents T_{τ} (s, t,u u u,μ μ μ) are given by

T_{τ} (s, t,u u u,μ μ μ) = (μ_{t} − t) ∑_{j=t}^{s−1} c(j) + u_{s}(μ_{t} − t) ∑_{j=1}^{n} c(j)

+ (K + n)\frac{u_{s}^{2}}{2} ∑_{j=1}^{n} c(j) + (K + n)u_{s} ∑_{j=1}^{s−1} c(j) ,

where c(j) = χ(τ(j) < τ(j + 1)), c(n) = χ(τ(n) < τ(1)) and we adopt the convention that ∑_{j=l}^{l−1} a_{j} = 0, and ∑_{j=l}^{k−1} a_{j} = − ∑_{j=k}^{l−1} a_{j} whenever k < l.

Our last theorem gives the promised result for counting 2-dimensional paths not touching the lines x_{1} − x_{2} = −1 and x_{2} − x_{1} = −1 − K by major and descents. The formulation of the theorem even is slightly more general.

Theorem C. Given c, d ∈ ℤ, d > c, let λ_{1}+c ≤ λ_{2} ≤ λ_{1}+d and μ_{1}+c ≤ μ_{2} ≤ μ_{1}+d. The generating function ∑ x^{des p}q^{maj p}, where the sum is over all lattice paths from μ μ μ = (μ_{1}, μ_{2}) to λ λ λ = (λ_{1}, λ_{2}) which do not cross the lines x_{2} = x_{1} + d and x_{2} = x_{1} + c, is given by

∑_{n≥0} x^{n} ∑_{k∈ℤ} q^{n^{2}+k^{2}(d−c+1)−k(1−c+μ_{2}−μ_{1})}

× ([ \begin{matrix}λ_{1} − μ_{1} − k(d − c) \\ n + k \end{matrix} ] [ \begin{matrix}λ_{2} − μ_{2} + k(d − c) \\ n − k \end{matrix} ]

− [ \begin{matrix}λ_{2} − μ_{1} − k(d − c) − c + 1 \\ n + k \end{matrix} ] [ \begin{matrix}λ_{1} − μ_{2} + k(d − c) + c − 1 \\ n − k \end{matrix} ]) ,

where [ \begin{matrix}a \\ b \end{matrix} ] is the Gaussian binomial coefficient, [ \begin{matrix}a \\ b \end{matrix} ] = \frac{[a]!}{[b]! [a−b]!}.

Previous results of McMahon [8, p.1429] and of one of the authors [3, Theorems 5-7] are special cases of this theorem.

References

1. M. Filaseta, A new method for solving a class of ballot problems, J. Combin. Theory A 39 (1985), 102–111.

2. I. Gessel and G. Viennot, Determinants, paths, and plane partitions, preprint.

3. C. Krattenthaler, Counting lattice paths with a linear boundary, Part 2: q-ballot and q-Catalan numbers, Sitz.ber. d. ÖAW, Math-naturwiss. Klasse 198 (1989), 171–199.

4. , Enumeration of lattice paths and generating functions for skew plane partitions, Manuscripta Math. 63 (1989), 129–155.

5. C. Krattenthaler and S. G. Mohanty, q-Generalization of a ballot problem, Discrete Math. 126 (1994), 195–208.

6. C. Krattenthaler and S. G. Mohanty, On lattice path counting by major and descents, Europ. J. Combin. 14 (1993), 43–51.

7. P. A. McMahon, Combinatory Analysis, Vol. 2, Cambridge University Press, 1916, reprinted by Chelsea, New York, 1960.

8. , Collected Papers: Combinatorics, Vol. I, MIT Press, Cambridge, Massachusetts, 1978.

9. R. P. Stanley, Ordered structures and partitions, Mem. Amer. Math. Soc. No. 119, American Mathematical Society, Providence, R.I., 1972.

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.

McMaster University, Hamilton, Ontario, Canada L8S 4K1.