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...
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 |
id |
ftccsdartic:oai:HAL:hal-01215040v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-01215040v1 2023-05-15T16:50:30+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) Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM) 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 en eng HAL CCSD DMTCS hal-01215040 https://hal.inria.fr/hal-01215040 https://hal.inria.fr/hal-01215040/document https://hal.inria.fr/hal-01215040/file/dmAO0153.pdf 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 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 ftccsdartic 2021-10-24T11:25:10Z 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 Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
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) Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM) 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 |
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 |
op_relation |
hal-01215040 https://hal.inria.fr/hal-01215040 https://hal.inria.fr/hal-01215040/document https://hal.inria.fr/hal-01215040/file/dmAO0153.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1766040635081490432 |