Families of prudent self-avoiding walks
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2008-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3627/pdf |
| _version_ | 1797270443955060736 |
|---|---|
| author | Mireille Bousquet-Mélou |
| author_facet | Mireille Bousquet-Mélou |
| author_sort | Mireille Bousquet-Mélou |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:04:22Z |
| format | Article |
| id | doaj.art-ba70282839fa4c9aaf6dbd8221c35570 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:04:22Z |
| publishDate | 2008-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-ba70282839fa4c9aaf6dbd8221c355702024-03-07T14:38:06ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502008-01-01DMTCS Proceedings vol. AJ,...Proceedings10.46298/dmtcs.36273627Families of prudent self-avoiding walksMireille Bousquet-Mélou0https://orcid.org/0000-0002-2863-8300Laboratoire Bordelais de Recherche en InformatiqueA 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.https://dmtcs.episciences.org/3627/pdfenumerationself-avoiding walks$d$-finite generating functions[math.math-co] mathematics [math]/combinatorics [math.co][info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Mireille Bousquet-Mélou Families of prudent self-avoiding walks Discrete Mathematics & Theoretical Computer Science enumeration self-avoiding walks $d$-finite generating functions [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Families of prudent self-avoiding walks |
| title_full | Families of prudent self-avoiding walks |
| title_fullStr | Families of prudent self-avoiding walks |
| title_full_unstemmed | Families of prudent self-avoiding walks |
| title_short | Families of prudent self-avoiding walks |
| title_sort | families of prudent self avoiding walks |
| topic | enumeration self-avoiding walks $d$-finite generating functions [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/3627/pdf |
| work_keys_str_mv | AT mireillebousquetmelou familiesofprudentselfavoidingwalks |