Staircase words and Chebyshev polynomials

DOI10.2298/AADM1000010KzbMATH Open1299.05003arXiv0809.0551OpenAlexW1554343055MaRDI QIDQ5412643FDOQ5412643

Authors: Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger 

Publication date: 25 April 2014

Published in: Applicable Analysis and Discrete Mathematics (Search for Journal in Brave)

Abstract: A word $sigma=sigm{a}_1\mathrm{...}sigm{a}_n$ over the alphabet $[k]=1,2,\mathrm{...},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 $|sigm{a}_n-sigm{a}_1|le1$. 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.

Full work available at URL: https://arxiv.org/abs/0809.0551

Recommendations

• Staircase patterns in words: subsequences, subwords, and separation number
• Chebyshev polynomials and statistics on a new collection of words in the Catalan family
• Staircases in \(\mathbb Z^2\)
• Restricted 132-avoiding \(k\)-ary words, Chebyshev polynomials, and continued fractions
• Restricted permutations and Chebyshev polynomials

zbMATH Keywords

generating functiontridiagonal matrixstaircase cyclic wordstaircase necklace

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15)

Cited In (11)

• Staircase patterns in words: subsequences, subwords, and separation number
• The infinite sums of reciprocals and the partial sums of Chebyshev polynomials
• A geometric property of the roots of Chebyshev polynomials
• Enumeration of r-smooth words over a finite alphabet
• Enumeration of smooth inversion sequences and proof of a recent related conjecture
• Staircases in \(\mathbb Z^2\)
• Domination polynomials of the grid, the cylinder, the torus, and the king graph
• Ben-Hur staircase climbs
• Some determinantal considerations for pentadiagonal matrices
• \((a, b)\)-rectangle patterns in permutations and words
• On the generalized climbing stairs problem.

This page was built for publication: Staircase words and Chebyshev polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5412643)