Journal of Integer Sequences, Vol. 13 (2010), Article 10.6.8

Counting Peaks and Valleys in a Partition of a Set

Toufik Mansour
Department of Mathematics
University of Haifa
31905 Haifa

Mark Shattuck
Department of Mathematics
University of Tennessee
Knoxville, TN 37996


A partition π of the set [n] = {1,2,...,n} is a collection {B1, B2, ... , Bk} of nonempty disjoint subsets of [n] (called blocks) whose union equals [n]. In this paper, we find an explicit formula for the generating function for the number of partitions of [n] with exactly k blocks according to the number of peaks (valleys) in terms of Chebyshev polynomials of the second kind. Furthermore, we calculate explicit formulas for the total number of peaks and valleys in all the partitions of [n] with exactly k blocks, providing both algebraic and combinatorial proofs.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000110 and A008277.)

Received April 19 2010; revised version received June 18 2010. Published in Journal of Integer Sequences, June 22 2010.

Return to Journal of Integer Sequences home page