q–Generalization of a ballot problem

C. Krattenthaler S. G. Mohanty

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

McMaster University, Hamilton, Ontario, Canada L8S 4K1

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 certain statistics, one of which is MacMahon’s major index, the others being variations of it. By a reflection–like proof, a formula involving determinants is obtained. It is a q–extension of Filaseta’s (J. Combin. Theory A 39 (1985), 102–111) expression for the number of elections in a specific ballot problem.

1. Introduction. In [2] Filaseta considered the following ballot problem. Let a_{1}, a_{2}, …, a_{n} and t_{1}, t_{2}, …, t_{n} be positive integers such that

a_{i} < a_{i−1} + t_{i} for i = 1, 2, …, n ,

where we take a_{0} = a_{n} in the case i = 1. Suppose n candidates A_{1}, A_{2}, …, A_{n} in an election in which candidate A_{i} received a_{i} votes, i = 1, 2, …, n. Let A_{i}(m) denote the number of votes A_{i} received after the first m votes have been cast, i = 1, 2, …, n. How many possible elections are there such that

A_{i}(m) < A_{i−1}(m) + t_{i} for i = 1, 2, …, n and m = 1, 2, …, ∑_{i=1}^{n} a_{i} ,

where again we take A_{0}(m) = A_{n}(m) in the case i = 1. Using an analytical argument, Filaseta obtained the following expression for this number of elections,

(1.1)  ∑_{u_{1}∈ℤ} ⋯ ∑_{u_{n}∈ℤ}_{u_{1}+···+u_{n}=0}(a_{1} + ⋯ + a_{s})! det_{1≤i,j≤n}(1/b_{ij}!) ,

1980 Mathematics Subject Classification (1991 Revision). Primary 05A15; Secondary 05A10, 05A17, 05A30.

Key words and phrases. Lattice paths, major index, ballot problem.

where

b_{ij} = a_{j} + u_{i} ∑_{ν=1}^{n} t_{ν} + ∑_{ν=1}^{i} t_{ν} − ∑_{ν=1}^{j} t_{ν} .

This ballot problem is equivalent to the problem of counting n–dimensional lattice paths from 0 0 0 to a a a = (a_{1}, a_{2}, …, a_{n}), consisting of positive unit steps, which do not touch any one of the hyperplanes

(1.2)  x_{i} = x_{i−1} + t_{i}  for i = 1, 2, …, n ,

where again x_{0} := x_{n}. This is seen by interpreting a path p from 0 0 0 to a a a by an election in which the m–th vote is a vote for candidate A_{j} if and only if the m–th step in the path p is a step in the x_{j}–direction.

In this paper we consider the problem of counting paths from 0 0 0 to a a a which do not touch any one of the hyperplanes in (1.2) by MacMahon’s [5] greater index, which nowadays frequently is called major index. (To be precise, we consider the equivalent problem of counting lattice paths from μ μ μ to λ λ λ not touching any one of the hyperplanes in (2.2) and (2.3).) The counting formula (Theorem 1 in section 3) which we obtain is a q–analogue of (1.1). Besides, this result generalizes previous ones of one of the authors [4]. It is easily seen that, using the terminology of Gessel and Zeilberger [3], Filaseta’s result solves the problem of counting lattice paths consisting of positive unit steps in a Weyl chamber corresponding to the affine root system S(A_{n}). Hence, our results give a solution for the problem of q-counting lattice paths in a Weyl chamber of S(A_{n}). The key for proving Theorem 1 lies in extending the proof method of [4] to this generalized path enumeration problem. Since this method heavily relies on Zeilberger’s [6] reflection proof for the classical n–candidate ballot problem, the first thing to be done is to give a reflection proof of Filaseta’s formula (1.1). This is the contents of section 4. (In fact, the arguments in section 4 are just the same as those in the proof of Theorem 1 in [3] but specialized to S(A_{n}).) Section 2 contains all relevant definitions. Finally, in section 5, we give the bijections which replace the reflections of section 4, thus establishing a combinatorial proof of Theorem 1. Section 6 presents an extension of Theorem 1 to a family of major-like statistics (Theorem 2). This result does not only include the case of counting by MacMahon’s greater index as special case, which is discussed in the preceding section, but also the corresponding result for counting lattice paths by MacMahon’s lesser index [5, p. 136].

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

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

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

In the sequel we assume K to be an arbitrary fixed positive integer. Let K_{n} stand for the set of all n–tuples λ λ λ of integers with

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

Let S_{n} denote the symmetric group of order n. Given σ ∈ S_{n} we write λ λ λ_{σ} for (λ_{σ(1)}, λ_{σ(2)}, …, λ_{σ(n)}). For the set of all permutations of the multiset {1^{μ_{1}}, 2^{μ_{2}}, …, n^{μ_{n}}} (the multiset consisting of μ_{i} copies of i, i = 1, 2, …, n) we write S(μ μ μ).

Throughout this paper, a lattice path p will be a finite sequence (p(0), p(1), …, p(L)) of points p(i) in the integer lattice ℤ^{n}, where p(i) ∈ ℤ^{n} and p(i + 1) − p(i) = E_{j} for some j, 1 ≤ j ≤ n, i = 0, 1, 2, . . .. E_{j} stands for the vector with the j–th coordinate being equal to 1, all other being equal to 0. [p(i)]_{k} will denote the k–th coordinate of the i–th point on the path p. A lattice path p from μ μ μ to λ λ λ can be symbolized by a pair (μ μ μ, π), where μ μ μ = p(0) and π ∈ S(λ λ λ − μ μ μ). π is obtained by proceeding along the path, starting at its first point μ μ μ, and successively writing a k for each step in the x_{k}–direction. To be precise, π = π_{1} … π_{L}, where L = |λ λ λ − μ μ μ| and π_{i} = k if and only if p(i) − p(i − 1) = E_{k}. Conversely, if a path p is given by (μ μ μ, π), the points of p are determined by

(2.1)  p(i) = μ μ μ + ∑_{k=1}^{n} E_{k} · |{r : 1 ≤ r ≤ i and π_{r} = k}| .

To give an example, take n = 3 and p_{0} = ((1, 2, 1), (1, 2, 2), (1, 2, 3), (2, 2, 3), (2, 3, 3), (3, 3, 3)). Then p_{0} is symbolized by the pair ((1, 2, 1), 33121).

By N(μ μ μ → λ λ λ) we denote the set of all lattice paths from μ μ μ to λ λ λ. We write N(μ μ μ → λ λ λ)^{+} for the set of all lattice paths from μ μ μ to λ λ λ whose points all lie in K_{n}. For λ λ λ, μ μ μ ∈ K_{n} the set N(μ μ μ → λ λ λ)^{+} is equal to the set of all lattice paths from μ μ μ to λ λ λ which do not touch any one of the hyperplanes

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

and

(2.3)  x_{n} − x_{1} = −1 − K .

Let H_{i} denote the hyperplane x_{i} − x_{i+1} = −1, i = 1, 2, …, n − 1, let H_{n} denote the hyperplane in (2.3), and let R_{i} be the reflection with respect to H_{i}, i = 1, 2, …, n. N(μ μ μ → λ λ λ)^{−} stands for the set of all lattice paths from μ μ μ to λ λ λ which touch at least one of the hyperplanes in (2.2) and (2.3).

Next, for a given multiset permutation π = π_{1}π_{2} … π_{L} we define the major statistics by

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

(χ(A) = 1 if A is true, and χ(A) = 0 otherwise.) Having in mind the representation of a lattice path p by a pair (μ μ μ, π), we extend maj to lattice paths by defining maj p = maj π, if p = (μ μ μ, π). Finally we introduce the generating function

G(μ μ μ → λ λ λ; q) = ∑_{p} q^{maj p} ,

where the sum is taken over all p ∈ N(μ μ μ → λ λ λ). Analogously,

G(μ μ μ → λ λ λ; q)^{+} = ∑_{p} q^{maj p} ,

where the sum is over all p ∈ N(μ μ μ → λ λ λ)^{+}, and

G(μ μ μ → λ λ λ; q)^{−} = ∑_{p} q^{maj p} ,

where the sum is over all p ∈ N(μ μ μ → λ λ λ)^{−} .

3. Formulation of the Theorem. In section 1 it was shown that Filaseta’s ballot problem is equivalent with the problem of counting all lattice paths from 0 0 0 to a a a which do not touch any one of the hyperplanes in (1.2). Let y y y = (y_{1}, y_{2}, …, y_{n}) be an element of ℤ_{n}. By performing the transformation y y y → z zz, where

y_{i} = z_{i} + ∑_{ν=1}^{i} t_{ν} − i for i = 1, 2, …, n ,

it is seen that the above lattice path counting problem is equivalent with the problem of counting all lattice paths from μ μ μ to λ λ λ which do not touch any one of the hyperplanes in (2.2) and (2.3), where

μ_{i} = i − ∑_{ν=1}^{i} t_{ν} ,

λ_{i} = a_{i} + i − ∑_{ν=1}^{i} t_{ν} ,

and

K = ∑_{ν=1}^{n} t_{ν} − n .

The major counting extension of this counting problem, which is proved in section 5, is the following.

Theorem 1. 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 (2.2) and (2.3), is given by

G(μ μ μ → λ λ λ; q)^{+}

= ∑_{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 = (u_{1}, u_{2}, …, u_{n}) 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}) .

The special case K > |λ λ λ − μ μ μ| (this is the corresponding result for counting lattice paths which do not touch any of the hyperplanes in (2.2) ) has previously appeared in [4, Theorem 1].

To give a concrete example, take n = 3, K = 2, μ μ μ = (1, −1, −1) and λ λ λ = (3, 2, 1). We want to count all paths p from (1, −1, −1) to (3, 2, 1) with respect to the major index which do not touch x_{1} − x_{2} = −1, x_{2} − x_{3} = −1, and x_{3} − x_{1} = −3. Let such a path be represented by p = ((1, −1, −1), π) as was explained above. The following table lists all possibilities of π together with the corresponding major–values.

\begin{matrix}π & maj π = maj p \\ 2312321 & 13 \\ 2312312 & 7 \\ 2312231 & 8 \\ 2321231 & 11 \\ 2321312 & 10 \\ 2321321 & 16 \\ 2323112 & 6 \\ 2323121 & 12 \\ 2231231 & 9 \\ 2231312 & 8 \\ 2231321 & 14 \\ 2233112 & 4 \\ 2233121 & 10 \end{matrix}

Hence,

G((1, −1, −1) → (3, 2, 1))^{+} = q^{4} + q^{6} + q^{7} + 2q^{8} + q^{9} + 2q^{10} + q^{11} + q^{12} + q^{13} + q^{14} + q^{16},

which agrees with the claimed expression in Theorem 1 as can be easily checked.

4. The reflection proof. Let λ λ λ, μ μ μ ∈ K_{n} and λ λ λ ≥ μ μ μ. For the number of all lattice paths from μ μ μ to λ λ λ, G(μ μ μ → λ λ λ; 1), we have

(4.1)  G(μ μ μ → λ λ λ; 1) = \binom{|λ λ λ − μ μ μ|}{λ λ λ − μ μ μ} .

Following Zeilberger [6], for σ ∈ S_{n} we define

e ee_{σ} = (1 − σ(1), 2 − σ(2), …, n − σ(n)) .

We are going to construct a bijection between

(4.2)  _{⋃_{σ even} ; u u u∈U_{n}}N(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ)^{−}

and

(4.3)  _{⋃_{σ odd} ; u u u∈U_{n}}N(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ)^{−} ,

which proves

(4.4) _{∑_{σ even} ; u u u∈U_{n}}G(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ; 1)^{−}

=_{∑_{σ odd} ; u u u∈U_{n}}G(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ; 1)^{−} .

This is done by application of the reflection principle. Consider a lattice path p of N(μ μ μ_{σ} + e ee_{σ} + (K + n)μ μ μ → λ λ λ)^{−}. Let H_{j} be the last hyperplane of those in (2.2) and (2.3) which the path p meets. If j ≤ n − 1 reflection with respect to H_{j} has the effect

(4.5)  R_{j}(x_{1}, …, x_{j}, x_{j+1}, …, x_{n}) = (x_{1}, …, x_{j+1} − 1, x_{j} + 1, …, x_{n}) ,

while reflection with respect to H_{n} yields

(4.6)  R_{n}(x_{1}, x_{2}, …, x_{n−1}, x_{n}) = (x_{n} + K + 1, x_{2}, …, x_{n−1}, x_{1} − K − 1) .

Hence, for j ≤ n − 1, we have

(4.7)  R_{j}(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u) = μ μ μ_{σ(j,j+1)} + e ee_{σ(j,j+1)} + (K + n)u u u^{(j)} ,

where u u u^{(j)} = (u_{1}, …, u_{j+1}, u_{j}, …, u_{n}), and if j = n,

(4.8)  R_{n}(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u) = μ μ μ_{σ(1,n)} + e ee_{σ(1,n)} + (K + n)u u u^{(n)} ,

where u u u^{(n)} = (u_{n}+1, u_{2}, …, u_{n−1}, u_{1}−1). ((g, h) is the transposition which exchanges g and h. An expression of the form σ(g, h) means the composition σ ∘ (g, h) of the permutations σ and (g, h).) Therefore, replacing the portion of the path p until the last meeting with H_{j} by its reflection with respect to H_{j}, turns p into a path of N(μ μ μ_{σ(j,j+1)} + e ee_{σ(j,j+1)} + (K + n)u u u^{(j)} → λ λ λ)^{−} if j ≤ n − 1, in the case j = n by this reflection we obtain a path of N(μ μ μ_{σ(1,n)} + e ee_{σ(1,n)} + (K + n)u u u^{(n)} → λ λ λ)^{−}. Since the reflected path again meets H_{j} as last hyperplane, and its last meeting point is the same, renewed application of this reflection procedure would give the original path. Therefore this mapping in fact is an involution which consequently defines the desired bijection between the sets (4.2) and (4.3). This implies that (4.4) holds.

Since, because of μ μ μ ∈ K_{n}, for σ ≠ id or u u u ≠ 0 0 0 we have

(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u) ∉ K_{n} ,

we get

(4.9) N(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ)^{−} = N(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ)

for σ ≠ id or u u u ≠ 0 0 0 .

Therefore, by consecutive use of (4.4), (4.9), and (4.1), we have

(4.10)

G(μ μ μ → λ λ λ; 1)^{+} = G(μ μ μ → λ λ λ; 1) − G(μ μ μ → λ λ λ; 1)^{−}
= G(μ μ μ → λ λ λ; 1) − G(μ μ μ → λ λ λ; 1)^{−}

+_{∑_{σ∈S_{n}} ; u u u∈U_{n}} sgn σ G(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ; 1)^{−}

=_{∑_{σ∈S_{n}} ; u u u∈U_{n}} sgn σ G(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ; 1)

=_{∑_{σ∈S_{n}} ; u u u∈U_{n}} sgn σ (\begin{matrix}|λ λ λ − μ μ μ| \\ λ λ λ − μ μ μ_{σ} − e ee_{σ} − (K + n)u u u \end{matrix})

= ∑_{u u u∈U_{n}} |λ λ λ − μ μ μ|! det(1/(λ_{s} − s − μ_{t} + t − (K + n)u_{s})!) .

5. Proof of the Theorem. To prove Theorem 1, the reflection procedure of section 4 must be modified because, when reflecting a part of a lattice path, nothing can be said about the major of its image. Therefore, in order to extend the reflection proof to q ≠ 1, we construct a map φ, which sends the initial point of a path to the same point as the reflection procedure would do, but is (in a certain sense) also maj–preserving. Let the weight w(p) of a path p ∈ N(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ) be defined by

(5.1)  w(p) = q^{∑_{s=1}^{n} T (s,σ(s),u u u,μ μ μ)}q^{maj p} ,

where T (s, t, u u u, μ μ μ) is the number given in Theorem 1. What we are going to do, is to construct a weight–preserving bijection φ between the two sets (4.2) and (4.3), which sends the initial point of a path to the same point as the reflection procedure would do.

Now, let p ∈ N(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ)^{−}. First, suppose that the path p meets H_{j} as the last hyperplane of those in (2.2) and (2.3), and j ≤ n − 1. In [4] a mapping Φ was given satisfying the following properties (cf. [4, Def. 3, p. 145 (3),(4), (5.25)]):

(1) Φ acts on paths which meet one of the hyperplanes H_{j}, 1 ≤ j ≤ n − 1.

(2) If the path \overline{p} ∈ N(\overline{μ} \overline{μ} \overline{μ} → \overline{λ} \overline{λ} \overline{λ})^{−} meets H_{j} as the last hyperplane, j ≤ n − 1, then Φ(\overline{p}) ∈ N(R_{j}(\overline{μ} \overline{μ} \overline{μ}) → \overline{λ} \overline{λ} \overline{λ})^{−} and

(5.2)  maj Φ(\overline{p}) = maj \overline{p} − \overline{μ}_{j} + \overline{μ}_{j+1} − 1 .

(3) Φ is an involution.

For p satisfying the above properties we define

φ(p) : = Φ(p) .

By (2) this immediately implies

p ∈ N(μ μ μ_{σ(j,j+1)} + e ee_{σ(j,j+1)} + (K + n)u u u^{(j)} → λ λ λ)^{−} ,

with the u u u^{(j)} of section 4. Moreover, using the weight property (5.2), we obtain

(5.3)  \begin{matrix}w( & φ(p)) = q^{∑_{s=1}^{n} T (s,(σ(j,j+1))(s),u u u^{(j)},μ μ μ)}q^{maj(Φ(p))} \\ = q^{∑_{s=1}^{n} T (s,σ(s),u u u,μ μ μ)−μ_{σ(j+1)}+σ(j+1)+μ_{σ(j)}−σ(j)+(K+n)(u_{j}−u_{j+1})} \\ · q^{maj p−μ_{σ(j)}−j+σ(j)−(K+n)u_{j}+μ_{σ(j+1)}+j+1−σ(j+1)+(K+n)u_{j+1}−1} \\ = w(p) . \end{matrix}

Now suppose that p meets H_{n} as last hyperplane. To define φ(p) in this case, we proceed in a manner analogous to [4, sec. 5]. Given a multiset permutation π = π_{1}π_{2} … π_{L}, π_{i} ∈ {1, 2, …, n}, we define the difference function d_{n}(π, i) by

d_{n}(π, i) = |{r : r ≤ i and π_{r} = n}| − |{r : r ≤ i and π_{r} = 1}| .

d_{n}(π, i) is the difference between the number of n’s and the number of 1’s in π_{1}π_{2} … π_{i}. In the following two definitions two auxiliary maps, L_{n} and R_{n}, are introduced. L_{n} has the effect of changing a single step in the x_{1}–direction into a step in x_{n}–direction, R_{n} has the reverse effect.

Definition 1. Let π = π_{1}π_{2} … π_{L} be a multiset permutation where the function i → d_{n}(π, i) does not reach its minimal value at i = 0 or i = L. Let k be the smallest integer, 1 ≤ k ≤ L − 1, where the function i → d_{n}(π, i) reaches its minimal value, in other words

i < k implies d_{n}(π, i) > d_{n}(π, k) ,
i ≥ k implies d_{n}(π, i) ≥ d_{n}(π, k) .

Obviously, π_{k} = 1. This given, we define L_{n} by:

(A) If π satisfies

π_{e} > π_{e+1} ≤ ⋯ ≤ π_{k−1} ≤ 1 < π_{k+1} ≤ ⋯ ≤ π_{f} > π_{f+1} ,

where 1 ≤ e + 1 < f ≤ L, and

either (a) e + 1 < k < f
or (b) k = e + 1 and π_{e} > π_{e+2} ,

then

L_{n}(π) = π_{1} … π_{e}π_{e+1} … π_{k−1}π_{k+1} … π_{f} n π_{f+1} … π_{L} .

(B) If π satisfies

π_{e} ≤ π_{e+1} > ⋯ > π_{k−1} > 1 < π_{k+1}

where 1 ≤ e + 1 < k ≤ L, and π_{k−1} ≤ π_{k+1}, then

L_{n}(π) = π_{1} … π_{e} n π_{e+1} … π_{k−1}π_{k+1} … π_{L} .

(By convention, if i > j, the symbol π_{i} … π_{j} means the empty word. For the detailed conventions of how to read the inequality chains, we refer the reader to [4, sec. 5].)

Defintion 2. Let π_{1}π_{2} … π_{L} be a multiset permutation where d_{n}(π, L) exceeds the minimal value of the function i → d_{n}(π, i) by at least two. Let (r − 1) be the largest integer, 0 ≤ r − 1 ≤ L − 1, where i → d_{n}(π, i) reaches its minimal value, meaning

i ≤ r − 1 implies d_{n}(π, i) ≥ d_{n}(π, r − 1) ,
i > r − 1 implies d_{n}(π, i) > d_{n}(π, r − 1) .

Then π_{r} = n. This given we define R_{n} by:

(A) If π satisfies

π_{e} > π_{e+1} ≤ ⋯ ≤ π_{r−1} < n ≤ π_{r+1} ≤ ⋯ ≤ π_{f} > π_{f+1} ,

where 1 ≤ e + 1 < f ≤ L and

either (a) e + 1 < r < f
or (b) r = f and π_{f−1} > π_{f+1} ,

then

R_{n}(π) = π_{1} … π_{e} 1 π_{e+1} … π_{r−1}π_{r+1} … π_{f}π_{f+1} … π_{L} .

(B) If π satisfies

π_{r−1} < n > π_{r+1} > ⋯ > π_{f} ≤ π_{f+1} ,

where 1 ≤ r < f ≤ L, and π_{r−1} ≤ π_{r+1}, then

R_{n}(π) = π_{1} … π_{r−1}π_{r+1} … π_{f} 1 π_{f+1} … π_{L} .

Following the lines of [4, sec. 5], it can be shown that L_{n} and R_{n} are well–defined, and that

L_{n} ∘ R_{n} = R_{n} ∘ L_{n} = id .

Besides, from the definition of L_{n} and R_{n} it is easily seen that for any multiset permutation π there holds

(5.4)  maj L_{n}(π) = maj R_{n}(π) = maj π .

Now we are able to define φ(p) for p meeting H_{n} as last hyperplane. Let p = (μ μ μ_{σ} + e ee_{σ} + (K + n)u u u, π), then

(5.5)  φ(p) = (R_{n}(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u), L_{n}^{E(σ,K,μ μ μ,u u u)}(π)) ,

where

E(σ, K, μ μ μ, u u u) = [μ μ μ_{σ} + e ee_{σ} + (K + n)u u u]_{n} − [μ μ μ_{σ} + e ee_{σ} + (K + n)u u u]_{1} + K + 1
= μ_{σ(n)} + n − σ(n) − μ_{σ(1)} − 1 + σ(1)
+ (K + n)(u_{n} − u_{1}) + K + 1 .

If the exponent E(σ, K, μ μ μ, u u u) in (5.5) is negative, by L_{n}^{E(σ,K,μ μ μ,u u u)} we mean R_{n}^{−E(σ,K,μ μ μ,u u u)}.

It can be shown that φ is well-defined, that the endpoint of φ(p) is the same as that of p, that the last meeting point with H_{n} is the same as that of p, and that the portion of the path after this last meeting point remains unchanged. Hence, by (4.8),

φ(p) ∈ N(μ μ μ_{σ(1,n)} + e ee_{σ(1,n)} + (K + n)u u u^{(n)} → λ λ λ)^{−} ,

with the u u u^{(n)} of section 4. Moreover, by (5.4) obviously we have

(5.6)  maj φ(p) = maj p .

It is easy to see that this definition again establishes an involution. Therefore, using (5.6) we obtain

(5.7)  \begin{matrix}w( & φ(p)) = q^{∑_{s=1}^{n} T (s,(σ(1,n))(s),u u u^{(n)},μ μ μ)}q^{maj(φ(p))} \\ = q^{∑_{s=1}^{n} T (s,σ(s),u u u,μ μ μ)+(n−1)(μ_{σ(1)}−σ(1))} \\ · q^{−(n−1)(μ_{σ(n)}−σ(n))+(n−1)(μ_{σ(n)}−σ(n))−(n−1)(μ_{σ(1)}−σ(1))} \\ · q^{(K+n)((n−1) \frac{1}{2} (2u_{n}+1−2u_{1}+1)−(n−1)u_{n}+1+(n−1)u_{1}−n)} \\ · q^{maj p} \\ = w(p) . \end{matrix}

To give an example, take n = 3, K = 2, μ μ μ = (1, −1, −1), λ λ λ = (3, 2, 1), σ = (123) (in cycle notation), and u u u = (1, 0, −1). Then μ μ μ_{σ} + e ee_{σ} + (K + n)u u u = (3, −2, −2). Consider the path p_{0} = ((3, −2, −2), 2233223). This path only touches the hyperplane H_{3}, which is given by x_{n} − x_{1} = −3 (cf. (2.3)). The meeting points are (3, 0, 0), (3, 1, 0), and (3, 2, 0), the last meeting point being (3, 2, 0). To apply the mapping φ, first we observe that

E((123), 2, (1, −1, −1), (1, 0, −1)) = −2 .

Hence, we have

φ(p_{0}) = (R_{3}(3, −2, −2), R_{3}^{2}(2233223)) = ((1, −2, 0), R_{3}^{2}(2233223)) .

Using Definition 2 (A) (e = 0, r = 3, f = 4), we obtain R_{3}(2233223) = 1223223, and by Definition 2 (B) (r = 4, f = 5) R_{3}(1223223) = 1222123. Hence, φ(p_{0}) = ((1, −2, 0), 1222123). Obviously, the final point of p_{0} again is (3, 2, 1). φ(p_{0}) meets H_{3} as the last hyperplane, just as p_{0} did. Again (3, 2, 0) is the last meeting point with H_{3} and after this point nothing was changed. Moreover, we have maj p_{0} = maj φ(p_{0}) = 4. Similarly, use of Definition 1 (B) (e = 3, k = 5) would give L_{3}(1222123) = 1223223, and by Definition 1 (A) (e = 0, k = 1, f = 4) we would get L_{3}(1223223) = 2233223. This establishes φ(φ(p_{0})) = p_{0}, which must be satisfied, since φ is an involution.

Summarizing, the map φ maps elements of the set in (4.2) onto elements of the set in (4.3) and vice versa. Since it is an involution it is a bijection. Moreover it is weight–preserving with respect to w. Therefore the equation which generalizes (4.4) reads

(5.8) _{∑_{σ even} ; u u u∈U_{n}}q^{∑_{s=1}^{n} T (s,σ(s),u u u,μ μ μ)}G(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ; q)^{−}

=_{∑_{σ odd} ; u u u∈U_{n}}q^{∑_{s=1}^{n} T (s,σ(s),u u u,μ μ μ)}G(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ; q)^{−} .

The q–analogue of (4.1) is MacMahon’s well–known result [1, Theorem 3.7, p. 42], which in our notation is

(5.9)  G(μ μ μ → λ λ λ; q) = [ \begin{matrix}|λ λ λ − μ μ μ| \\ λ λ λ − μ μ μ \end{matrix} ] .

Successive use of (5.8), (4.9), and (5.9) gives

(5.10)

G(μ μ μ → λ λ λ; q)^{+} = G(μ μ μ → λ λ λ; q) − G(μ μ μ → λ λ λ; q)^{−}
= G(μ μ μ → λ λ λ; q) − G(μ μ μ → λ λ λ; q)^{−}

+_{∑_{σ∈S_{n}} ; u u u∈U_{n}} sgn σ q^{∑_{s=1}^{n} T (s,σ(s),u u u,μ μ μ)}G(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ; q)^{−}

=_{∑_{σ∈S_{n}} ; u u u∈U_{n}} sgn σ q^{∑_{s=1}^{n} T (s,σ(s),u u u,μ μ μ)}G(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ; q)

=_{∑_{σ∈S_{n}} ; u u u∈U_{n}} sgn σ q^{∑_{s=1}^{n} T (s,σ(s),u u u,μ μ μ)} [\begin{matrix}|λ λ λ − μ μ μ| \\ λ λ λ − μ μ μ_{σ} − e ee_{σ} − (K + n)u u u \end{matrix}]

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

which exactly is the expression in Theorem 1.

6. An extension of Theorem 1. In this section we extend Theorem 1, which is a theorem about major counting, to other, major-like statistics. To motivate the following considerations, recall that MacMahon not only dealt with the major (i.e. greater) index but also with what he called the “lesser index” [5, p. 136]. This lesser index, which we denote by maj’, of a multiset permutation π = π_{1}π_{2} … π_{L} is defined by

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

While for the major index each j with π_{j} > π_{j+1} makes a contribution, for the lesser index it is each j with π_{j} < π_{j+1} which makes a contribution. One also could roughly say that taking the lesser index is nothing but taking the major index where the order 1 < 2 < ⋯ < n of the numbers {1, 2, …, n} has been changed into 1 > 2 > ⋯ > n. Having this idea in mind, it is also reasonable to consider other total orders of {1, 2, …, n} and to take major index with respect to these orders. Thus, for each n one obtains a set of n! different major variants, the original major index and the lesser index being only two of them.

To be more precise, we proceed as follows. Given a specific total order i_{1} < i_{2} < ⋯ < i_{n} of the set {1, 2, …, n}, let the permutation τ be defined by τ(i_{j}) := j, j = 1, 2, …, n. Then taking the major index of a multiset permutation π = π_{1}π_{2} … π_{L} with respect to the order i_{1} < i_{2} < ⋯ < i_{n} is just the same as maj(τ(π_{1})τ(π_{2}) … τ(π_{L})). This leads to the following definition.

Let τ be a fixed permutation, τ ∈ S_{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 = (μ μ μ, π) is defined by τ(p) = (μ μ μ, τ(π)). Now we introduce the following permutation-indexed statistics:

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

Obviously, maj_{id} is identical with the major index, while for τ_{0} given by τ_{0}(i) = n + 1 − i the statistics maj_{τ_{0}} coincides with MacMahon’s lesser index.

To give another example, take n = 3, τ_{1} = \binom{1 2 3}{2 3 1}, π_{1} = 1223213. This choice of τ_{1} corresponds to the total order 3 < 1 < 2. We have maj_{τ_{1}} π_{1} = 3 + 5 + 6 = 14.

The same idea as that which was used in the proof of Theorem 1 also serves to establish an analogous result for counting N(μ μ μ → λ λ λ)^{+} by maj_{τ}. In fact, the result for the generating function ∑ q^{maj_{τ} p} almost looks to be identical, except that the powers of q are changed according to the choice of τ.

Theorem 2. 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 (2.2) and (2.3), 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) + u_{s} ∑_{j=1}^{s−1} c(j)) ,

where c(j) = χ(τ(j) < τ(j+1)), and where 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. By τ(n + 1) here and in the sequel we mean τ(1). Analogous conventions will be assumed for n+1 appearing as a subscript: μ_{n+1} := μ_{1}, etc.

Sketch of proof. In analogy with (5.1) let the weight w_{τ} (p) of a path p ∈ N(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ) be defined by

(6.2)  w_{τ} (p) = q^{∑_{s=1}^{n} T_{τ} (s,σ(s),u u u,μ μ μ)}q^{maj_{τ} p} .

Let p ∈ N(μ μ μ_{σ} + e ee_{σ} + (K + n)u u u → λ λ λ)^{−} be a path which meets H_{j} as last hyperplane of those in (2.2) and (2.3). Suppose that there are mappings ψ_{j} which satisfy the following properties:

(1) ψ_{j} acts on paths which meet H_{j} as last hyperplane.

(2) If \overline{p} ∈ N(\overline{μ μ μ} → \overline{λ λ λ})^{−} meets H_{j} as last hyperplane, then ψ_{j}(\overline{p}) ∈ N(R_{j}(\overline{μ μ μ}) → \overline{λ λ λ})^{−} and ψ_{j}(\overline{p}) also meets H_{j} as last hyperplane.

(3) The action of ψ_{j} changes maj_{τ} according to

(6.3)  maj_{τ} ψ_{j}(\overline{p}) = \{ \begin{matrix}maj_{τ} \overline{p} − c(j)(\overline{μ}_{j} − \overline{μ}_{j+1} + 1) & 1 ≤ j ≤ n − 1 \\ maj_{τ} \overline{p} − c(n)(\overline{μ}_{n} − \overline{μ}_{1} + 1 + K) & j = n \end{matrix} ,

with c(j) = χ(τ(j) < τ(j + 1)).

(4) ψ_{j} is an involution.

Then simple calculations show that ψ_{j}(p) ∈ N(μ μ μ_{σ(j,j+1)}+e ee_{σ(j,j+1)}+(K+n)u u u^{(j)} → λ λ λ)^{−} with u u u^{(j)} being defined in section 4. Moreover, w_{τ} (ψ_{j}(p)) = w_{τ} (p). Let the mapping φ_{τ}, which acts on elements of the union of the sets in (4.2) and (4.3), be defined as follows: If an element of the union of the sets in (4.2) and (4.3) meets H_{j} as last hyperplane of those in (2.2) and (2.3), then the image of this path under application of φ_{τ} is given by applying ψ_{j} to this path. φ_{τ} is seen to be an involution, and hence a bijection between the sets in (4.2) and (4.3). Besides, it is weight-preserving with respect to w_{τ}. Computations which proceed analogously to those in (5.8)–(5.10) would complete the proof of Theorem 2.

It remains to construct those mappings ψ_{j}. The idea is as follows:

If τ(j) < τ(j +1) modify Definitions 1,2 of [4] such that L_{j} changes a single τ(j +1) into τ(j), R_{j} changes a single τ(j) into a τ(j + 1), and

R_{j} ∘ L_{j} = L_{j} ∘ R_{j} = id ,
maj L_{j}(π) = maj π − 1 ,
maj R_{j}(π) = maj π + 1 .

Then for a path p = (μ μ μ, π) which meets H_{j} as last hyperplane, ψ_{j} is given by

ψ_{j}(p) = (R_{j}(μ μ μ), L_{j}^{μ_{j}−μ_{j+1}+1+K·χ(j=n)}(τ(π))) .

If N is negative, by L_{j}^{N} we mean R_{j}^{−N}. Similarly, if τ(j) > τ(j+1), modify Definitions 3,4 of [4] such that \overline{L}_{j} changes a τ(j +1) into a τ(j), \overline{R}_{j} changes a τ(j) into a τ(j +1), and

\overline{R}_{j} ∘ \overline{L}_{j} = \overline{L}_{j} ∘ \overline{R}_{j} = id ,
maj \overline{L}_{j}(π) = maj \overline{R}_{j}(π) = maj π .

In this case, ψ_{j} is given by

ψ_{j}(p) = (R_{j}(μ μ μ), \overline{L}_{j}^{μ_{j}−μ_{j+1}+1+K·χ(j=n)}(τ(π))) ,

with the analogous convention concerning negative exponents of \overline{L}_{j}. □

Setting τ = τ_{0} in Theorem 2 yields the corresponding result for counting N(μ μ μ → λ λ λ)^{+} by the lesser index.

Corollary 1. 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 of the hyperplanes in (2.2) and (2.3), 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

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

The special case K > |λ λ λ − μ μ μ| has been proved previously in [4, Theorem 4].

References

1. G. E. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, (Addison–Wesley, Reading, 1976).

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

3. I. M. Gessel, D. Zeilberger, Random walk in a Weyl chamber, preprint, 1990.

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

5. P. A. MacMahon, Combinatory Analysis, Vol. 2, (Cambridge University Press, Cambridge, 1916; reprinted by Chelsea, New York, 1960).

6. D. Zeilberger, André’s reflection proof generalized to the many candidate ballot problem, Discrete Math. 44 (1983), 325–326.

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

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