Dyck path enumeration. (English) Zbl 0932.05006
Dyck paths of semilength \(n\) are paths from (0, 0) to \((2n,0)\) with steps (1, 1) and \((1,-1)\) which lie on or above the \(x\)-axis. The paper gives a systematic treatment to the enumeration of Dyck paths according to semilength and one more statistics. Many known and some new facts are proved, mostly using generating functions and Lagrange inversion. The elementary technique presented, which is an alternative of the closely related Schützenberger methodology, can also be applied to Motzkin paths, Schröder paths, noncrossing partitions, ordered trees, to certain classes of polyominoes, and probably to many other problems.
Reviewer: L.A.Székely (Columbia/South Carolina)
Keywords:
Catalan numbers; Narayana numbers; Dyck paths; enumeration; generating functions; Lagrange inversion; Motzkin paths; Schröder paths; noncrossing partitions; ordered trees; polyominoesSoftware:
OEISOnline Encyclopedia of Integer Sequences:
Binomial coefficient C(2n+1, n-1).Catalan triangle A009766 transposed.
Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having k ddu’s [here u = (1,1) and d = (1,-1)].
Triangle read by rows: number of Dyck paths of semilength n with k peaks after the first return (0 <= k < n).
Triangle of Dyck paths counted by number of long interior inclines.
References:
| [1] | Benchekroun, S.; Moszkowski, P., A new bijection between ordered trees and legal bracketings, European J. Combin., 17, 605-611 (1996) · Zbl 0863.05005 |
| [2] | Bender, E. A., Asymptotic methods in enumeration, SIAM Rev., 16, 485-515 (1974) · Zbl 0294.05002 |
| [3] | Bousquet-Mélou, M., Codage des polyominos convexes et équations pour l’énumération suivant l’aire, Discrete Appl. Math., 48, 21-43 (1994) · Zbl 0788.05020 |
| [4] | I’a. Bromwich, T. J., An Introduction to the Theory of Infinite Series (1959), Macmillan: Macmillan London · JFM 39.0306.02 |
| [5] | Chen, C.-C.; Koh, K.-M., Principles and Techniques in Combinatorics (1992), World Scientific: World Scientific Singapore · Zbl 0786.05002 |
| [6] | Comtet, L., Advanced Combinatorics (1974), Reidel: Reidel Dordrecht · Zbl 0283.05001 |
| [7] | Dasarathy, B.; Yang, C., A transformation on ordered trees, Computer J., 23, 161-164 (1980) · Zbl 0432.68046 |
| [8] | Delest, M. P.; Dubernard, J. P.; Dutour, I., Polyominos parallelogrammes, coins et mots de Motzkin, (Actes 31e Séminaire Lotharingien (1994), Publ. I.R.M.A: Publ. I.R.M.A Strasbourg), 29-49 · Zbl 0978.05515 |
| [9] | Delest, M. P.; Fedou, J. M., Enumeration of skew Ferrers diagrams, Discrete Math., 112, 65-79 (1993) · Zbl 0778.05002 |
| [10] | Delest, M. P.; Gouyou-Beauchamps, D.; Vauquelin, B., Enumeration of parallelogram polyominoes with given bond and site perimeter, Graphs Combin., 3, 325-339 (1987) · Zbl 0651.05027 |
| [11] | Delest, M. P.; Viennot, G., Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci., 34, 169-206 (1984) · Zbl 0985.68516 |
| [12] | Dershowitz, N.; Zaks, S., Enumerations of ordered trees, Discrete Math., 31, 9-28 (1980) · Zbl 0443.05049 |
| [13] | Dershowitz, N.; Zaks, S., Applied Tree Enumerations, (Lecture Notes in Computer Science, vol. 112 (1981), Springer: Springer Berlin), 180-193 · Zbl 0462.68038 |
| [14] | Deutsch, E., Discrete Math., 187, 297 (1998), for the omitted Fig. 1 · Zbl 0890.05005 |
| [16] | Dobrow, R. P.; Fill, J. A., On the Markov chain for the move-to-root rule for binary search trees, Ann. Appl. Probab., 5, 1-19 (1995) · Zbl 0822.60058 |
| [17] | Edelman, P. H., Chain enumeration and non-crossing partitions, Discrete Math., 31, 171-180 (1980) · Zbl 0443.05011 |
| [18] | Eğecioğlu, Ö., The parity of the Catalan numbers via lattice paths, Fibonacci Quart., 21, 65-66 (1983) · Zbl 0502.05005 |
| [19] | Fedou, J.-M., Grammaire et \(q- énumérations\) de polyominos, (Thèse (1989), Univ. Bordeaux I) |
| [20] | Fine, T., Extrapolation when very little is known about the source, Inform. Control, 16, 331-359 (1970) · Zbl 0205.44003 |
| [21] | Flajolet, P.; Sedgewick, R., Analytic Combinatorics, (Book in preparation (1998)), (Individual chapters are available as INRIA Research Reports 1888, pp. 2026, 2376, 2956, 3162.) |
| [22] | Gessel, I. M.; Stanley, R. P., Algebraic enumeration, (Graham, R.; Grötschel, M.; Lovász, L., Handbook of Combinatorics, vol. II (1995), Elsevier: Elsevier Amsterdam), 1021-1061 · Zbl 0853.05002 |
| [23] | Gould, H. W., Research Bibliography of Two Special Sequences (1977), Combinatorial Research Institute: Combinatorial Research Institute Morgantown, West Virginia · Zbl 0226.10002 |
| [24] | Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), Wiley: Wiley New York · Zbl 0519.05001 |
| [25] | Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0836.00001 |
| [26] | Knuth, D. E., (The Art of Computer Programming, vol. I. Fundamental Algorithms (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0302.68010 |
| [27] | Kreweras, G., Sur les éventails de segments, Cahiers du B.U.R.O., 15, 3-41 (1970) |
| [28] | Kreweras, G., Sur les partitions non croisées d’un cycle, Discrete Math., 1, 333-350 (1972) · Zbl 0231.05014 |
| [29] | Kreweras, G., Joint distributions of three descriptive parameters of bridges, (Lecture Notes in Mathematics, vol. 1234 (1986), Springer: Springer Berlin), 177-191 · Zbl 0612.05012 |
| [30] | Kreweras, G.; Moszkowski, P., A new enumerative property of the Narayana numbers, J. Statist. Plann. Inference, 14, 63-67 (1986) · Zbl 0601.05005 |
| [31] | Kreweras, G.; Poupard, Y., Subdivision des nombres de Narayana suivant deux paramètres supplémentaires, Europ. J. Combin., 7, 141-149 (1986) · Zbl 0647.05007 |
| [32] | Kuchinski, M. J., Catalan structures and correspondences, (M.S. Thesis (1977), West Virginia University: West Virginia University Morgantown, WV) · Zbl 0368.05003 |
| [33] | Lalanne, J. C., Une involution sur les chemins de Dyck, European J. Combin., 13, 477-487 (1992) · Zbl 0764.05020 |
| [34] | Lalanne, J. C., Sur une involution sur les chemins de Dyck, Theoret. Comput. Sci., 117, 203-215 (1993) · Zbl 0792.05003 |
| [35] | Meir, A.; Moon, J. W., Path edge-covering constants for certain families of trees, Utilitas Math., 14, 313-333 (1978) · Zbl 0423.05011 |
| [36] | Moon, J. W., Some enumeration problems for similarity relations, Discrete Math., 26, 251-260 (1979) · Zbl 0409.05007 |
| [37] | Narayana, T. V., A partial order and its applications to probability, Sankhya, 21, 91-98 (1959) · Zbl 0168.39202 |
| [38] | Pólya, G., On picture-writing, Amer. Math. Monthly, 63, 689-697 (1956) · Zbl 0074.25005 |
| [39] | Prodinger, H., A correspondence between ordered trees and noncrossing partitions, Discrete Math., 46, 205-206 (1983) · Zbl 0514.05008 |
| [40] | Rey, J. G., Problem 2070, Crux Mathematicorum, 22, 6, 279-281 (1996) |
| [41] | Rogers, D. G., Similarity relations on finite ordered sets, J. Combin. Theory Ser. A, 23, 88-98 (1977) · Zbl 0366.06001 |
| [42] | Rogers, D. G.; Shapiro, L. W., Deques, trees and lattice paths, (Lecture Notes in Mathematics, vol. 884 (1981), Springer: Springer Berlin), 293-303 · Zbl 0469.05005 |
| [43] | Schützenberger, M. P., On context-free languages and push-down automata, Information and Control, 6, 246-264 (1963) · Zbl 0123.12502 |
| [44] | Schützenberger, M. P., Certain elementary families of automata, (Proc. Symp. on Mathematical Theory of Automata. Proc. Symp. on Mathematical Theory of Automata, Polytechnic Institute of Brooklyn, 24-26 April 1962 (1963), Polytechnic Press: Polytechnic Press Brooklyn, NY), 139-153 · Zbl 0221.94080 |
| [45] | Sedgewick, R.; Flajolet, P., An Introduction to the Analysis of Algorithms (1996), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0841.68059 |
| [46] | Shapiro, L. W., A Catalan triangle, Discrete Math., 14, 83-90 (1976) · Zbl 0323.05004 |
| [47] | Shapiro, L. W., A short proof of an identity of Touchard’s concerning Catalan numbers, J. Combin. Theory Ser. A, 20, 375-376 (1976) · Zbl 0337.05012 |
| [48] | Simion, R., Combinatorial statistics on non-crossing partitions, J. Combin. Theory Ser. A, 66, 270-301 (1994) · Zbl 0803.05003 |
| [49] | Simion, R.; Ullman, D., On the structure of the lattice of noncrossing partitions, Discrete Math., 98, 193-206 (1991) · Zbl 0760.05004 |
| [50] | Sloane, N. J.A.; Plouffe, S., The Encyclopedia of Integer Sequences (1995), Academic Press: Academic Press San Diego · Zbl 0845.11001 |
| [51] | Stanley, R. P., Generating functions, (Rota, G.-C., Studies in Combinatorics (1978), The Mathematical Association of America: The Mathematical Association of America Washington), 100-141 |
| [53] | Stanton, D.; White, D., Constructive Combinatorics (1986), Springer: Springer New York · Zbl 0595.05002 |
| [54] | Strehl, V., A note on similarity relations, Discrete Math., 19, 99-101 (1977) · Zbl 0369.05005 |
| [55] | Sulanke, R. A., Catalan path statistics having the Narayana distribution, Discrete Math., 180, 369-389 (1998) · Zbl 0896.05002 |
| [56] | Sulanke, R. A., Constraint sensitive Catalan path statistics having the Narayana distribution, Discrete Math., 204, 397-414 (1999), (this Vol.) · Zbl 0936.05004 |
| [57] | Touchard, J., Sur certaines équations fonctionnelles, (Proc. Internat. Math. Congress, Toronto, 1924, vol. 1 (1928), University of Toronto Press: University of Toronto Press Toronto), 465-472 · JFM 54.0440.03 |
| [58] | Vaillé, J., Une bijection explicative de plusieurs propriétés remarquables des ponts, European J. Combin., 18, 117-124 (1997) · Zbl 0866.05005 |
| [59] | Wilf, H. S., generatingfunctionology (1994), Academic Press: Academic Press New York · Zbl 0831.05001 |
| [60] | Zeilberger, D., Six études in generating functions, Internat. J. Computer Math., 29, 201-215 (1989) · Zbl 0689.05003 |
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.
