Staircase words and Chebyshev polynomials

DOI10.2298/AADM1000010KMaRDI QIDQ5412643zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

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
• Staircases in \(\mathbb Z^2\)
• Enumeration of smooth inversion sequences and proof of a recent related conjecture
• 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)