##
**
Counting Peaks and Valleys in a Partition of a Set
**

###
Toufik Mansour

Department of Mathematics

University of Haifa

31905 Haifa

Israel

Mark Shattuck

Department of Mathematics

University of Tennessee

Knoxville, TN 37996

USA

**Abstract:**

A *partition* π of the set [*n*] = {1,2,...,n} is a
collection {*B*_{1}, *B*_{2}, ... ,
*B*_{k}} 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**