# Combinatorics | Building a wall

Let $n$ be a positive integer. A child builds a wall along a line with $n$ identical cubes. He lays the first cube on the line and at each subsequent step, he lays the next cube either on the ground or on the top of another cube, so that it has a common face with the previous one. How many such distinct walls exist?

My attempt: In all there are n cubes so lets assume there are 'm' number of stacks of such cubes. Now we need to find in how many ways n can be decomposed into m integers. Am I right?

-

For brevity, call a "wall" built with $n$ cubes an $n$-wall. Call two $n$-walls different if, viewed from left to right, they look different. We give two ways of counting the $n$-walls, the second much simpler than the first. But the first way has the advantage that it arises from experimentation with small numbers. That always should be done, in order to try to get insight about a new combinatorial problem.

It is clear that the number of $1$-walls is $1$.

The $2$-walls are $11$ and $2$. There are $2$ of them.

The $3$-walls are $111$, $21$, $12$, and $3$. There are $4$ of them.

We list the $4$-walls, carefully. There are $8$ of them, $1111$, $211$, $121$, $31$, $112$, $22$, $13$, and $4$.

It is not unreasonable to conjecture that the number of $n$-walls is $2^{n-1}$, though admittedly the evidence is scanty.

Now let's prove the conjecture, technically by induction. Suppose that we know for some specific $n$, that the number of $n$-walls is $2^{n-1}$. How many $(n+1)$-walls are there?

There are two types of $(n+1)$-wall. Type $A$ has a $1$ at the right end. Type $B$ has a number $>1$ at the right end.

It is obvious that the number of type $A$ $(n+1)$-walls is $2^{n-1}$. The type $A$ $(n+1)$-walls are obtained by taking any $n$-wall, and appending a $1$ at the right end. Given any type $A$ $(n+1)$-wall, we can uniquely recover the $n$-wall that it "came from" by removing the terminal $1$.

There are also $2^{n-1}$ type $B$ $(n+1)$-walls. They are obtained by adding a cube on top of the rightmost pile of an $n$-wall. Given a type $B$ $(n+1)$-wall, we can uniquely recover the $n$-wall that it "came from" by removing the top cube from the rightmost pile of the type $B$ $(n+1)$-wall.

It follows that the number of $(n+1)$-walls is $2^{n-1}+2^{n-1}$, that is, $2^n$, twice as many as the number of $n$-walls.

Since we know that the number of $1$-walls is $2^{1-1}$, this completes the induction process. More informally, we know that there is $1$ $1$-wall. Therefore, without listing, we know that there must be $2$ $2$-walls. Therefore, without listing, we know there must be $4$ $3$-walls. But therefore there must be $8$ $4$-walls. And therefore there must be $16$ $5$-walls. And so on forever.

Another way: Imagine that the child's older sister is a professional wall designer. She lays out the $n$ cubes in a long row, with a space of a few centimeters between consecutive cubes. There are $n$ cubes, and therefore $n-1$ spaces.

The designer then chooses a subset of the set of $n-1$ spaces, and places a ribbon at each chosen space. (She might choose the empty subset of the $n-1$ spaces, or just $1$ of the spaces, or $2$, and so on.)

Now her kid brother builds the wall. The cubes from the left end of the row to the first ribbon are piled on each other to make the leftmost part of the wall (if $0$ spaces were chosen, all the cubes go on top of each other). The cubes from the first ribbon to the second are piled on top of each other, immediately to the right of the first pile. And so on.

It is clear that there are exactly as many $n$-walls as there are ways to choose a subset of the $n-1$ gaps. But any set of $n-1$ elements has $2^{n-1}$ subsets, so there are $2^{n-1}$ $n$-walls.

Comment: Let's add a rule to the wall building: The wall must be exactly $m$ cubes long. Then in the second argument, the designer must choose exactly $m-1$ of the $n-1$ gaps to put a ribbon into. It follows that the number of different walls of length exactly $m$ is $\binom{n-1}{m-1}$.

-

Your definition allows a considerable choice in the order in which the blocks of a finished wall are laid down. I will assume that you consider two walls that look identical to be "the same" wall even though they may have been built by different methods.

Now, for every finished wall there are many ways to build it. But we can decide to build all the walls from left to right, such that we first build the leftmost column up to its final height, then the next-to-leftmost column an so forth. This rule will allow us to build every possible wall in one and only one way.

As we follow the left-to-right principle, each time we lay down a block, we have a choice to made: We can either add it to the column we're already building, or we can start a new column to the right of it. This choice cannot be undone afterwards, because it determines completely whether the current column's final height will be its current height or something higher.

There are exactly two options to choose between each time we put down a block, except for the first one which can only be laid in one way. Therefore, if we have $n$ blocks in total, then the number of ways all the decisions can be made is $$1 \times \underbrace{2 \times 2 \times \cdots \times 2}_{n-1\text{ factors}} = 2^{n-1}$$ and this must also be the number of different possible finished walls.

Alternative: The approach you sketch in the question would also work. It leads to the number of length-$m$ walls with $n$ cubes being the binomial coefficient $\binom{n-1}{m-1}$. Taking the sum of this for all relevant $m$ gives $2^{n-1}$ (which is a fact about binomial coefficients that you'd need to know in advance).

-
Nice! It is a much clearer presentation of the process. –  André Nicolas Sep 3 '11 at 20:19

Your definition is somewhat confusing; I presume that a block placed on the ground has to be adjacent to the previously built tower, or else there are an infinite number of such walls.

But also, it depends on how you're defining decomposition. The stacks of the wall can be built in any order, and those are counted as different walls. On the other hand, assuming you're defining a decomposition as a representation of n as a sum of m positive integers, two different sums in different orders will be the same.

So, if order matters in your decomposition, then you are correct: any sequence of (positive) integers adding to n can be made into a wall by building a tower with height the first integer, then starting over with the second integer, etc. Similarly, any wall produces such a sequence of integers, so this gives a bijection between the two sets being counted. If you are ignoring order, the number of walls is much larger.

-

There is one way of placing the first block.

There are three ways of placing the second block: to the left, on top, or to the right of the first block.

The number of ways of placing the third block will depend on the width of the two-block wall.

So let $f(n,w)$ be the number of ways of building an $n$-block wall of width $w$. You start with $f(1,1)=1$ and $f(1,w)=0$ for $w \not = 1$. Then you have $$f(n,w)=2f(n-1,w-1)+wf(n-1,w)$$

and the following table

            w
f(n,w)      1   2   3   4   5   6

n   1       1   0   0   0   0   0
2       1   2   0   0   0   0
3       1   6   4   0   0   0
4       1   14  24  8   0   0
5       1   30  100 80  16  0
6       1   62  360 520 240 32


Adding up the rows gives the sequence $1,3,11,47,227,1215,\ldots$ which turns out to be OEIS A035009, half of OEIS A001861.

Henning Makholm's comments suggest looking at the finished wall instead of the building. In that case, $f(n,w) = {n-1 \choose w-1}$ (a basic result from counting compositions) and the sums over $w$ are $2^{-1}$ as he says in his answer.