On the Generalized Climbing Stairs Problem

Abstract

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