Closed paths whose steps are roots of unity
International audience We give explicit formulas for the number $U_n(N)$ of closed polygonal paths of length $N$ (starting from the origin) whose steps are $n^{\textrm{th}}$ roots of unity, as well as asymptotic expressions for these numbers when $N \rightarrow \infty$. We also prove that the sequen...
Published in: | Discrete Mathematics & Theoretical Computer Science |
---|---|
Main Authors: | , |
Other Authors: | , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01215040 https://hal.inria.fr/hal-01215040/document https://hal.inria.fr/hal-01215040/file/dmAO0153.pdf https://doi.org/10.46298/dmtcs.2937 |
id |
ftunivnantes:oai:HAL:hal-01215040v1 |
---|---|
record_format |
openpolar |
spelling |
ftunivnantes:oai:HAL:hal-01215040v1 2023-05-15T16:50:24+02:00 Closed paths whose steps are roots of unity Labelle, Gilbert Lacasse, Annie Laboratoire de combinatoire et d'informatique mathématique Montréal (LaCIM) Centre de Recherches Mathématiques Montréal (CRM) Université de Montréal (UdeM)-Université de Montréal (UdeM)-Université du Québec à Montréal = University of Québec in Montréal (UQAM) Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS) Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel Reykjavik, Iceland 2011 https://hal.inria.fr/hal-01215040 https://hal.inria.fr/hal-01215040/document https://hal.inria.fr/hal-01215040/file/dmAO0153.pdf https://doi.org/10.46298/dmtcs.2937 en eng HAL CCSD DMTCS info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2937 hal-01215040 https://hal.inria.fr/hal-01215040 https://hal.inria.fr/hal-01215040/document https://hal.inria.fr/hal-01215040/file/dmAO0153.pdf doi:10.46298/dmtcs.2937 info:eu-repo/semantics/OpenAccess ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science DMTCS Proceedings FPSAC: Formal Power Series and Algebraic Combinatorics https://hal.inria.fr/hal-01215040 FPSAC: Formal Power Series and Algebraic Combinatorics, 2011, Reykjavik, Iceland. pp.599-610, ⟨10.46298/dmtcs.2937⟩ closed polygonal paths Roots of unity $P$-recursive Asymptotics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftunivnantes https://doi.org/10.46298/dmtcs.2937 2022-10-19T00:19:51Z International audience We give explicit formulas for the number $U_n(N)$ of closed polygonal paths of length $N$ (starting from the origin) whose steps are $n^{\textrm{th}}$ roots of unity, as well as asymptotic expressions for these numbers when $N \rightarrow \infty$. We also prove that the sequences $(U_n(N))_{N \geq 0}$ are $P$-recursive for each fixed $n \geq 1$ and leave open the problem of determining the values of $N$ for which the $\textit{dual}$ sequences $(U_n(N))_{n \geq 1}$ are $P$-recursive. Nous donnons des formules explicites pour le nombre $U_n(N)$ de chemins polygonaux fermés de longueur $N$ (débutant à l'origine) dont les pas sont des racines $n$-ièmes de l'unité, ainsi que des expressions asymptotiques pour ces nombres lorsque $N \rightarrow \infty$. Nous démontrons aussi que les suites $(U_n(N))_{N \geq 0}$ sont $P$-récursives pour chaque $n \geq 1$ fixé et laissons ouvert le problème de déterminer les valeurs de $N$ pour lesquelles les suites $\textit{duales}$ $(U_n(N))_{n \geq 1}$ sont $P$-récursives. Conference Object Iceland Université de Nantes: HAL-UNIV-NANTES Discrete Mathematics & Theoretical Computer Science DMTCS Proceeding Proceedings |
institution |
Open Polar |
collection |
Université de Nantes: HAL-UNIV-NANTES |
op_collection_id |
ftunivnantes |
language |
English |
topic |
closed polygonal paths Roots of unity $P$-recursive Asymptotics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
spellingShingle |
closed polygonal paths Roots of unity $P$-recursive Asymptotics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Labelle, Gilbert Lacasse, Annie Closed paths whose steps are roots of unity |
topic_facet |
closed polygonal paths Roots of unity $P$-recursive Asymptotics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
description |
International audience We give explicit formulas for the number $U_n(N)$ of closed polygonal paths of length $N$ (starting from the origin) whose steps are $n^{\textrm{th}}$ roots of unity, as well as asymptotic expressions for these numbers when $N \rightarrow \infty$. We also prove that the sequences $(U_n(N))_{N \geq 0}$ are $P$-recursive for each fixed $n \geq 1$ and leave open the problem of determining the values of $N$ for which the $\textit{dual}$ sequences $(U_n(N))_{n \geq 1}$ are $P$-recursive. Nous donnons des formules explicites pour le nombre $U_n(N)$ de chemins polygonaux fermés de longueur $N$ (débutant à l'origine) dont les pas sont des racines $n$-ièmes de l'unité, ainsi que des expressions asymptotiques pour ces nombres lorsque $N \rightarrow \infty$. Nous démontrons aussi que les suites $(U_n(N))_{N \geq 0}$ sont $P$-récursives pour chaque $n \geq 1$ fixé et laissons ouvert le problème de déterminer les valeurs de $N$ pour lesquelles les suites $\textit{duales}$ $(U_n(N))_{n \geq 1}$ sont $P$-récursives. |
author2 |
Laboratoire de combinatoire et d'informatique mathématique Montréal (LaCIM) Centre de Recherches Mathématiques Montréal (CRM) Université de Montréal (UdeM)-Université de Montréal (UdeM)-Université du Québec à Montréal = University of Québec in Montréal (UQAM) Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS) Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel |
format |
Conference Object |
author |
Labelle, Gilbert Lacasse, Annie |
author_facet |
Labelle, Gilbert Lacasse, Annie |
author_sort |
Labelle, Gilbert |
title |
Closed paths whose steps are roots of unity |
title_short |
Closed paths whose steps are roots of unity |
title_full |
Closed paths whose steps are roots of unity |
title_fullStr |
Closed paths whose steps are roots of unity |
title_full_unstemmed |
Closed paths whose steps are roots of unity |
title_sort |
closed paths whose steps are roots of unity |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://hal.inria.fr/hal-01215040 https://hal.inria.fr/hal-01215040/document https://hal.inria.fr/hal-01215040/file/dmAO0153.pdf https://doi.org/10.46298/dmtcs.2937 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science DMTCS Proceedings FPSAC: Formal Power Series and Algebraic Combinatorics https://hal.inria.fr/hal-01215040 FPSAC: Formal Power Series and Algebraic Combinatorics, 2011, Reykjavik, Iceland. pp.599-610, ⟨10.46298/dmtcs.2937⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2937 hal-01215040 https://hal.inria.fr/hal-01215040 https://hal.inria.fr/hal-01215040/document https://hal.inria.fr/hal-01215040/file/dmAO0153.pdf doi:10.46298/dmtcs.2937 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.46298/dmtcs.2937 |
container_title |
Discrete Mathematics & Theoretical Computer Science |
container_volume |
DMTCS Proceeding |
container_issue |
Proceedings |
_version_ |
1766040556319801344 |