On the Generalized Climbing Stairs Problem

Original · EN

Let 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 ∈ 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 = ∑ₛ ∈ ₛ mₛ s satisfying 0 ≤ mₛ ≤ 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.