Map folding

In the mathematics of paper folding, map folding and stamp folding are two problems of counting the number of ways that a piece of paper can be folded. In the stamp folding problem, the paper is a strip of stamps with creases between them, and the folds must lie on the creases. In the map folding problem, the paper is a map, divided by creases into rectangles, and the folds must again lie only along these creases.

Lucas (1891) credits the invention of the stamp folding problem to Émile Lemoine.Touchard (1950) provides several other early references.

In the stamp folding problem, the paper to be folded is a strip of square or rectangular stamps, separated by creases, and the stamps can only be folded along those creases. In one commonly considered version of the problem, each stamp is considered to be distinguishable from each other stamp, so two foldings of a strip of stamps are considered equivalent only when they have the same vertical sequence of stamps. For example, there are six ways to fold a strip of three different stamps:

These include all six permutations of the stamps, but for more than three stamps not all permutations are possible. If, for a permutation p, there are two numbers i and j with the same parity such that the four numbers i, j, i + 1, and j + 1 appear in p in that cyclic order, then p cannot be folded. The parity condition implies that the creases between stamps i and i + 1, and between stamps j and j + 1, appear on the same side of the stack of folded stamps, but the cyclic ordering condition implies that these two creases cross each other, a physical impossibility. For instance, the four-element permutation 1324 cannot be folded, because it has this forbidden pattern with i = 1 and j = 3. All remaining permutations, without this pattern, can be folded. The number of different ways to fold a strip of n stamps is given by the sequence

...
Wikipedia