Counting staircases in integer compositions

Abstract

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^{(\genfrac{}{}{0ex}{}{m+1}{2})}{\left(\frac{y}{1-x}\right)}^m+\frac{1-x-xy}{1-x}(k_m–\frac{q{x}^{m}y}{1-x}{k}_{m-1})}.$$
where
$$k_m=\sum _{j=0}^{m-1}{x}^{mj–(\genfrac{}{}{0ex}{}{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.