Smooth words and Chebyshev polynomials

Details Smooth words and Chebyshev polynomials Smooth words and Chebyshev polynomials

2008-09-03

arxiv.org/abs/0809.0551v1

Mathematics

Combinatorics

12 pages

Scientific paper

A word $\sigma=\sigma_1...\sigma_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 $\sigma$ is said to be {\em smooth cyclic} if it is a smooth word and in addition satisfies $|\sigma_n-\sigma_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.

Affiliated with

Also associated with

No associations

Rating

Smooth words and Chebyshev polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Smooth words and Chebyshev polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Smooth words and Chebyshev polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-104155