Loading [MathJax]/jax/output/HTML-CSS/jax.js

Philippe Nadeau - Enumeration of walks reaching a line

dmtcs:3449 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3449
Enumeration of walks reaching a lineConference paper

Authors: Philippe Nadeau ORCID1

  • 1 Laboratoire de Recherche en Informatique

We enumerate walks in the plane R2, with steps East and North, that stop as soon as they reach a given line; these walks are counted according to the distance of the line to the origin, and we study the asymptotic behavior when the line has a fixed slope and moves away from the origin. When the line has a rational slope, we study a more general class of walks, and give exact as well as asymptotic enumerative results; for this, we define a nice bijection from our walks to words of a rational language. For a general slope, asymptotic results are obtained; in this case, the method employed leads us to find asymptotic results for a wider class of walks in Rm.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: walk,generating function,rational language,singularity analysis,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC]

Consultation statistics

This page has been seen 214 times.
This article's PDF has been downloaded 203 times.