Document Open Access Logo

Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem

Authors Andrei Asinowski , Axel Bacher , Cyril Banderier , Bernhard Gittenberger

PDF
Thumbnail PDF

File

LIPIcs.AofA.2018.10.pdf
  • Filesize: 0.7 MB
  • 14 pages

Document Identifiers

Author Details

Andrei Asinowski
  • Technische Universität Wien, Institut für Diskrete Mathematik und Geometrie, https://dmg.tuwien.ac.at/asinowski/
Axel Bacher
  • Université Paris 13, LIPN, UMR CNRS 7030, http://lipn.univ-paris13.fr/~bacher
Cyril Banderier
  • Université Paris 13, LIPN, UMR CNRS 7030, http://lipn.univ-paris13.fr/~banderier
Bernhard Gittenberger
  • Technische Universität Wien, Institut für Diskrete Mathematik und Geometrie, https://dmg.tuwien.ac.at/gittenberger/

Funding

This work was partially funded by the Austrian Science Fund (FWF) project SFB F50 "Algorithmic and Enumerative Combinatorics".

Cite As Get BibTex

Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger. Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.AofA.2018.10

Abstract

In a companion article dedicated to the enumeration aspects, we showed how to obtain closed form formulas for the generating functions of walks, bridges, meanders, and excursions avoiding any fixed word (a pattern p). The autocorrelation polynomial of this forbidden pattern p (as introduced by Guibas and Odlyzko in 1981, in the context of regular expressions) plays a crucial role. In this article, we get the asymptotics of these walks. We also introduce a trivariate generating function (length, final altitude, number of occurrences of p), for which we derive a closed form. We prove that the number of occurrences of p is normally distributed: This is what Flajolet and Sedgewick call an instance of Borges's theorem.
We thus extend and refine the study by Banderier and Flajolet in 2002 on lattice paths, and we unify several dozens of articles which investigated patterns like peaks, valleys, humps, etc., in Dyck and Motzkin paths. Our approach relies on methods of analytic combinatorics, and on a matricial generalization of the kernel method. The situation is much more involved than in the Banderier-Flajolet work: forbidden patterns lead to a wider zoology of asymptotic behaviours, and we classify them according to the geometry of a Newton polygon associated with these constrained walks, and we analyse what are the universal phenomena common to all these models of lattice paths avoiding a pattern.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Generating functions
  • Mathematics of computing → Distribution functions
  • Theory of computation → Random walks and Markov chains
  • Theory of computation → Grammars and context-free languages
Keywords
  • Lattice paths
  • pattern avoidance
  • finite automata
  • context-free languages
  • autocorrelation
  • generating function
  • kernel method
  • asymptotic analysis
  • Gaussian limit law

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger. Analytic combinatorics of lattice paths with forbidden patterns: enumerative aspects. In S. Klein, C. Martín-Vide, and D. Shapira, editors, Language and Automata Theory and Applications. LATA 2018, volume 10782 of Lecture Notes in Computer Science, pages 195-206. Springer, 2018. URL: http://dx.doi.org/10.1007/978-3-319-77313-1_15.
  2. Axel Bacher and Mireille Bousquet-Mélou. Weakly directed self-avoiding walks. Journal of Combinatorial Theory, Series A, 118(8):2365-2391, 2011. URL: http://dx.doi.org/10.1016/j.jcta.2011.06.001.
  3. Cyril Banderier. Combinatoire analytique des chemins et des cartes. Ph.D. thesis, Université Paris VI, 2001. URL: https://lipn.univ-paris13.fr/~banderier/Papers/these.pdf.
  4. Cyril Banderier and Michael Drmota. Formulae and asymptotics for coefficients of algebraic functions. Combinatorics, Probability and Computing, 24(1):1-53, 2015. URL: http://dx.doi.org/10.1017/S0963548314000728.
  5. Cyril Banderier and Philippe Flajolet. Basic analytic combinatorics of directed lattice paths. Theoretical Computer Science, 281(1-2):37-80, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(02)00007-5.
  6. Cyril Banderier and Bernhard Gittenberger. Analytic combinatorics of lattice paths: enumeration and asymptotics for the area. Discrete Math. Theor. Comput. Sci. Proc., AG:345-355, 2006. URL: https://hal.inria.fr/hal-01184683/document.
  7. Cyril Banderier and Pierre Nicodème. Bounded discrete walks. Discrete Math. Theor. Comput. Sci., AM:35-48, 2010. URL: https://dmtcs.episciences.org/2792/pdf.
  8. Cyril Banderier and Michael Wallner. The kernel method for lattice paths below a rational slope. In Lattice paths combinatorics and applications, Developments in Mathematics Series. Springer, 2018. To appear. URL: https://arxiv.org/abs/1606.08412.
  9. Jean-Luc Baril and Armen Petrossian. Equivalence classes of Motzkin paths modulo a pattern of length at most two. J. Integer Seq., 18(11):Article 15.7.1, 2015. URL: https://cs.uwaterloo.ca/journals/JIS/VOL18/Baril/baril3.pdf.
  10. Antonio Bernini, Luca Ferrari, Renzo Pinzani, and Julian West. Pattern-avoiding Dyck paths. Discrete Math. Theor. Comput. Sci. Proc., pages 683-694, 2013. URL: https://dmtcs.episciences.org/2334/pdf.
  11. Mireille Bousquet-Mélou. Rational and algebraic series in combinatorial enumeration. In International Congress of Mathematicians. Vol. III, pages 789-826. EMS, 2006. URL: https://hal.archives-ouvertes.fr/file/index/docid/277255/filename/icm.pdf.
  12. Mireille Bousquet-Mélou and Arnaud Jehanne. Polynomial equations with one catalytic variable, algebraic series and map enumeration. Journal of Combinatorial Theory. Series B, 96(5):623-672, 2006. URL: http://dx.doi.org/10.1016/j.jctb.2005.12.003.
  13. Charlotte Brennan and Simon Mavhungu. Visits to level r by Dyck paths. Fund. Inform., 117(1-4):127-145, 2012. URL: https://www.researchgate.net/profile/Charlotte_Brennan/publication/264970113_Visits_to_Level_r_by_Dyck_Paths/links/53fdbf460cf22f21c2f83297/Visits-to-Level-r-by-Dyck-Paths.pdf.
  14. Fritz Carlson. Über Potenzreihen mit ganzzahligen Koeffizienten. Math. Z., 9(1-2):1-13, 1921. URL: http://dx.doi.org/10.1007/BF01378331.
  15. Noam Chomsky and Marcel-Paul Schützenberger. The algebraic theory of context-free languages. In Computer programming and formal systems, pages 118-161. North-Holland, Amsterdam, 1963. Google Scholar
  16. Nachum Dershowitz and Shmuel Zaks. More patterns in trees: up and down, young and old, odd and even. SIAM J. Discrete Math., 23(1):447-465, 2008/09. URL: http://dx.doi.org/10.1137/070687475.
  17. Emeric Deutsch and Louis W. Shapiro. A bijection between ordered trees and 2-Motzkin paths and its many consequences. Discrete Math., 256(3):655-670, 2002. URL: http://dx.doi.org/10.1016/S0012-365X(02)00341-2.
  18. Jean Dieudonné. Calcul infinitésimal. Hermann, Paris, 2 edition, 1980. 1st ed. in 1968: 479pp., there is also an English translation of the 1st ed. in 1971, 427pp. Google Scholar
  19. Yun Ding and Rosena R. X. Du. Counting humps in Motzkin paths. Discrete Appl. Math., 160(1-2):187-191, 2012. URL: http://dx.doi.org/10.1016/j.dam.2011.08.018.
  20. Philippe Duchon. On the enumeration and generation of generalized Dyck words. Discrete Mathematics, 225(1-3):121-135, 2000. URL: http://dx.doi.org/10.1016/S0012-365X(00)00150-3.
  21. Sen-Peng Eu, Shu-Chung Liu, and Yeong-Nan Yeh. Dyck paths with peaks avoiding or restricted to a given set. Stud. Appl. Math., 111(4):453-465, 2003. URL: http://dx.doi.org/10.1111/1467-9590.t01-1-00042.
  22. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. URL: http://algo.inria.fr/flajolet/Publications/book.pdf.
  23. Leonidas J. Guibas and Andrew M. Odlyzko. String overlaps, pattern matching, and nontransitive games. J. Combin. Theory Ser. A, 30(2):183-208, 1981. URL: http://dx.doi.org/10.1016/0097-3165(81)90005-4.
  24. John E. Hopcroft, Raghavan Motwani, and Jeffrey D. Ullman. Introduction to automata theory, languages, and computation. Pearson, 3rd edition, 2006. (First edition by Addison-Wesley in 1979). URL: http://infolab.stanford.edu/~ullman/ialc.html.
  25. Jacques Labelle and Yeong Nan Yeh. Generalized Dyck paths. Discrete Mathematics, 82(1):1-6, 1990. URL: http://dx.doi.org/10.1016/0012-365X(90)90039-K.
  26. Kostas Manes, Aristidis Sapounakis, Ioannis Tasoulas, and Panagiotis Tsikouras. Strings of length 3 in Grand-Dyck paths and the Chung-Feller property. Electron. J. Combin., 19(2):Paper 2, 10, 2012. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p2/pdf.
  27. Toufik Mansour and Mark Shattuck. Counting humps and peaks in generalized Motzkin paths. Discrete Appl. Math., 161(13-14):2213-2216, 2013. URL: http://dx.doi.org/10.1016/j.dam.2013.03.007.
  28. Donatella Merlini, D. G. Rogers, R. Sprugnoli, and M. Cecilia Verri. Underdiagonal lattice paths with unrestricted steps. Discrete Appl. Math., 91(1-3):197-213, 1999. URL: http://dx.doi.org/10.1016/S0166-218X(98)00126-7.
  29. Youngja Park and Seung Kyung Park. Enumeration of generalized lattice paths by string types, peaks, and ascents. Discrete Math., 339(11):2652-2659, 2016. URL: http://dx.doi.org/10.1016/j.disc.2016.04.024.
  30. Marcel-Paul Schützenberger. On context-free languages and push-down automata. Information and Control, 6:246-264, 1963. Google Scholar
  31. Marcel-Paul Schützenberger. On the synchronizing properties of certain prefix codes. Information and Control, 7:23-36, 1964. URL: https://www.sciencedirect.com/science/article/pii/S0019995864902323/pdf.
  32. Richard P. Stanley. Enumerative combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2nd edition, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact