Skip to Main content Skip to Navigation
Conference papers

Families of prudent self-avoiding walks

Abstract : A self-avoiding walk on the square lattice is $\textit{prudent}$, if it never takes a step towards a vertex it has already visited. Préa was the first to address the enumeration of these walks, in 1997. For 4 natural classes of prudent walks, he wrote a system of recurrence relations, involving the length of the walks and some additional "catalytic'' parameters. The generating function of the first class is easily seen to be rational. The second class was proved to have an algebraic (quadratic) generating function by Duchi (FPSAC'05). Here, we solve exactly the third class, which turns out to be much more complex: its generating function is not algebraic, nor even $D$-finite. The fourth class ―- general prudent walks ―- still defeats us. However, we design an isotropic family of prudent walks on the triangular lattice, which we count exactly. Again, the generating function is proved to be non-$D$-finite. We also study the end-to-end distance of these walks and provide random generation procedures.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185162
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 19, 2015 - 11:42:59 AM
Last modification on : Friday, March 13, 2020 - 12:14:02 PM
Long-term archiving on: : Friday, November 20, 2015 - 10:33:33 AM

File

dmAJ0115.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185162, version 1

Collections

Citation

Mireille Bousquet-Mélou. Families of prudent self-avoiding walks. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. pp.167-180. ⟨hal-01185162⟩

Share

Metrics

Record views

206

Files downloads

704