A remarkable formula for counting nonintersecting lattice paths in a ladder with respect to turns

Krattenthaler, C.; Prohaska, M.

doi:10.1090/S0002-9947-99-01884-X

A remarkable formula for counting nonintersecting lattice paths in a ladder with respect to turns
HTML articles powered by AMS MathViewer

by C. Krattenthaler and M. Prohaska PDF

Trans. Amer. Math. Soc. 351 (1999), 1015-1042 Request permission

Abstract:

We prove a formula, conjectured by Conca and Herzog, for the number of all families of nonintersecting lattice paths with certain starting and end points in a region that is bounded by an upper ladder. Thus we are able to compute explicitly the Hilbert series for certain one-sided ladder determinantal rings.

References

Shreeram S. Abhyankar, Enumerative combinatorics of Young tableaux, Monographs and Textbooks in Pure and Applied Mathematics, vol. 115, Marcel Dekker, Inc., New York, 1988. MR 926272
Shreeram Abhyankar and Devadatta M. Kulkarni, On Hilbertian ideals, Linear Algebra Appl. 116 (1989), 53–79. MR 989717, DOI 10.1016/0024-3795(89)90398-4
Winfried Bruns and Jürgen Herzog, On the computation of $a$-invariants, Manuscripta Math. 77 (1992), no. 2-3, 201–213. MR 1188581, DOI 10.1007/BF02567054
Winfried Bruns and Jürgen Herzog, Cohen-Macaulay rings, Cambridge Studies in Advanced Mathematics, vol. 39, Cambridge University Press, Cambridge, 1993. MR 1251956
Aldo Conca, Ladder determinantal rings, J. Pure Appl. Algebra 98 (1995), no. 2, 119–134. MR 1319965, DOI 10.1016/0022-4049(94)00039-L
Aldo Conca and Jürgen Herzog, On the Hilbert function of determinantal rings and their canonical module, Proc. Amer. Math. Soc. 122 (1994), no. 3, 677–681. MR 1213858, DOI 10.1090/S0002-9939-1994-1213858-0
Sudhir R. Ghorpade, Abhyankar’s work on Young tableaux and some recent developments, Algebraic geometry and its applications (West Lafayette, IN, 1990) Springer, New York, 1994, pp. 215–249. MR 1272033
Sudhir R. Ghorpade, Young bitableaux, lattice paths and Hilbert functions, J. Statist. Plann. Inference 54 (1996), no. 1, 55–66. MR 1406731, DOI 10.1016/0378-3758(95)00156-5
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1989. A foundation for computer science. MR 1001562
Jürgen Herzog and Ngô Viêt Trung, Gröbner bases and multiplicity of determinantal and Pfaffian ideals, Adv. Math. 96 (1992), no. 1, 1–37. MR 1185786, DOI 10.1016/0001-8708(92)90050-U
J. Horn, Über eine hypergeometrische Funktion zweier Veränderlichen, Monatsh. Math. Phys. 47 (1939), 359–379 (German). MR 91, DOI 10.1007/BF01695508
Christian Krattenthaler, Generating functions for plane partitions of a given shape, Manuscripta Math. 69 (1990), no. 2, 173–201. MR 1072987, DOI 10.1007/BF02567918
Peter B. Gibbons and Rudolf Mathon, The use of hill-climbing to construct orthogonal Steiner triple systems, J. Combin. Des. 1 (1993), no. 1, 27–50. MR 1303522, DOI 10.1002/jcd.3180010105
C. Krattenthaler, Counting nonintersecting lattice paths with turns, Sém. Lothar. Combin. 34 (1995), Art. B34i, approx. 17. MR 1399756
C. Krattenthaler, Non-crossing two-rowed arrays, in preparation.
C. Krattenthaler and S. G. Mohanty, On lattice path counting by major index and descents, European J. Combin. 14 (1993), no. 1, 43–51. MR 1197475, DOI 10.1006/eujc.1993.1007
C. Krattenthaler and S. G. Mohanty, Counting tableaux with row and column bounds, Discrete Math. 139 (1995), no. 1-3, 273–285. Formal power series and algebraic combinatorics (Montreal, PQ, 1992). MR 1336843, DOI 10.1016/0012-365X(94)00136-7
Devadatta M. Kulkarni, Hilbert polynomial of a certain ladder-determinantal ideal, J. Algebraic Combin. 2 (1993), no. 1, 57–71. MR 1210402, DOI 10.1023/A:1022428731241
Devadatta M. Kulkarni, Counting of paths and coefficients of the Hilbert polynomial of a determinantal ideal, Discrete Math. 154 (1996), no. 1-3, 141–151. MR 1395454, DOI 10.1016/0012-365X(94)00345-J
I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR 1354144
M. R. Modak, Combinatorial meaning of the coefficients of a Hilbert polynomial, Proc. Indian Acad. Sci. Math. Sci. 102 (1992), no. 2, 93–123. MR 1195735, DOI 10.1007/BF02836782
Bruce E. Sagan, The symmetric group, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991. Representations, combinatorial algorithms, and symmetric functions. MR 1093239
G. Viennot, Une forme géométrique de la correspondance de Robinson-Schensted, Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976) Lecture Notes in Math., Vol. 579, Springer, Berlin, 1977, pp. 29–58 (French). MR 0470059