28549 articles – 22058 references  [version française]

hal-00697386, version 1

Non-D-finite excursions in the quarter plane

Alin Bostan (, http://algo.inria.fr/bostan/) 1, Kilian Raschel (, http://www.lmpt.univ-tours.fr/~raschel/) 2, 3, Bruno Salvy (, http://algo.inria.fr/salvy/) 1

(15/05/2012)

Abstract: We prove that the sequence $(e^{\mathfrak{S}}_n)_{n\geq 0}$ of excursions in the quarter plane corresponding to a nonsingular step set~$\mathfrak{S} \subseteq \{0,\pm 1 \}^2$ with infinite group does not satisfy any nontrivial linear recurrence with polynomial coefficients. Accordingly, in those cases, the trivariate generating function of the numbers of walks with given length and prescribed ending point is not D-finite. Moreover, we display the asymptotics of $e^{\mathfrak{S}}_n$.

  • 1:  ALGORITHMS (INRIA Rocquencourt)
  • INRIA
  • 2:  Laboratoire de Mathématiques et Physique Théorique (LMPT)
  • Université François Rabelais - Tours – CNRS : UMR7350
  • 3:  Fédération de recherche Denis Poisson (FRDP)
  • CNRS : FR2964 – Université d'Orléans – Université François Rabelais - Tours
  • Domain : Mathematics/Combinatorics
    Mathematics/Probability
  • Keywords : Walks in the quarter plane – generating functions – D-finite functions – excursions
  • Comment : 14 pages
 
  • hal-00697386, version 1
  • http://hal.archives-ouvertes.fr/hal-00697386
  • oai:hal.archives-ouvertes.fr:hal-00697386
  • From: Kilian Raschel <>
  • Submitted on: Tuesday, 15 May 2012 11:32:05
  • Updated on: Tuesday, 5 February 2013 13:34:18