all possible sequences of positive integers that sum upto N and are strictly increasing

Question

I have $N$ bricks and i have to build a staircase. A staircase will consist of steps of different sizes in decreasing order, no two step size should be same. Each step should consists of atleast one brick and each staircase should consist of atleast two steps. How to find all the possible number of staircases with $N$ bricks?

EDIT-it can also be stated as: All possible sequences of positive integers ($\ge 1$) that sum upto $N$ and are strictly increasing.

Answer 1

Ok, your question is "how many sequences of positive integers are there that sum to N, and are strictly increasing?"

Notice that this is the same question as "how many sequence of positive integers are there that sum to N, each element of the sequence is unique, without regard to order?"

For example, the sequences {5, 2, 1} and {2, 5, 1} are the same sequence without regard to order. If I give you any sequence that sums to N and each element is unique (doesn't occur more than once), you can just put that sequence in increasing order to get the size of your steps, such as {1, 2, 5}.

This is called the "Partition Function Q". here is a writeup about it from Mathworld. If Mathworld can't write up a simple closed form solution, it would probably be a waste of energy for me to try. The solution I used to find it was:

$ f(N, K) = \left\{ \begin{array}{l l} 0 & \quad N \le K \\ 1 + \sum_{i = K+1}^{N}F(N - i, i) & \quad N > K \end{array} \right.$

Where K is one less than the minimum value allowed in your sequence. This equation solves the problem recursively, breaking the problem into sub problems as "what if the next value in the sequence is i?" You are looking for $f(N, 0)$.

Hope this takes you where you want to go.

Edit: Explaining formula...

Suppose you want the number of sequences that add up to 10, no value as low as 3. That's F(10, 3).

Your sequences can start with 4, 5, 6, 7, 8, 9, or 10. How many sequences start with 4? F(6, 4) many sequences do. The {N} sequence I treat as a special case, so just add 1.

In hindsight I see it's better to just assume F(0, K) = 1: $ f(N, K) = \left\{ \begin{array}{l l} 1 & \quad N = 0 \\ \sum_{i = K+1}^{N}F(N - i, i) & \quad \text{otherwise} \end{array} \right.$

...noting that the summation is zero when K+1 > N.

Answer 2

Your problem is equivalent to finding the number of partitions of $N$ into distinct parts, denoted by $Q(N)$ or $q(N)$. The sequence $\langle Q(n):n\in\Bbb N\rangle$ is OEIS A$000009$; it has a decent generating function, but there is no nice closed form, and even the recurrences given at the two references are a bit on the messy side; see the references for details and further references.