II. Definitions and Preliminaries 2.1. Definitions and notation. In this paper we always consider lattice paths in the plane consisting of unit horizontal and vertical steps in the positive direction. In the sequel we shall call them paths for short. Any path in a natural way corresponds to a multiset permutation consisting of l's and 2's. Let P be a path from A = (Ai, A2) to £ = (Ei,E2). Later we frequently abbreviate the fact that a path P goes from A to 8 by P : A — S. P may be represented by a pair (A,7r), where A is the starting point of P and 7r = ^ ^ 2 .. . irEi+E2-Ai-A2i where 7Tj = 1 if the z'th step in the path P is a horizontal one and 7r,- = 2 if the z'th step in the path P is a vertical one. n is a multiset permutation consisting of E\ — A\ entries of 1 and E2 — A2 entries of 2. For example, the path P0 in Figure 1 is represented by ((1, - 1 ) , 221221112122). Of course, this representation of paths is unique. Hence, we may identify each path with its representation. • • • f m • » i • • • • • • Figure 1 The major index (or "greater index") of a multiset permutation TT = TTI7r2 .. . 7rn, 7Ti EN (set of positive integers), is defined by n - l maj TT = ^ i ' X(*% ^i+i) i=i where x is ^ n e usual truth function, x(A) — 1 if A is true, and x(A) — 0 otherwise. Given a path P — (A, 7r), we extend the major index to P by defining maj P := maj 7r. For our path in Figure 1 we have maj PQ = 2 + 5 + 9 = 16. By definition each pair 21 that occurs in a multiset permutation 7r, and only these, makes a contribution to the major index of TT. Given a path P = (^4,7r), the occurence of 21 in 7r means that a vertical step is followed by a horizontal one. The point which is the end point of this vertical step (and at the same time the starting point of this horizontal step) will be called a North-East corner of the path P. The North-East corners of our path in Figure 1 are (1,1), (2,3), and (5,4). By the above consideration we see that only North-East corners of a path make a contribution to the major index. Besides, the contribution of the North-East corner (a, b) is the number of steps from 4

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 1995 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.