{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T05:31:24Z","timestamp":1777527084621,"version":"3.51.4"},"reference-count":82,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,10,13]],"date-time":"2019-10-13T00:00:00Z","timestamp":1570924800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,13]],"date-time":"2019-10-13T00:00:00Z","timestamp":1570924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"FWF \u2014 Austrian Science Fund","doi-asserted-by":"crossref","award":["(SFB F50-03)"],"award-info":[{"award-number":["(SFB F50-03)"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002428","name":"FWF \u2014 Austrian Science Fund","doi-asserted-by":"crossref","award":["(P 28466-N35)"],"award-info":[{"award-number":["(P 28466-N35)"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>In this article we develop a <jats:italic>vectorial kernel method<\/jats:italic>\u2014a powerful method which solves in a unified framework all the problems related to the enumeration of words generated by a pushdown automaton. We apply it for the enumeration of lattice paths that avoid a fixed word (a <jats:italic>pattern<\/jats:italic>), or for counting the occurrences of a given pattern. We unify results from numerous articles concerning patterns like peaks, valleys, humps, etc., in Dyck and Motzkin paths. This refines the study by Banderier and Flajolet from 2002 on enumeration and asymptotics of lattice paths: we extend here their results to pattern-avoiding walks\/bridges\/meanders\/excursions. We show that the autocorrelation polynomial of this forbidden pattern, as introduced by Guibas and Odlyzko in 1981 in the context of rational languages, still plays a crucial role for our algebraic languages. <jats:italic>En passant<\/jats:italic>, our results give the enumeration of some classes of self-avoiding walks, and prove several conjectures from the On-Line Encyclopedia of Integer Sequences. Finally, we also give the trivariate generating function (length, final altitude, number of occurrences of the pattern\u00a0<jats:italic>p<\/jats:italic>), and we prove that the number of occurrences is normally distributed and linear with respect to the length of the walk: this is what Flajolet and Sedgewick call an instance of <jats:italic>Borges\u2019s theorem<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00453-019-00623-3","type":"journal-article","created":{"date-parts":[[2019,10,13]],"date-time":"2019-10-13T02:17:00Z","timestamp":1570933020000},"page":"386-428","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Analytic Combinatorics of Lattice Paths with Forbidden Patterns, the Vectorial Kernel Method, and Generating Functions for Pushdown Automata"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0689-0775","authenticated-orcid":false,"given":"Andrei","family":"Asinowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9789-7074","authenticated-orcid":false,"given":"Axel","family":"Bacher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0755-3022","authenticated-orcid":false,"given":"Cyril","family":"Banderier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2639-8227","authenticated-orcid":false,"given":"Bernhard","family":"Gittenberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,10,13]]},"reference":[{"key":"623_CR1","unstructured":"Asinowski, A., Bacher, A., Banderier, C., Gittenberger, B.: Analytic combinatorics of lattice paths with forbidden patterns: asymptotic aspects. In: 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 110, pp. 10.1\u201310.13 (2018)"},{"key":"623_CR2","doi-asserted-by":"crossref","unstructured":"Asinowski, A., Bacher, A., Banderier, C., Gittenberger, B.: Analytic combinatorics of lattice paths with forbidden patterns: enumerative aspects. In: Language and Automata Theory and Applications. LATA 2018, volume 10782 of Lecture Notes in Computer Science, pp. 195\u2013206. Springer (2018)","DOI":"10.1007\/978-3-319-77313-1_15"},{"key":"623_CR3","unstructured":"Asinowski, A., Bacher, A., Banderier, C., Gittenberger, B.: Pushdown automata, the vectorial kernel method, and underdetermined functional equations. In preparation (2019)"},{"issue":"1","key":"623_CR4","doi-asserted-by":"crossref","first-page":"R19","DOI":"10.37236\/937","volume":"14","author":"A Ayyer","year":"2007","unstructured":"Ayyer, A., Zeilberger, D.: The number of [old-time] basketball games with final score $$n:n$$ where the home team was never losing but also never ahead by more than $$w$$ points. Electron. J. Comb. 14(1), R19 (2007)","journal-title":"Electron. J. Comb."},{"key":"623_CR5","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.disc.2013.12.011","volume":"321","author":"A Bacher","year":"2014","unstructured":"Bacher, A., Bernini, A., Ferrari, L., Gunby, B., Pinzani, R., West, J.: The Dyck pattern poset. Discrete Math. 321, 12\u201323 (2014)","journal-title":"Discrete Math."},{"issue":"8","key":"623_CR6","doi-asserted-by":"crossref","first-page":"2365","DOI":"10.1016\/j.jcta.2011.06.001","volume":"118","author":"A Bacher","year":"2011","unstructured":"Bacher, A., Bousquet-M\u00e9lou, M.: Weakly directed self-avoiding walks. J. Comb. Theory Ser. A 118(8), 2365\u20132391 (2011)","journal-title":"J. Comb. Theory Ser. A"},{"key":"623_CR7","unstructured":"Banderier, C.: Combinatoire analytique des chemins et des cartes. Ph.D. thesis, Universit\u00e9 Paris\u00a0VI (2001)"},{"issue":"1","key":"623_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0963548314000728","volume":"24","author":"C Banderier","year":"2015","unstructured":"Banderier, C., Drmota, M.: Formulae and asymptotics for coefficients of algebraic functions. Comb. Probab. Comput. 24(1), 1\u201353 (2015)","journal-title":"Comb. Probab. Comput."},{"issue":"1\u20132","key":"623_CR9","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/S0304-3975(02)00007-5","volume":"281","author":"C Banderier","year":"2002","unstructured":"Banderier, C., Flajolet, P.: Basic analytic combinatorics of directed lattice paths. Theor. Comput. Sci. 281(1\u20132), 37\u201380 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"623_CR10","first-page":"345","volume":"AG","author":"C Banderier","year":"2006","unstructured":"Banderier, C., Gittenberger, B.: Analytic combinatorics of lattice paths: enumeration and asymptotics for the area. Discrete Math. Theor. Comput. Sci. Proc. AG, 345\u2013355 (2006)","journal-title":"Discrete Math. Theor. Comput. Sci. Proc."},{"key":"623_CR11","doi-asserted-by":"crossref","unstructured":"Banderier, C., Krattenthaler, C., Krinik, A., Kruchinin, D., Kruchinin, V., Nguyen, D., Wallner, M.: Explicit formulas for enumeration of lattice paths: basketball and the kernel method. In: Lattice Paths Combinatorics and Applications. Developments in Mathematics Series, vol. 58, pp. 78\u2013118. Springer (2019)","DOI":"10.1007\/978-3-030-11102-1_6"},{"key":"623_CR12","first-page":"35","volume":"AM","author":"C Banderier","year":"2010","unstructured":"Banderier, C., Nicod\u00e8me, P.: Bounded discrete walks. Discrete Math. Theor. Comput. Sci. AM, 35\u201348 (2010)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"1","key":"623_CR13","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.jspi.2005.02.004","volume":"135","author":"C Banderier","year":"2005","unstructured":"Banderier, C., Schwer, S.: Why Delannoy numbers? J. Stat. Plan. Inference 135(1), 40\u201354 (2005)","journal-title":"J. Stat. Plan. Inference"},{"key":"623_CR14","doi-asserted-by":"crossref","unstructured":"Banderier, C., Wallner, M.: The kernel method for lattice paths below a rational slope. In: Lattice Paths Combinatorics and Applications. Developments in Mathematics Series, vol. 58, pp. 119\u2013154. Springer (2019)","DOI":"10.1007\/978-3-030-11102-1_7"},{"issue":"3","key":"623_CR15","first-page":"13","volume":"17","author":"J-L Baril","year":"2016","unstructured":"Baril, J.-L.: Avoiding patterns in irreducible permutations. Discrete Math. Theor. Comput. Sci. 17(3), 13\u201330 (2016)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"4","key":"623_CR16","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1016\/j.disc.2018.12.005","volume":"342","author":"J-L Baril","year":"2019","unstructured":"Baril, J.-L., Kirgizov, S., Petrossian, A.: Enumeration of \u0141ukasiewicz paths modulo some patterns. Discrete Math. 342(4), 997\u20131005 (2019)","journal-title":"Discrete Math."},{"issue":"1\u20132","key":"623_CR17","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.ipl.2013.10.001","volume":"114","author":"J-L Baril","year":"2014","unstructured":"Baril, J.-L., Pallo, J.M.: Motzkin subposets and Motzkin geodesics in Tamari lattices. Inf. Process. Lett. 114(1\u20132), 31\u201337 (2014)","journal-title":"Inf. Process. Lett."},{"key":"623_CR18","unstructured":"Barry, P.: Continued fractions and transformations of integer sequences. J. Integer Seq. 12(7), Article 09.7.6 (2009)"},{"issue":"8","key":"623_CR19","doi-asserted-by":"crossref","first-page":"2611","DOI":"10.1093\/logcom\/exx018","volume":"27","author":"M Bendkowski","year":"2017","unstructured":"Bendkowski, M., Grygiel, K., Lescanne, P., Zaionc, M.: Combinatorics of $$\\lambda $$-terms: a natural approach. J. Log. Comput. 27(8), 2611\u20132630 (2017)","journal-title":"J. Log. Comput."},{"issue":"1","key":"623_CR20","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1112\/jlms\/jdv020","volume":"92","author":"D Bevan","year":"2015","unstructured":"Bevan, D.: Permutations avoiding 1324 and patterns in \u0141ukasiewicz paths. J. Lond. Math. Soc. (2) 92(1), 105\u2013122 (2015)","journal-title":"J. Lond. Math. Soc. (2)"},{"issue":"3","key":"623_CR21","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/s00026-010-0060-7","volume":"14","author":"M B\u00f3na","year":"2010","unstructured":"B\u00f3na, M., Knopfmacher, A.: On the probability that certain compositions have the same number of parts. Ann. Comb. 14(3), 291\u2013306 (2010)","journal-title":"Ann. Comb."},{"key":"623_CR22","doi-asserted-by":"crossref","unstructured":"Bousquet-M\u00e9lou, M.: Rational and algebraic series in combinatorial enumeration. In: International Congress of Mathematicians, vol. III, pp. 789\u2013826. EMS (2006)","DOI":"10.4171\/022-3\/40"},{"key":"623_CR23","doi-asserted-by":"crossref","unstructured":"Bousquet-M\u00e9lou, M.: Discrete excursions. S\u00e9m. Lothar. Comb. 57, Article B57d (2008)","DOI":"10.1016\/j.endm.2008.06.016"},{"issue":"5","key":"623_CR24","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1016\/j.jctb.2005.12.003","volume":"96","author":"M Bousquet-M\u00e9lou","year":"2006","unstructured":"Bousquet-M\u00e9lou, M., Jehanne, A.: Polynomial equations with one catalytic variable, algebraic series and map enumeration. J. Comb. Theory Ser. B 96(5), 623\u2013672 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1\u20134","key":"623_CR25","doi-asserted-by":"crossref","first-page":"127","DOI":"10.3233\/FI-2012-691","volume":"117","author":"C Brennan","year":"2012","unstructured":"Brennan, C., Mavhungu, S.: Visits to level $$r$$ by Dyck paths. Fund. Inform. 117(1\u20134), 127\u2013145 (2012)","journal-title":"Fund. Inform."},{"issue":"1\u20132","key":"623_CR26","first-page":"1","volume":"9","author":"F Carlson","year":"1921","unstructured":"Carlson, F.: \u00dcber Potenzreihen mit ganzzahligen Koeffizienten. Math. Z. 9(1\u20132), 1\u201313 (1921)","journal-title":"Math. Z."},{"key":"623_CR27","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/S0049-237X(08)72023-8","volume-title":"Computer Programming and Formal Systems","author":"N. Chomsky","year":"1963","unstructured":"Chomsky, N., Sch\u00fctzenberger, M.-P.: The algebraic theory of context-free languages. In: Computer Programming and Formal Systems, pp. 118\u2013161. North-Holland, Amsterdam (1963)"},{"key":"623_CR28","unstructured":"Dershowitz, N.: Nonleaf patterns in trees: protected nodes and Fine numbers. Submitted to J. Integer Seq. \narXiv:1908.04329\n\n (2019)"},{"issue":"1","key":"623_CR29","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1137\/070687475","volume":"23","author":"N Dershowitz","year":"2009","unstructured":"Dershowitz, N., Zaks, S.: More patterns in trees: up and down, young and old, odd and even. SIAM J. Discrete Math. 23(1), 447\u2013465 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"623_CR30","unstructured":"Deutsch, E.: Another type of lattice path. Am. Math. Mon. 107(4), 368\u2013370 (2000). Problem 10658, with solution by D. Callan, M. Beck, W. Bohm, R.F. McCoart, and GCHQ Problems Group"},{"key":"623_CR31","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.dam.2016.12.026","volume":"221","author":"E Deutsch","year":"2017","unstructured":"Deutsch, E., Elizalde, S.: Statistics on bargraphs viewed as cornerless Motzkin paths. Discrete Appl. Math. 221, 54\u201366 (2017)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"623_CR32","doi-asserted-by":"crossref","first-page":"1550","DOI":"10.1016\/j.jspi.2009.12.013","volume":"140","author":"E Deutsch","year":"2010","unstructured":"Deutsch, E., Munarini, E., Rinaldi, S.: Skew Dyck paths, area, and superdiagonal bargraphs. J. Stat. Plan. Inference 140(6), 1550\u20131562 (2010)","journal-title":"J. Stat. Plan. Inference"},{"issue":"3","key":"623_CR33","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1016\/S0012-365X(02)00341-2","volume":"256","author":"E Deutsch","year":"2002","unstructured":"Deutsch, E., Shapiro, L.W.: A bijection between ordered trees and 2-Motzkin paths and its many consequences. Discrete Math. 256(3), 655\u2013670 (2002)","journal-title":"Discrete Math."},{"key":"623_CR34","unstructured":"Dieudonn\u00e9, J.: Calcul infinit\u00e9simal, 2 edn. Hermann, Paris (1980). 1st edition in 1968: 479 pp, there is also an English translation of the 1st edition in 1971, 427 pp"},{"key":"623_CR35","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.dam.2011.08.018","volume":"160","author":"Y Ding","year":"2012","unstructured":"Ding, Y., Du, R.R.X.: Counting humps in Motzkin paths. Discrete Appl. Math. 160, 187\u2013191 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"623_CR36","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0012-365X(00)00150-3","volume":"225","author":"P Duchon","year":"2000","unstructured":"Duchon, P.: On the enumeration and generation of generalized Dyck words. Discrete Math. 225(1\u20133), 121\u2013135 (2000)","journal-title":"Discrete Math."},{"issue":"3","key":"623_CR37","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1016\/j.disc.2015.11.001","volume":"339","author":"M Dziemia\u0144czuk","year":"2016","unstructured":"Dziemia\u0144czuk, M.: On directed lattice paths with vertical steps. Discrete Math. 339(3), 1116\u20131139 (2016)","journal-title":"Discrete Math."},{"issue":"4","key":"623_CR38","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1111\/1467-9590.t01-1-00042","volume":"111","author":"S-P Eu","year":"2003","unstructured":"Eu, S.-P., Liu, S.-C., Yeh, Y.-N.: Dyck paths with peaks avoiding or restricted to a given set. Stud. Appl. Math. 111(4), 453\u2013465 (2003)","journal-title":"Stud. Appl. Math."},{"key":"623_CR39","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-7643-8797-6","volume-title":"Counting Surfaces. Progress in Mathematical Physics","author":"B Eynard","year":"2016","unstructured":"Eynard, B.: Counting Surfaces. Progress in Mathematical Physics, vol. 70. Springer, Berlin (2016). CRM Aisenstadt chair lectures"},{"key":"623_CR40","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-60001-2","volume-title":"Random Walks in the Quarter-Plane. Applications of Mathematics","author":"G Fayolle","year":"1999","unstructured":"Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random Walks in the Quarter-Plane. Applications of Mathematics, vol. 40. Springer, Berlin (1999)"},{"issue":"2","key":"623_CR41","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0012-365X(80)90050-3","volume":"32","author":"P Flajolet","year":"1980","unstructured":"Flajolet, P.: Combinatorial aspects of continued fractions. Discrete Math. 32(2), 125\u2013161 (1980)","journal-title":"Discrete Math."},{"key":"623_CR42","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"P Flajolet","year":"2009","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)"},{"issue":"1","key":"623_CR43","doi-asserted-by":"crossref","first-page":"R108","DOI":"10.37236\/832","volume":"15","author":"E Georgiadis","year":"2008","unstructured":"Georgiadis, E., Callan, D., Hou, Q.-H.: Circular digraph walks, $$k$$-balanced strings, lattice paths and Chebychev polynomials. Electron. J. Comb. 15(1), R108 (2008)","journal-title":"Electron. J. Comb."},{"issue":"3","key":"623_CR44","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0097-3165(80)90074-6","volume":"28","author":"IM Gessel","year":"1980","unstructured":"Gessel, I.M.: A factorization for formal Laurent series and lattice path enumeration. J. Comb. Theory Ser. A 28(3), 321\u2013337 (1980)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"2","key":"623_CR45","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0097-3165(81)90005-4","volume":"30","author":"LJ Guibas","year":"1981","unstructured":"Guibas, L.J., Odlyzko, A.M.: String overlaps, pattern matching, and nontransitive games. J. Comb. Theory Ser. A 30(2), 183\u2013208 (1981)","journal-title":"J. Comb. Theory Ser. A"},{"key":"623_CR46","unstructured":"Hackl, B., Heuberger, C., Prodinger, H.: Ascents in non-negative lattice paths. \narXiv:1801.02996\n\n (2018). (Long version of Counting ascents in generalized Dyck paths, in Proceedings of Analysis of Algorithms 2018.)"},{"issue":"1","key":"623_CR47","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.disc.2011.06.004","volume":"312","author":"IL Hofacker","year":"2012","unstructured":"Hofacker, I.L., Reidys, C.M., Stadler, P.F.: Symmetric circular matchings and RNA folding. Discrete Math. 312(1), 100\u2013112 (2012)","journal-title":"Discrete Math."},{"key":"623_CR48","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"2006","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley, Boston (2006). (First edition in 1979)","edition":"3"},{"issue":"2","key":"623_CR49","doi-asserted-by":"crossref","first-page":"P2.16","DOI":"10.37236\/7799","volume":"26","author":"V Irvine","year":"2019","unstructured":"Irvine, V., Melczer, S., Ruskey, F.: Vertically constrained Motzkin-like paths inspired by bobbin lace. Electron. J. Comb. 26(2), P2.16 (2019)","journal-title":"Electron. J. Comb."},{"issue":"1","key":"623_CR50","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s11538-007-9240-y","volume":"70","author":"EY Jin","year":"2008","unstructured":"Jin, E.Y., Qin, J., Reidys, C.M.: Combinatorics of RNA structures with pseudoknots. Bull. Math. Biol. 70(1), 45\u201367 (2008)","journal-title":"Bull. Math. Biol."},{"key":"623_CR51","series-title":"Texts and Monographs in Symbolic Computation","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-7091-0445-3","volume-title":"The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates","author":"M Kauers","year":"2011","unstructured":"Kauers, M., Paule, P.: The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Texts and Monographs in Symbolic Computation. Springer, Berlin (2011)"},{"key":"623_CR52","volume-title":"The Art of Computer Programming. Vol 1: Fundamental Algorithms","author":"DE Knuth","year":"1968","unstructured":"Knuth, D.E.: The Art of Computer Programming. Vol 1: Fundamental Algorithms. Addison-Wesley, Boston (1968)"},{"key":"623_CR53","doi-asserted-by":"crossref","unstructured":"Krattenthaler, C.: Lattice path enumeration. In: Handbook of Enumerative Combinatorics, pp. 589\u2013678. Discrete Math. Appl. (Boca Raton), CRC Press","DOI":"10.1201\/b18255-13"},{"issue":"1","key":"623_CR54","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0378-3758(86)90011-X","volume":"14","author":"G Kreweras","year":"1986","unstructured":"Kreweras, G., Moszkowski, P.: A new enumerative property of the Narayana numbers. J. Stat. Plan. Inference 14(1), 63\u201367 (1986)","journal-title":"J. Stat. Plan. Inference"},{"issue":"2","key":"623_CR55","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/S0195-6698(86)80040-3","volume":"7","author":"G Kreweras","year":"1986","unstructured":"Kreweras, G., Poupard, Y.: Subdivision des nombres de Narayana suivant deux param\u00e8tres suppl\u00e9mentaires. Eur. J. Comb. 7(2), 141\u2013149 (1986)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"623_CR56","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0012-365X(90)90039-K","volume":"82","author":"J Labelle","year":"1990","unstructured":"Labelle, J., Yeh, Y.-N.: Generalized Dyck paths. Discrete Math. 82(1), 1\u20136 (1990)","journal-title":"Discrete Math."},{"issue":"2","key":"623_CR57","doi-asserted-by":"crossref","first-page":"P2","DOI":"10.37236\/2181","volume":"19","author":"K Manes","year":"2012","unstructured":"Manes, K., Sapounakis, A., Tasoulas, I., Tsikouras, P.: Strings of length 3 in Grand-Dyck paths and the Chung\u2013Feller property. Electron. J. Comb. 19(2), P2 (2012)","journal-title":"Electron. J. Comb."},{"issue":"10","key":"623_CR58","doi-asserted-by":"crossref","first-page":"2557","DOI":"10.1016\/j.disc.2016.05.001","volume":"339","author":"K Manes","year":"2016","unstructured":"Manes, K., Sapounakis, A., Tasoulas, I., Tsikouras, P.: Equivalence classes of ballot paths modulo strings of length 2 and 3. Discrete Math. 339(10), 2557\u20132572 (2016)","journal-title":"Discrete Math."},{"key":"623_CR59","unstructured":"Mansour, T.: Statistics on Dyck paths. J. Integer Seq. 9, Article 06.1.5 (2006)"},{"issue":"13\u201314","key":"623_CR60","doi-asserted-by":"crossref","first-page":"2213","DOI":"10.1016\/j.dam.2013.03.007","volume":"161","author":"T Mansour","year":"2013","unstructured":"Mansour, T., Shattuck, M.: Counting humps and peaks in generalized Motzkin paths. Discrete Appl. Math. 161(13\u201314), 2213\u20132216 (2013)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"623_CR61","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0166-218X(98)00126-7","volume":"91","author":"D Merlini","year":"1999","unstructured":"Merlini, D., Rogers, D.G., Sprugnoli, R., Verri, M.C.: Underdiagonal lattice paths with unrestricted steps. Discrete Appl. Math. 91(1\u20133), 197\u2013213 (1999)","journal-title":"Discrete Appl. Math."},{"key":"623_CR62","volume-title":"Lattice Path Counting and Applications","author":"SG Mohanty","year":"1979","unstructured":"Mohanty, S.G.: Lattice Path Counting and Applications. Academic Press, Boston (1979)"},{"key":"623_CR63","unstructured":"Munarini, E., Salvi, N.Z.: Binary strings without zigzags. S\u00e9m. Lothar. Comb. 49, Article\u00a0B49h (2002)"},{"key":"623_CR64","first-page":"181","volume":"74","author":"H Niederhausen","year":"2010","unstructured":"Niederhausen, H., Sullivan, S.: Ballot paths avoiding depth zero patterns. J. Comb. Math. Comb. Comput. 74, 181\u2013192 (2010)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"8","key":"623_CR65","doi-asserted-by":"crossref","first-page":"2312","DOI":"10.1016\/j.jspi.2010.01.026","volume":"140","author":"H Niederhausen","year":"2010","unstructured":"Niederhausen, H., Sullivan, S.: Pattern avoiding ballot paths and finite operator calculus. J. Stat. Plan. Inference 140(8), 2312\u20132320 (2010)","journal-title":"J. Stat. Plan. Inference"},{"issue":"2","key":"623_CR66","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1515\/integ.2011.099","volume":"12","author":"H Niederhausen","year":"2012","unstructured":"Niederhausen, H., Sullivan, S.: Counting depth zero patterns in ballot paths. Integers 12(2), 215\u2013236 (2012)","journal-title":"Integers"},{"key":"623_CR67","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/j.aam.2019.01.005","volume":"105","author":"R Pan","year":"2019","unstructured":"Pan, R., Qiu, D., Remmel, J.: Counting consecutive pattern matches in $${{\\cal{S}}}_n(132)$$ and $${{\\cal{S}}}_n(123)$$. Adv. Appl. Math. 105, 130\u2013167 (2019)","journal-title":"Adv. Appl. Math."},{"key":"623_CR68","doi-asserted-by":"crossref","unstructured":"Pan, R., Remmel, J.B.: Paired patterns in lattices paths. In: Lattice Paths Combinatorics and Applications. Developments in Mathematics Series, vol. 58, pp. 382\u2013418. Springer (2019)","DOI":"10.1007\/978-3-030-11102-1_17"},{"issue":"11","key":"623_CR69","doi-asserted-by":"crossref","first-page":"2652","DOI":"10.1016\/j.disc.2016.04.024","volume":"339","author":"Y Park","year":"2016","unstructured":"Park, Y., Park, S.K.: Enumeration of generalized lattice paths by string types, peaks, and ascents. Discrete Math. 339(11), 2652\u20132659 (2016)","journal-title":"Discrete Math."},{"key":"623_CR70","doi-asserted-by":"crossref","unstructured":"Parviainen, R.: Lattice path enumeration of permutations with $$k$$ occurrences of the pattern 2\u201313. J. Integer Seq. 9(3), Article 06.3.2 (2006)","DOI":"10.37236\/1137"},{"key":"623_CR71","unstructured":"Qiu, D., Remmel, J.: Quadrant marked mesh patterns in 123-avoiding permutations. Discrete Math. Theor. Comput. Sci. 19(2), Paper No. 12 (2018)"},{"key":"623_CR72","unstructured":"Regev, A.: Identities for the number of standard Young tableaux in some $$(k,\\ell )$$-hooks. S\u00e9m. Lothar. Comb. 63, Article\u00a0B63c (2010)"},{"key":"623_CR73","unstructured":"Righi, C.: Number of \u201c$$udu$$\u201ds of a Dyck path and $$ad$$-nilpotent ideals of parabolic subalgebras of $$sl_{\\ell +1}({\\mathbb{C}})$$. S\u00e9m. Lothar. Comb. 59, Article\u00a0B59c (2008)"},{"issue":"2","key":"623_CR74","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/S0097-3165(75)80010-0","volume":"19","author":"J Riordan","year":"1975","unstructured":"Riordan, J.: Enumeration of plane trees by branches and endpoints. J. Comb. Theory Ser. A 19(2), 214\u2013222 (1975)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"23","key":"623_CR75","doi-asserted-by":"crossref","first-page":"2909","DOI":"10.1016\/j.disc.2007.03.005","volume":"307","author":"A Sapounakis","year":"2007","unstructured":"Sapounakis, A., Tasoulas, I., Tsikouras, P.: Counting strings in Dyck paths. Discrete Math. 307(23), 2909\u20132924 (2007)","journal-title":"Discrete Math."},{"key":"623_CR76","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/S0019-9958(63)90306-1","volume":"6","author":"M-P Sch\u00fctzenberger","year":"1963","unstructured":"Sch\u00fctzenberger, M.-P.: On context-free languages and push-down automata. Inf. Control 6, 246\u2013264 (1963)","journal-title":"Inf. Control"},{"key":"623_CR77","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0019-9958(64)90232-3","volume":"7","author":"M-P Sch\u00fctzenberger","year":"1964","unstructured":"Sch\u00fctzenberger, M.-P.: On the synchronizing properties of certain prefix codes. Inf. Control 7, 23\u201336 (1964)","journal-title":"Inf. Control"},{"key":"623_CR78","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139058520","volume-title":"Enumerative Combinatorics. Vol. 1. Cambridge Studies in Advanced Mathematics","author":"RP Stanley","year":"2011","unstructured":"Stanley, R.P.: Enumerative Combinatorics. Vol. 1. Cambridge Studies in Advanced Mathematics, vol. 49, 2nd edn. Cambridge University Press, Cambridge (2011)","edition":"2"},{"issue":"3","key":"623_CR79","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0012-365X(79)90033-5","volume":"26","author":"PR Stein","year":"1979","unstructured":"Stein, P.R., Waterman, M.S.: On some new sequences generalizing the Catalan and Motzkin numbers. Discrete Math. 26(3), 261\u2013272 (1979)","journal-title":"Discrete Math."},{"key":"623_CR80","unstructured":"Sulanke, R.A.: Objects counted by the central Delannoy numbers. J. Integer Seq. 6(1), Article 03.1.5 (2003)"},{"issue":"1\u20133","key":"623_CR81","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/j.disc.2004.07.002","volume":"287","author":"Y Sun","year":"2004","unstructured":"Sun, Y.: The statistic number of udu\u2019s in Dyck paths. Discrete Math. 287(1\u20133), 177\u2013186 (2004)","journal-title":"Discrete Math."},{"issue":"2","key":"623_CR82","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1016\/j.disc.2017.09.004","volume":"341","author":"Y Zhuang","year":"2018","unstructured":"Zhuang, Y.: A generalized Goulden\u2013Jackson cluster method and lattice path enumeration. Discrete Math. 341(2), 358\u2013379 (2018)","journal-title":"Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00623-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00623-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00623-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,11]],"date-time":"2020-10-11T23:15:49Z","timestamp":1602458149000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00623-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,13]]},"references-count":82,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["623"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00623-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,13]]},"assertion":[{"value":"1 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}