Finding all possible designs for a staircase

Question

I was given this problem as an extra credit challenge, but was completely stumped on how to even approach it.

The problem:

You have 50 blocks to build a staircase, how many different designs are possible?

Staircase Rules:

1: A staircase must have at least two steps

2: A step must be at least one block shorter than the one before it

3: All bricks must be used in the design

How would you start making a formula to solve this?

Answer 1

The way to solve this with dynamic programming is pretty simple. For a positive integer $k$, let $B_k(n)$ be the number of partitions into elements of distinct size of $n$, such that every summand is among $1,2,\dots, k$. Clearly we want $B_{49}(50)$.

Then clearly $B_{k+1}(n)=B_{k}(n-k-1)+B_k(n)$.

Using this we can fill an array of size $51$ with $B_1(n)$ for all $0\leq n\leq 50$ and actualize it from $B_k$ to $B_{k+1}$ until we get $B_{50}(n)$, which is what we need. Here is come c++ code:

#include <bits/stdc++.h>

int B[51]; // this array saves the results

int main(){
    B[0]=1;
    for(int i=1;i<50;i++){ // here we actualize from B_(i-1) to B_i
        for(int j=50;j>=i;j--){ // we let B_i(j)=B_(i-1)(j-i)+B_(i-1)(j)
            B[j]+=B[j-i];
        }
    }
    printf("%d\n",B[50]); // we print the result
}

Output:

$3657$

Answer 2

A nice thing about these questions is that you can almost always start with the most direct, painful way, and then hopefully along the way we get some insight about how to do it better. Note that by condition $2$ (and if we count the steps from shortest to tallest), the $n$th shortest step has at least $n$ blocks in it. So in particular, the staircase can have at most 9 steps (otherwise we would need $1+2+\dots+10=55$ blocks. Now lets condition on how many steps we have. If we have $k$ steps, then we have $1+2+\dots+k=\frac{k(k+1)}{2}$ steps that are "fixed" in the sense above. This leaves $50-\frac{k(k+1)}{2}$ steps to play around with. I claim that, in assigning these steps, we will end up with integer partition numbers.

To see this, let $b_n=\#(\text{blocks in nth shortest step})-n$. From the discussion above, we know $b_n\geq 0$ for all $n$. Furthermore, the $b_n$ are weakly increasing, again by condition $2$. If you add an additional block onto the shortest step, you have to increase the height of every taller step as well. Finally, we have $b_1+b_2+\dots+b_k=50-\frac{k(k+1)}{2}$; so this is a partition of $50-\frac{k(k+1)}{2}$ into at most $k$ parts. We now have a (somewhat ugly) formula: $$ \text{Total possibilities}=\sum_{k=2}^9p_{\leq k}\left(50-\frac{k(k+1)}{2}\right) $$ where $p_\leq(\circ)$ denotes the number of integer partitions with $k$ or fewer parts.

Edit: A brief SAGE calculation gives this number to be 3657.