Abstract
We use the “first passage decomposition” methodology to study the area between various kinds of underdiagonal lattice paths and the main diagonal. This area is important because it is connected to the number of inversions in permutations and to the internal path length in various types of trees. We obtain the generating functions for the total area of all the lattice paths from the origin to the point (n, n). Since this method also determines the number of these paths, we are able to obtain exact results for the average area.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Barcucci, R. Pinzani, and R. Sprugnoli. The Motzkin family. Pure Mathematics and Applications, 2:249–279, 1991.
L. Carlitz. Sequences, paths, ballot numbers. Fibonacci Quart., 10:531–549, 1972.
L. Carlitz and J. Riordan. Two elements lattice permutation numbers and their q-generalization. Duke J. Math., 31:371–388, 1964.
M. P. Delest and J. M. Fédou. Enumeration of skew Ferrers diagrams. Discrete Mathematics, 112:65–79, 1993.
M. P. Delest and G. Viennot. Algebraic languages and polyominoes. Theoretical Computer Science, 34:169–206, 1984.
I. Dutour and J. M. Fédou. Grammaire d'objects. Technical Report 963, LaBRI, Université Bordeaux I, 1994.
W. Feller. An introduction to probability theory and its applications. Wiley, 1950.
J. Francon and X. G. Viennot. Permutation selon les pics, creux, doubles montees, doubles descentes, nombres d'Euler et nombres de Genocchi. Discrete Mathematics, 28:21–35, 1979.
R. D. Fray and D. P. Roselle. Weighted lattice paths. Pacific Journal of Mathematics, 37:85–96, 1971.
R. D. Fray and D. P. Roselle. On weighted lattice paths. Journal of Combinatorial Theory, series A, 14:21–29, 1973.
J. Fürlinger and J. Holfbauer. q-Catalan numbers. Journal of Combinatorial Theory, Series A, 40:248–264, 1985.
J. R. Goldman. Formal languages and enumeration. Journal of Combinatorial Theory, Series A, 24:318–338, 1978.
J. R. Goldman and T. Sundquist. Lattice path enumeration by formal schema. Advances in applied mathematics, 13:216–251, 1992.
E. Goodman and T. V. Narayana. Lattice paths with diagonal steps. Canad. Math. Bull., 12:847–855, 1969.
I. P. Goulden and D. M. Jackson. Combinatorial Enumeration. John Wiley & S., 1983.
B. R. Handa and S. G. Mohanty. Higher dimensional lattice paths with diagonal steps. Discrete Mathematics, 15:137–140, 1976.
D. E. Knuth. The art of computer programming. Vol. 1–3. Addison-Wesley, 1973.
J. Labelle and Y. Yeh. Dyck paths of knight moves. Discrete applied mathematics, 24:213–221, 1989.
J. Labelle and Y. Yeh. Generalized Dyck paths. Discrete mathematics, 82:1–6, 1990.
D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri. Lattice paths with steep and shallow steps. Technical Report 16, Dipartimento di Sistemi e Informatica, Università di Firenze, 1995.
D. Merlini, R. Sprugnoli, and M. C. Verri. Algebraic and combinatorial properties of simple, coloured walks. In Proceedings of CAAP'94, volume 787 of Lecture Notes in Computer Science, pages 218–233, 1994.
S. G. Mohanty and B. R. Handa. On lattice paths with several diagonal steps. Canad. Math. Bull., 11:537–545, 1968.
L. Moser and W. Zayachkowski. Lattice paths with diagonal steps. Scripta Math., 26:223–229, 1963.
D. G. Rogers and L. W. Shapiro. Deques, trees and lattice paths. Lectures Notes in Mathematics, 884:292–303, 1981.
V. K. Rohatgi. On lattice paths with diagonals steps. Canad. Math. Bull., 7:470–472, 1964.
M. P. Schützenberger. Context-free language and pushdown automata. Information and Control, 6:246–264, 1963.
L. Takács. Some asymptotic formulas for lattice paths. Journal of statistical planning and inference, 14:123–142, 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Merlini, D., Sprugnoli, R., Verri, M.C. (1996). The area determined by underdiagonal lattice paths. In: Kirchner, H. (eds) Trees in Algebra and Programming — CAAP '96. CAAP 1996. Lecture Notes in Computer Science, vol 1059. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61064-2_29
Download citation
DOI: https://doi.org/10.1007/3-540-61064-2_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61064-9
Online ISBN: 978-3-540-49944-2
eBook Packages: Springer Book Archive