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.
Reviewer: L.A.Székely (Columbia/South Carolina)
MSC:
| 05A15 | Exact enumeration problems, generating functions |
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: 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: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
