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.
Just to run it into the ground, here are the 50 stacks that can be made from 5 stamps.
There doesn’t seem to be a closed-form formula for computing these counts.
If you kind of liked this, you’ll kind of love map foldings or unlabeled stamp foldings.
See Martin Gardner, Wheels, Life and Other Mathematical Amusements, pp. 60–61, 1983.
Figures created with Mathematica 7.
Copyright © 2010–2012 Robert Dickau. All rights reserved, no responsibilities accepted.
[ home ] || [ 100801 ]
www.robertdickau.com/stampfolding.html