A GENERALIZATION OF THE CLIMBING STAIRS PROBLEM II

Mohammad K. Azarian

Abstract. In a previous article [2], we found the number of ways to run up a staircase with n steps, where there was no restriction on the size s of each step taken, other than 1 ≤ s ≤ n (n ≥ 1). In this paper, we first answer questions posed in [2], where there are some restrictions on s, and then we pose some further questions for the reader.

1. Introduction. As is evident from our discussion in [2], the climbing stairs problem is a partition problem. To compute p(n), the partition of a positive integer n, we used a generating function. However, we must remember that L. Euler obtained a recursive relation for p(n) in 1748 [1]. Nonetheless, the most fascinating theorem in the theory of partition is a theorem for the exact value of p(n) by G. E. Hardy, S. Ramanujan, and H. Rademacher [1]. This theorem gives the exact value of p(n). But to use this theorem and actually compute p(n), we would be dealing with an infinite series that involves square roots, complex roots of unity, derivatives of hyperbolic functions, and π. This is more of a theoretical theorem than an algorithm suitable for calculating p(n), for the kinds of simple problems that we are dealing with in this article.

In [2], we found the number of ways to run up a staircase with n steps (n ≥ 1) in steps of possibly different sizes. We summarize the results of [2] in the following theorem.

\underline{Theorem 1.1}. [2]. The number of different ways to run up a staircase with n steps, taking steps of possibly different sizes, where the order is not important and there is no restriction on the number or the size of each step taken is p(n), the coefficient of x^{n} in the expansion of its corresponding generating function

g(x) = ∏_{k=1}^{n} \frac{1}{1 − x^{k}} .

Under the same conditions and when the order is important the answer is 2^{n−1}, the coefficient of x^{n} in the expansion of its corresponding generating function

g(x) = \frac{x}{1 − 2x}.

We observe that in the above theorem there is no restriction on the size s of each step taken, other than 1 ≤ s ≤ n. The objective of this article is twofold. We answer questions posed in [2], where there are some restrictions on s, and then we pose some further questions for the reader. The calculations here are simple and are similar to those in [2], and are left to the reader. However, to calculate the number of linear permutations of n, when some summands are repeated n_{1}, n_{2}, …, n_{k} times, we use the well–known formula

\frac{n!}{n_{1}!n_{2}! ⋯ n_{k}!}, where ∑_{i=1}^{k} n_{i} = n.

Also, we note that throughout this article we will be dealing with ordinary generating functions only.

2. Answers to Questions Posed in [2].

\underline{Question 1}. How many different ways are there to run up a staircase with n steps, taking steps of even sizes only?

In order to run up a staircase taking steps of even sizes, n itself must be even. When the order in which each step taken is important, then the total number of ways to run up a staircase for n = 2, 4, 6, …, 16 are 1, 2, 4, 8, 16, 32, 64, and 128, respectively. Hence, in general, the total number of possible ways to run up a staircase with n = 2k steps, taking steps of even sizes, where the order is important is the number of compositions of n = 2k into even summands, which is equal to the number of compositions of k = n/2 into all summands (even and odd summands). When the order in which each step is taken is not important, for n = 2, 4, …, 18, we get 1, 2, 3, 5, 7, 15, 22, and 30 as the total number of ways to run up a staircase, respectively. Hence, we have the following theorem.

\underline{Theorem 2.1}. The number of different ways to run up a staircase with n = 2k steps, taking steps of even sizes, where the order in which each step is taken is important and there is no restriction on the number or the size of each step taken is 2^{k−1}, the coefficient of x^{k} in the expansion of its generating function

g(x) = \frac{x}{1 − 2x}.

Under the same conditions and when the order is not important the answer is p(n), the coefficient of x^{n} in the expansion of its corresponding generating function

g(x) = \frac{1}{1 − x^{2}} · \frac{1}{1 − x^{4}} · \frac{1}{1 − x^{6}} ⋯ \frac{1}{1 − x^{n}} = ∏_{i=1}^{k} \frac{1}{1 − x^{2i}} , (n = 2k).

\underline{Question 2}. How many different ways are there to run up a staircase with n steps, taking steps of odd sizes only?

If the order in which each step taken is relevant, then for n = 1 − 14, we get 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, and 377 as the total number of ways to run up a staircase, respectively. These numbers suggest that the number of different ways to run up a staircase in this case is F_{n}, a Fibonacci number. This is what was expected [6]. If the order is not relevant, then for n = 1 − 14, we get 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, and 22, respectively. So, this case is nothing but the partition of the integer n into odd summands. Therefore, we have established the following theorem.

\underline{Theorem 2.2}. The number of different ways to run up a staircase with n steps, taking steps of odd sizes, where the order is relevant and there is no other restriction on the number or the size of each step taken is F_{n}, the coefficient of x^{n} in the expansion of its corresponding generating function

g(x) = \frac{x}{1 − x − x^{2}} = ∑_{n=1}^{∞} F_{n}x^{n}.

Under the same conditions and when the order is not relevant the answer is p(n), the coefficient of x^{n} in the expansion of its corresponding generating function

g(x) = (1 + x + x^{2} + x^{3} + ⋯)(1 + x^{3} + x^{6} + ⋯)(1 + x^{5} + x^{10} + ⋯)

⋯ (1 + x^{n} + x^{2n} + x^{3n} + ⋯)

= ∏_{k=odd}^{n} \frac{1}{1 − x^{k}} .

\underline{Question 4}. How many different ways are possible to run up a staircase with n steps, taking steps of distinct sizes only?

When the order in which each step is taken matters, we obtain 1, 1, 3, 3, 5, 11, 13, 19, 27, 57, 65, 101, 133, and 193, for n = 1 − 14, respectively. As expected, these numbers are compositions of the integer n into distinct summands. When the order in which each step is taken does not matter, then for n = 1−14, we get 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 17, and 20, respectively. These numbers indicate that the number of different ways to run up a staircase with n steps, taking steps of distinct sizes, where the order does not matter, is the number of partitions of the integer n into distinct summands. Consequently, we can state the following theorem.

\underline{Theorem 2.3}. The number of different ways to run up a staircase with n steps, taking steps of distinct sizes, where the order matters and there is no other restriction on the number or the size of each step taken, is the composition of n into distinct parts, which is the coefficient of x^{n} in the expansion of its corresponding generating function

g(x) = ∑_{k=0}^{n} \frac{k!x^{\frac{k^{2}+k}{2}}}{∏_{j=1}^{k}(1 − x^{j})}.

Under the same conditions and when the order does not matter the answer is p(n), the coefficient of x^{n} in the expansion of its corresponding generating function

g(x) = (1 + x)(1 + x^{2})(1 + x^{3}) ⋯ = ∏_{k=1}^{n}(1 + x^{k}).

\underline{Answers to Other Questions}. Questions 3, 5, 6, and 7 follow from the above theorems and are left to the reader.

3. More Questions. To study this topic further we pose the following questions for the reader.

\underline{Question 1}. How many different ways are there to run up a staircase taking steps of distinct and even (odd) sizes only?

\underline{Question 2}. How many different ways are there to run up a staircase taking at most k steps of size k, (1 ≤ k ≤ n)?

\underline{Question 3}. How many different ways are there to run up a staircase, where the size of each step is greater than one?

\underline{Question 4}. How many different ways are there to run up a staircase taking only steps of size one or two (or both)?

\underline{Question 5}. How many different ways are there to run up a staircase, where each step must be taken an even (odd) number of times?

\underline{Question 6}. How many different ways are there to run up a staircase, where each step is taken at most twice?

\underline{Question 7}. How many different ways are there to run up a staircase, if only steps of size k, (for a fixed k) are allowed (1≤k≤n)?

\underline{Question 8}. How many different ways are there to run up a staircase, where the size of each step taken is a prime number? Also, consider the case where the size of each step taken is a distinct prime number.

\underline{Question 9}. How many different ways are there to run up a staircase, where the size of each step taken is a Fibonacci number? What if the size of each step taken is a distinct Fibonacci number?

\underline{Question 10}. How many different ways are there to run up a staircase taking steps of size s, where 1 < a ≤ s ≤ b ≤ n, 1 ≤ a ≤ s ≤ b < n, 1 ≤ a ≤ s ≤ b ≤ n, or 1 < a ≤ s ≤ b < n, for some arbitrary positive integers a and b.

It is clear that there are all sorts of questions that one could ask, so one can pose one’s own favorite questions.

\underline{References}

1. G. E. Andrews, Encyclopedia of Mathematics and its Applications, Vol. 2: The Theory of Partitions, Addison-Wesley, New York, NY, 1976.

2. M. K. Azarian, “A Generalization of the Climbing Stairs Problem,” Mathematics and Computer Education Journal, 31 (1997), 24–28.

3. M. K. Azarian, “The Generating Function for the Fibonacci Sequence,” Missouri Journal of Mathematical Sciences, 2 (1990), 78–79.

4. C. G. Bower, “Sequence A032020,” in N. J. S. Sloane, Sloane’s On-Line Encylocpedia of Integer Sequences, http://www.research.att.com/∼njas /sequences/index.html.

5. R. P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 3rd ed., Addison-Wesley, New York, NY, 1994.

6. K. H. Rosen, ed., Handbook of Discrete and Combinatorial Mathematics, CRC Press, Boca Raton, FL, 2000.

7. N. J. S. Sloane, Sloane’s On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/∼njas/sequences/index.html.

Mohammad K. Azarian Department of Mathematics 1800 Lincoln Avenue University of Evansville Evansville, IN 47722 email: azarian@evansville.edu