# Stamp Folding

A nice problem in combinatorics is to count the number of ways to fold a strip of n labeled stamps into a stack one stamp wide. The “labeled” part is important; the counts are different if only the positions of the perforated connections are distinguishable, for example.

For strips of 1, 2, and 3 stamps, a stack corresponding to every permutation of stamps exists.

With n ≥ 4 stamps, however, not all n! permutations are valid stamp foldings. The figures below with a shaded background are impossible foldings, as they would require some perforations that join adjacent stamps to intersect.

After removing the impossible figures, the following 16 stacks remain.

And here are the 50 stacks that can be made from 5 stamps.

There seems not to be a closed-form formula to compute the counts of labeled stamp foldings, though many have tried.

If you kind of liked this, you’ll kind of love map foldings, unlabeled stamp foldings, symmetric stamp foldings, or symmetric unlabeled stamp foldings.

See Martin Gardner, Wheels, Life and Other Mathematical Amusements, pp. 60–61, 1983.

Figures created with Mathematica 7.