Smooth words and Chebyshev polynomials
| dc.creator | Knopfmacher, Arnold | |
| dc.creator | Mansour, Toufik | |
| dc.creator | Munagi, Augustine | |
| dc.creator | Prodinger, Helmut | |
| dc.date | 2008-09-03 | |
| dc.date.accessioned | 2026-07-07T10:00:16Z | |
| dc.date.available | 2026-07-07T10:00:16Z | |
| dc.description | 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|\le 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. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/0809.0551 | |
| dc.identifier | http://arxiv.org/abs/0809.0551 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/168281 | |
| dc.subject | Combinatorics | |
| dc.subject | 68R05; 05A05; 05A15; 05A16 | |
| dc.title | Smooth words and Chebyshev polynomials | |
| dc.type | text |