How many ways are there to stack boxes?

Question

Joshua was a box-stacker at the local supermarket. Every day he had to stack hundreds upon hundreds of boxes, so he devised a little game to keep himself entertained. Each day, he would take out a certain number($n$) of cubic boxes, and stack them according to these rules:

• He would only stack the boxes in a $2$-dimensional plane (only 1 layer deep).
• Every box in the bottom layer of boxes must be adjacent to another box, i.e. no gaps between the boxes in the bottom layer.
• Every box that is not on the bottom layer must be placed directly on top of another box.

After having stacked the $n$ boxes, Joshua would take a picture of the set-up and store it on his phone. How many different pictures could Joshua take if he had $n$ boxes to play with?

*Hint: You may be tempted to bash away with combinatoric mathematics, but I promise there is a very simplistic and beautiful way that involves no hard maths whatsoever.

Answer 1

Here is another way to arrive at the answer of

$2^{n-1}$

We can represent these "stackings" by taking a row of $n$ $*$'s, and placing |'s between some of the stars to break them into groups, representing the stacks.

For example, the below layout

*
* *
****

would be represented by

* * *|*|* *|*

This represents every possible stacking in a unique way, so asking for the number of stackings is the same as asking the number of strings of $*$'s and |'s in the above form. The latter is much easier to count: between every two adjacent $*$'s, there either is a |, or there isn't. This means there are $n-1$ choices to make, each with $2$ options, for a total of $2^{n-1}$ possibilities.

Answer 2

Answer:

$2^{n-1}$

How I arrived at this solution: We start by looking at the base case of $n=1$. There is only one way to stack one box.

Continuing for $n=2,3,4$, we get:

While drawing each piece out, I made sure to group the figures by the number of bottom pieces. By doing this, I noticed that the number in each group is very familiar:

n=1: 1
n=2: 1 1
n=3: 1 2 1
n=4: 1 3 3 1
.... It's Pascal's Triangle!

Thus, using the well known formula for the sum of each row, we get the answer:

$2^n$, but looking at the case of $n=1$, we only have one configuration, so the answer is actually: $2^{n-1}$

Answer 3

For every arrangement of $n$ boxes, we can define a procedure to create that arrangement consisting of $n$ instructions of either of the forms:

• Place a box on the current stack.
  OR
• Place a box to the right of the current stack. (This box is the new stack.)

Let's call the first instruction $0$ and the second instruction $1$. A sequence of instructions consists of a string of $n$ $1$s and $0$s. The only restriction is that, assuming we start with an empty stack, the first instruction must be a $0$: otherwise we could end up with an empty stack, and we don't want any gaps.

We can see that every arrangement has a unique sequence of instructions, and that every possible sequence of instructions corresponds to a unique arrangement of boxes. Thus the number of arrangements is equal to the number of length-$n$ binary strings that start with $0$; which is itself equal to the number of length-$(n-1)$ binary strings:

$$2^{n-1}$$

Answer 4

We're basically looking for the number of possible arrangements of vertical boxes whose sum of lengths give $n$. Let's imagine that there are $n$ 1s, with each linked to the adjacent 1. We can either cut a link or leave it as it is. The linked ones will be considered grouped together. Since there are $n-1$ links, we can leave them in $2$^$(n-1)$ ways.