It's a pretty difficult combinatorics problem.

I'm assuming the wall has no gaps in it... Correct me if I'm wrong...it's the number of compositions of $n$ into positive integers, because we have $n$ blocks and $k$ stacks of blocks with a total of $n$ cubes among these $k$ stacks. Then ...and the number of compositions of $n$ into $k$ positive integers is $\binom{n-k+k-1}{k-1}=\binom{n-1}{k-1}$...then your final answer is $\sum_{k=1}^{n}{\binom{n-1}{k-1}}=\binom{n-1}{0}+\binom{n-1}{1}+...+\binom{n-1}{n-1}=\boxed{2^{n-1}}$... That's not so hard... Unless I misinterpreted the problem? When shobber said "it has a common face with the previous one", does that mean that any given cube is adjacent to the one placed before it?

K81o7 wrote: Unless I misinterpreted the problem? When shobber said "it has a common face with the previous one", does that mean that any given cube is adjacent to the one placed before it? Regardless of whether or not the requirement exists that each cube must be adjacent to the one placed before it, any "wall" produced by your formula is still possible to build (because if the requirement does exist, you can simply build left to right). Consider this solution: label each block $1,2,...,n$. Place block 1 on the floor. Block 2 may go in one of two places: on top of block 1, or next to it. Similarly, block 3 may go on top of the rightmost stack (block 2), or it may go on the floor in a new stack. This continues until block $n$ is placed, either on top of block $n-1$ or on the floor to the right of it. This gives a total of $1 \cdot 2 \cdot 2 \cdot ... \cdot 2$ with $n-1$ 2's, and so the total is $2^{n-1}$. Edit: Unless of course, reflections of walls do not count as distinct. In this case, it might be a bit tougher...

No, if each cube must be next to the previous cube, then it must either be directly above or below that cube, or at the same height...

For the sake of simplicity, I defined the building process as starting at the left and working right. As a result of that, blocks can only be placed to the right or on top of other blocks. This makes counting easier.

maokid7 wrote:

But the wall can be more than 2 blocks high. So when you stac, say, three blocks on top of the other $n-3$, there are more than $\binom{n-3}{3}$ ways to do that... It's easier to look at it the other way I think... Yeah, xsquardster's solution is essentially building the composition piece by piece: each step, adding either an object, or a divider and an object.

Sorry for bumping this thread, but is the answer $ 2^[n-1]$ correct? Can someone explain it to me better?

I mean $ 2^{n-1}$.

Suppose we make a systematic procedure of creating each wall: (1) Put down a block (2) For each block, either put a block on top of this block or on the ground to the right of this block Note that there's exactly one way that follows the above procedure format for building any valid wall. Thus, the number of possible walls is equal to the number of different ways we can go about the above procedure. We have 1 way to place the first block (on the ground), and 2 ways to place any subsequent block (on top of the previous block i.e. in the same column, or to the right of the previous block i.e. in a new column). Hence, $ 1 \cdot 2^{n-1} = 2^{n-1}$

Oh, I seem to have misunderstood the problem. When it says "has a common face with the previous one" I thought it meant the $ nth$ cube placed has to have a common face with the $ n+1th$ cube placed. Therefore, if you placed the second cube on top of the first cube, you could only place the third cube above the second. Can anyone solve my interpretation?

There are $ n$ cubes that you can pick to be the "corner cube", where picking the first to be the corner cube makes a column, picking the last makes a horizontal row, and picking anything in between makes a sort-of L-shape. This gives you $ n$ walls.

No, I don't think $ n$ is correct. For example, there are 3 ways of placing 3 blocks - a horizontal row, a vertical row and a backwards L shape. However, with the backwards L shape, we can place the 4th block either on top of the 3rd block, or on top of the first. Therefore, there are 5 different walls of 4 blocks.

@immortaltechnique: it seems as if you are insisting on placing the second block to the right of or on top of the first, because otherwise, there are four possibilities for three walls: vertical column, horizontal row, forwards-L or backwards-L, where the forwards-L is achieved by going to the left and then up.