A square piece of paper is folded in half along a line of symmetry. The resulting shape is then folded in half along a line of symmetry of the new shape. This process is repeated until $n$ folds have been made, giving a sequence of $n+1$ shapes. If we do not distinguish between congruent shapes, find the number of possible sequences when:
(a) $n=3$;
(b) $n=6$;
(c) $n=9$.
(When $n=1$ there are two possible sequences.)
Solution
We classify the sequences of shapes according to the final shape in the sequence and make the following observations:
- The final shape can be an isosceles triangle if and only if the penultimate shape is either an isosceles triangle or a square.
- The final shape can be a square if and only if the penultimate shape is a rectangle in the ratio $1: 2$.
- The final shape can be a rectangle in the ratio $1: 2^{k}$ for $n \geq 1$ if and only if the penultimate shape is a rectangle in the ratio $1: 2^{k-1}$ or $1: 2^{k+1}$.

We now construct the Pascal-like triangle below.
\begin{tabular}{c|ccccccccccc|c}
$n$ & $\Delta$ & $\square$ & $1: 2$ & $1: 4$ & $1: 8$ & $1: 16$ & $1: 32$ & $1: 64$ & $1: 128$ & $1: 256$ & $1: 512$ & $\Sigma$ \\
\hline 0 & & 1 & & & & & & & & & & 1 \\
1 & 1 & & 1 & & & & & & & & & 2 \\
2 & 1 & 1 & & 1 & & & & & & & & 3 \\
3 & 2 & & 2 & & 1 & & & & & & & 5 \\
4 & 2 & 2 & & 3 & & 1 & & & & & & 8 \\
5 & 4 & & 5 & & 4 & & 1 & & & & & 14 \\
6 & 4 & 5 & & 9 & & 5 & & 1 & & & & 24 \\
7 & 9 & & 14 & & 14 & & 6 & & 1 & & & 44 \\
8 & 9 & 14 & & 28 & & 20 & & 7 & & 1 & & 79 \\
9 & 23 & & 42 & & 48 & & 27 & & 8 & & 1 & 149
\end{tabular}

Each entry is the number of $n$-fold sequences whose final shape is given by the column heading. The first two columns count sequences ending in isosceles triangles and squares respectively, the remaining columns count sequences ending in proper rectangles.

The observations above mean that:
- Each entry in the $\Delta$ column is the sum of entries in the $\Delta$ and $\square$ columns in the row above.
- Each entry in the $\square$ column is equal to the entry in the $1: 2$ column in the row above.
- Each entry in the other columns is equal to the sum of the two entries 'diagonally above' it.

The answers can now be read off from the final column of the table, which records the sum of the entries in each row.
(a) 3 folds, 5 sequences; (b) 6 folds, 24 sequences; (c) folds, 149 sequences.

Alternative
There is a short cut: each number in the table contributes to two numbers in the row below, apart from the $\Delta$ column which only contributes to one. Therefore each row sum is twice the previous row sum minus the $\Delta$ number in the previous row. Thus we can work out all the relevant row sums by calculating with the much reduced table below.
\begin{tabular}{l|ccccc|c}
$n$ & $\Delta$ & $\square$ & $1: 2$ & $1: 4$ & $1: 8$ & $\Sigma$ \\
\hline 0 & & 1 & & & & 1 \\
1 & 1 & & 1 & & & 2 \\
2 & 1 & 1 & & 1 & & 3 \\
3 & 2 & & 2 & & 1 & 5 \\
4 & 2 & 2 & & 3 & & 8 \\
5 & 4 & & 5 & & & 14 \\
6 & 4 & 5 & & & & 24 \\
7 & 9 & & & & & 44 \\
8 & 9 & & & & & 79 \\
9 & & & & & & 149
\end{tabular}

REMARK
There is a good deal more to explore in this question. For example, it turns out that the entries in the right hand portion of the table can be obtained by starting with a copy of Pascal's triangle and subtracting a second, slightly offset, copy of the same triangle. This can be verified by induction, but a direct counting argument is not so easy to come by.

One consequence of this observation is that the number of paths of length $2 k$ which end in a square is given by $\binom{2 k}{k}-\binom{2 k}{k-1}=\frac{1}{k+1}\binom{2 k}{k}$. These are the Catalan numbers which occur in a huge variety of different counting problems and certainly merit further reading.
If we call number of sequences ending in a triangle after either $2 k$ or $2 k-1$ folds $t_{k}$, we obtain the sequence $1,2,4,9,23, \ldots$ The $n$th term is simply the sum of the first $n$ Catalan numbers, but the sequence also satisfies the relation $t_{k+1}=\frac{1}{k+1}\left((5 k-1) t_{k}-(4 k-2) t_{k-1}\right)$ which can be used to solve the original problem for much larger numbers of folds.