On the Generalized Climbing Stairs Problem

Let $\mathcal{S}$ be a subset of the positive integers, and $M$ be a positive integer. Mohammad K. Azarian, inspired by work of Tony Colledge, considered the number of ways to climb a staircase containing $n$ stairs using “step-sizes” $s \in \mathcal S$andmultiplicitiesatmost$M$. In this exposition, we find a solution via generating functions, i.e., an expression which counts the number of partitions $n = \sum_{s \in \mathcal S} m_s s$satisfying$0 \leq m_s \leq M$. We then use this result to answer a series of questions posed by Azarian, thereby showing a link with ten sequences listed in the On-Line Encyclopedia of Integer Sequences. We conclude by posing open questions which seek to count the number of compositions of $n$.