On the Generalized Climbing Stairs Problem

Abstract

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}$ and multiplicities at most $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\le m_s\le 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$.