Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

John Hall

UCSD

Counting Descents with Prescribed Tops and Bottoms

Abstract:

Given sets $X$ and $Y$ of positive integers and a permutation $\sigma = \sigma_1 \sigma_2 \cdots \sigma_n$, an $X,Y$-\emph{descent} of $\sigma$ is a descent pair $\sigma_i > \sigma_{i+1}$ whose ``top'' $\sigma_i$ is in $X$ and whose ``bottom'' $\sigma_{i+1}$ is in $Y$. We give two formulas for the number $P_{n,s}^{X,Y}$ of $\sigma \in S_n$ with $s$ $X,Y$-descents. $P_{n,s}^{X,Y}$ is also shown to be a hit number of a certain Ferrers board. This work generalizes results of Kitaev and Remmel on counting descent pairs whose top (or bottom) is equal to 0 mod $k$. (This is joint work with Jeff Remmel.)

October 10, 2006

4:00 PM

AP&M 7321

****************************