Enumeration of Sequences Constrained by the Ratio of Consecutive Parts

Sylvie Corteel ; Sunyoung Lee ; Carla D. Savage

Séminaire lotharingien de combinatoire, 54A (2005-2007)

Résumé

Recurrences are developed to enumerate any family of nonnegative integer sequences $\lambda=(\lambda_1,\ldots ,\lambda_n)$ satisfying the constraints:

\begin{displaymath} \frac{\lambda_1}{a_1} \geq \frac{\lambda_2}{a_{2}} \geq \cdo... ...\lambda_{n-1}}{a_{n-1}} \geq \frac{\lambda_{n}}{a_{n}} \geq 0, \end{displaymath}

for a given constraint sequence a=[a₁, ..., a_n] of positive integers. They are applied to derive new counting formulas, to reveal new relationships between families, and to give simple proofs of the truncated lecture hall and anti-lecture hall theorems.

Résumé. Nous développons des récurrences pour énumérer des familles de suites d'entiers $\lambda=(\lambda_1,\ldots ,\lambda_n)$ satisfaisant les contraintes

\begin{displaymath} \frac{\lambda_1}{a_1} \geq \frac{\lambda_2}{a_{2}} \geq \cdo... ...\lambda_{n-1}}{a_{n-1}} \geq \frac{\lambda_{n}}{a_{n}} \geq 0, \end{displaymath}

pour une suite d'entiers positifs donnée a=[a₁, ..., a_n]. Ces récurrences permettent de dériver de nouvelles formules dénumération, de révéler de nouvelles relations entre certaines familles, et de donner des preuves simples des théorèmes des partitions Lecture Hall tronquées et des compositions Lecture Hall tronquées.