Parity Theorems for Combinatorial Statistics

Author

Mark A. Shattuck, University of Tennessee - Knoxville

Date of Award

12-2005

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Mathematics

Major Professor

Carl G. Wagner

Committee Members

John Nolt, Jan Rosinski, Pavlos Tzermias

Abstract

A q-generalization Gn(q) of a combinatorial sequence Gn which reduces to that sequence when q = 1 is obtained by q-counting a statistic defined on a sequence of finite discrete structures enumerated by Gn. In what follows, we evaluate Gn(−1) for statistics on several classes of discrete structures, giving both algebraic and combinatorial proofs. For the latter, we define appropriate sign-reversing involutions on the associated structures. We shall call the actual algebraic result of such an evaluation at q = −1 a parity theorem (for the statistic on the associated class of discrete structures). Among the structures we study are permutations, binary sequences, Laguerre configurations, derangements, Catalan words, and finite set partitions.

As a consequence of our results, we obtain bijective proofs of congruences involving Stirling, Catalan, and Bell numbers. In addition, we modify the ideas used to construct the aforementioned sign-reversing involutions to furnish bijective proofs of combinatorial identities involving sums with alternating signs.

Recommended Citation

Shattuck, Mark A., "Parity Theorems for Combinatorial Statistics. " PhD diss., University of Tennessee, 2005.
https://trace.tennessee.edu/utk_graddiss/2327