I. Introduction Gessel and Viennot's [16, 17] beautiful idea of interpreting tableaux as families of nonintersecting lattice paths is a very useful tool for obtaining determinantal ex- pressions for generating functions for various families of tableaux with a given shape. (Subsequently, Stembridge [41] widened this theory. He showed that generating func- tions for tableaux where the shape now is allowed to vary can frequently given in form of a Pfaffian.) What is done in this theory, is counting families of nonintersect- ing lattice paths by weights which depend on the position of the path's edges in the integer lattice Z 2 . (Z stands for the set of integers.) We in turn propose the counting of families of nonintersecting lattice paths by MacMahon's [32] major index and gen- eralizations of it. The original motivation of doing major counting of nonintersecting lattice paths lay in a problem of Choi and Gouyou-Beauchamps. In [7] they found a nice product formula for the number of tableaux with p odd rows, with the parts being bounded by n, and where the lengths of the rows are bounded by 2r. It was conjectured that there is also a simple product formula for the generating function of this family of tableaux. By a slight modification of Choi and Gouyou-Beauchamps' idea of proof, which is inspired by Desainte-Catherine and Viennot's [10] geometric interpretation of a variation of the celebrated Knuth correspondence [24, 6], in this paper it is shown that the computation of the generating function of the above family of tableaux can be solved by counting nonintersecting lattice paths with given start- ing and final points, which in addition do not cross the diagonal line x = y, by a variation of the major index. So we decided to systematically develop a theory of counting families of nonintersecting lattice paths by major index and generalizations of it, which we call strange major indices (cf. (4.0.4)-(4.0.4)). This major counting theory is developed quite analogously to the usual theory which encounters edge weights. The only difference is that for the major counting we have to assume that the starting points of the lattice paths lie on a line parallel to x -+- y = 0. Once this is done, we also obtain determinants involving g-binomials for the major and strange major generating functions for families of nonintersecting lattice paths with given starting and final points. Also here these determinants in special cases can be evaluated to result in simple products. However, the really significant parts of this paper consider nonintersecting paths which are bounded by x = y. This has no counterpart with edge weights. Only the number of such families of nonintersecting lattice paths has been previously considered [17, 10, 7]. Again we find determinantal expressions, though a little bit more complicated. And again, in special cases these determinants can be evaluated to result in nice product expressions. Applications of this theory do not only include the solution of the above tableaux problem. There are other tableaux problems which also can be treated that way. An interesting application of our major counting is to give an alternative proof for the Received by the editor November 20, 1993.
Previous Page Next Page