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 {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