Stamp Folding

The number of ways of folding a strip of stamps has several possible variants. Considering only positions of the hinges for unlabeled stamps without regard to orientation of the stamps, the number of foldings is denoted $U(n)$. If the stamps are labeled and orientation is taken into account, the number of foldings is denoted $N(n)$. Finally, the number of symmetric foldings is denoted $S(n)$. The following table summarizes these values for the first $n$.

$n$	$S(n)$	$U(n)$	$N(n)$
Sloane	Sloane's A001010	Sloane's A001011	Sloane's A000136
1	1	1	1
2	2	1	2
3	2	2	6
4	4	5	16
5	6	14	50
6	8	38	144
7	18	120	462
8	20	353	1392
9	56	1148	4536
10	48	3527	14060

See also Map Folding

References

Gardner, M. ``The Combinatorics of Paper-Folding.'' In Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 60-73, 1983.

Ruskey, F. ``Information of Stamp Folding.'' http://sue.csc.uvic.ca/~cos/inf/perm/StampFolding.html.

Sloane, N. J. A. A Handbook of Integer Sequences. Boston, MA: Academic Press, p. 22, 1973.