Counting staircases in integer compositions
Aubrey Blecher, Toufik Mansour · Online Journal of Analytic Combinatorics · 2016
The main theorem establishes the generating function \(F\) which counts the number of times the staircase \(1 + 2 + 3 + \cdots + m^+\) fits inside an integer composition of \(n\). \[ F = \frac{k_m - \frac{q x^m y}{1-x} k_{m-1}}{(1-q)x^{\binom{m+1}{2}} \left( \frac{y}{1-x} \right)^m + \frac{1-x-xy}{1-x} \left( k_m - \frac{q x^m y}{1-x} k_{m-1} \right)}. \] where \[ k_m = \sum_{j=0}^{m-1} x^{mj - \binom{j}{2}} \left( \frac{y}{1-x} \right)^j. \] Here \(x\) and \(y\) respectively track the composition size and number of parts, whilst \(q\) tracks the number of such staircases contained.