2008/09/03 by Arnold Knopfmacher, Toufik Mansour, Knopfmacher, Arnold +6
Computer Science · Mathematics · #05A05 #05A15 #05A16 #68R05 #Advanced Combinatorial Mathematics #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A05 #msc:05A15 #msc:05A16 #msc:68R05 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0809.0551
12 pages
arxiv created 2008/09/03 · openalex publication_date 2008/09/03 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A word σ=σ1...σn over the alphabet [k]=\1,2,...,k\ is said to be \em smooth if there are no two adjacent letters with difference greater than 1. A word σ is said to be \em smooth cyclic if it is a smooth word and in addition satisfies |σn-σ1|≤ 1. We find the explicit generating functions for the number of smooth words and cyclic smooth words in [k]n, in terms of \it Chebyshev polynomials of the second kind. Additionally, we find explicit formula for the numbers themselves, as trigonometric sums. These lead to immediate asymptotic corollaries. We also enumerate smooth necklaces, which are cyclic smooth words that are not equivalent up to rotation.