×

zbMATH — the first resource for mathematics

Underdiagonal lattice paths with unrestricted steps. (English) Zbl 0923.05003
The paper studies a generalization of Dyck paths, i.e. lattice paths in the plane composed of a set of unrestricted steps. An algorithm is introduced to obtain the generating function for the number of underdiagonal paths for a large class of path problems. The techniques of the paper use previous work of M. P. Schützenberger [Inf. Control 6, 246-264 (1963; Zbl 0123.12502)] and J. R. Goldman [J. Comb. Theory, Ser. A 24, 318-338 (1978; Zbl 0411.05010)] for making combinatorial decomposition based on context-free grammar, in order to obtain a recurrence relation.

MSC:
05A15 Exact enumeration problems, generating functions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bender, E.A., Asymptotic methods in enumeration, SIAM rev., 16, 485-515, (1974) · Zbl 0294.05002
[2] Feller, W., An introduction to probability theory and its applications, (1950), Wiley New York · Zbl 0039.13201
[3] Gessel, I.M., A factorization for formal Laurent series and lattice path enumeration, J. combin. theory ser. A, 28, 321-337, (1980)
[4] Goldman, J.R., Formal languages and enumeration, J. combin. theory ser. A, 24, 318-338, (1978) · Zbl 0411.05010
[5] Goldman, J.R.; Sundquist, T., Lattice path enumeration by formal schema, Adv. appl. math., 13, 216-251, (1992) · Zbl 0767.05008
[6] Labelle, J., Languages de Dyck généralisés, Ann. sci. math. Québec, 17, 1, 53-64, (1993) · Zbl 0795.05004
[7] Markushevich, A.I., Theory of functions of a complex variable, (1965), Prentice-Hall Englewood cliffs. NJ · Zbl 0135.12002
[8] Merlini, D.; Rogers, D.G.; Sprugnoli, R.; Verri, M.C., On some alternative characterizations of Riordan arrays, Canad. J. math., 49, 2, 301-320, (1997) · Zbl 0886.05013
[9] Rancy, G.N., Functional composition patterns and power series reversion, Trans. amer. math. soc., 94, 441-451, (1960) · Zbl 0131.01402
[10] Schützenberger, M.P., Context-free language and pushdown automata, Inform and control, 6, 246-264, (1963) · Zbl 0123.12502
[11] Sprugnoli, R., Riordan arrays and combinatorial sums, Discrete math., 132, 267-290, (1994) · Zbl 0814.05003
[12] Sprugnoli, R.; Verri, M.C., Asymptotics for Lagrange inversion, Pure math. appl., 5, 1, (1994) · Zbl 0816.05006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.