A word ? = ?1... ?n over the alphabet [k]={1,2,...,k} is said to be a staircase if there are no two adjacent letters with difference greater than 1. A word ? is said to be staircase-cyclic if it is a staircase word and in addition satisfies |?n??1|?1. We find the explicit generating functions for the number of staircase words and staircase-cyclic words in [k]n, in terms of 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 staircase necklaces, which are staircase-cyclic words that are not equivalent up to rotation.
1 January 2005 in International Journal of Mathematics and Mathematical Sciences
Partitions of the set {1, 2, …, n} are classified as having successions if a block contains consecutive integers, and separated otherwise. This paper constructs enumeration formulas for such set partitions and some variations using Stirling numbers of the second kind.