Nigerian Math Olympiad Question How many ways can a child who is given the task of laying n bricks lay them out if they can do so under the conditions

*

*The laying of bricks is constrained to a single vertical plane

*The bricks must be either placed adjacent to the previously placed brick or directly above it

*The child constructs the initial layer from left to right

*No brick can be floating

All cases with 6 blocks

My attempt: I just thought of this as a case of partitioning n, if I find the number of ways to partition n , I know the structures they make since after partitioning I just arrange the numbers in descending order and that would be it.
However I haven't come across any such formula that states the number of partitions a number n can have, i think it may be that my solution is wrong somehow since this was asked in the Nigeran math Olympiad a few years ago (saw it on AOPS) and the answers are almost always a complete formula in these kinds of tests, instead of statements. So is my answer right or wrong?
 A: Observations towards a solution.
Prove the following. If you're stuck, state what you've tried.

*

*The total number of blocks in the structure is $n$.

*Every layer must be built one at a time (since we can't go down)

*The structure is uniquely determined by how many squares is in each horizontal layer.

*The number of blocks in each horizontal layer (2nd onwards)has at most as many blocks as the layer beneath it.

*Thus, when viewed in horizontal layers, a structure yields a partition of $n$.

*Conversely, show that if we have a partition of $n$, then we can build a structure.

*Thus, we have a bijection. So, the number of structures is indeed the number of partitions.

I agree with you that no closed-form expression is known, so that likely isn't what they were expecting.
Maybe check the original writeup (see if they were asked to prove it's the number of partitions). It might also be possible that they got the problem wrong.
A: The structure is built in a zig-zag - choose in one layer how far to go to the right (say) before going up; then in the next layer you can choose how far to go to the left, up to a maximum of the width of the previous layer, before going up; then repeat. This is why the number of structures is equal to the number of partitions of $n$: any pile of rows of squares with the number of squares in each row at most the number in the row below (a partition) can be turned into a zig-zag by moving each row horizontally so the rightmost square in it is above the rightmost square in the row below, or the leftmost square is above the leftmost square in the row below, alternating between these.
A: Edit: this is in fact the number of partitions. A partition of 6 is a list of numbers without order, something like $6=2+2+1+1$, not a choice of where to put dividers into a line of six balls, like $\cdot|\cdot\cdot|\cdot\cdot|\cdot$.
I would approach this problem using a recursive function. You can do this with a recursive function. The only choice you can make in each row is how many bricks to place in that row. Each choice leads to a sub-problem, where you place a smaller number of bricks, and you also have a constraint on the maximum number of bricks in the "new first row" (i.e. the actual second row).
Can you see a way to set up the recursion? And can you work out the initial conditions (one initial condition for $n$ bricks with a previous-row width of 1 row, and another initial condition for 0 bricks with a previous-row width of $r$ rows)?
Once you have your recursion and initial conditions, you can set up your table of values. Once you get a few rows in, see if you can see the pattern in the diagonal entries (those for $n$ bricks with a previous-row width of $n$ bricks). I haven't found a pattern yet, but my numbers were 1,2,3,5,7,11,15,22,30, ...
A: It is not partitioning, because in the partition diagrams, the height is monotonic left to right.
The solution can be written thus:
Suppose the bottom layer has $k$ bricks. Then the number of ways is the number of ways to put $n-k$ bricks in $k$ bins, which is ${n-1}\choose{k-1}.$ Now, $k$ can be anything from $1$ to $n,$ so we have the sum
$$
\sum_{k=1}^n \binom{n-1}{k-1} = \sum_{k=0}^{n-1} \binom{n-1}k= 2^{n-1}.$$
