A000136 Number of ways of folding a strip of n labeled stamps.

1, 2, 6, 16, 50, 144, 462, 1392, 4536, 14060, 46310, 146376, 485914, 1557892, 5202690, 16861984, 56579196, 184940388, 622945970, 2050228360, 6927964218, 22930109884, 77692142980, 258360586368, 877395996200, 2929432171328, 9968202968958, 33396290888520, 113837957337750

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• M. B. Wells, Elements of Combinatorial Computing. Pergamon, Oxford, 1971, p. 238.

Links

• T. D. Noe, Table of n, a(n) for n = 1..45
• Oswin Aichholzer, Florian Lehner, and Christian Lindorfer, Folding polyominoes into cubes, arXiv:2402.14965 [cs.CG], 2024. See p. 9.
• T. Asano, E. D. Demaine, M. L. Demaine and R. Uehara, NP-completeness of generalized Kaboozle, J. Information Processing, 20 (July, 2012), 713-718.
• CombOS - Combinatorial Object Server, Generate meanders and stamp foldings
• R. Dickau, Stamp Folding
• R. Dickau, Stamp Folding [Cached copy, pdf format, with permission]
• Thomas C. Hull, Adham Ibrahim, Jacob Paltrowitz, Natalya Ter-Saakov, and Grace Wang, The Stamp Folding Problem From a Mountain-Valley Perspective: Enumerations and Bounds, arXiv:2503.23661 [math.CO], 2025. See p. 1.
• J. E. Koehler, Folding a strip of stamps, J. Combin. Theory, 5 (1968), 135-152.
• J. E. Koehler, Folding a strip of stamps, J. Combin. Theory, 5 (1968), 135-152. [Annotated, corrected, scanned copy]
• Stéphane Legendre, The 16 foldings of 4 labeled stamps
• Bowie Liu, Dennis Wong, Chan-Tong Lam, and Marcus Im, Recursive and iterative approaches to generate rotation Gray codes for stamp foldings and semi-meanders, arXiv:2411.05458 [cs.DS], 2024. See p. 2.
• W. F. Lunnon, A map-folding problem, Math. Comp. 22 (1968), 193-199.
• David Orden, In how many ways can you fold a strip of stamps?, 2014.
• A. Panayotopoulos and P. Vlamos, Partitioning the Meandering Curves, Mathematics in Computer Science (2015) p 1-10.
• Frank Ruskey, Information on Stamp Foldings
• M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 41.
• M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 41. [Incomplete annotated scan of title page and pages 18-51]
• J. Sawada and R. Li, Stamp foldings, semi-meanders, and open meanders: fast generation algorithms, Electronic Journal of Combinatorics, Volume 19 No. 2 (2012), P#43 (16 pages).
• Eric Weisstein's World of Mathematics, Stamp Folding
• M. B. Wells, Elements of Combinatorial Computing, Pergamon, Oxford, 1971. [Annotated scanned copy of pages 237-240]
• Index entries for sequences obtained by enumerating foldings

Crossrefs

Cf. A000560, A000682.

Formula

a(n) = 2*n * A000560(n-1) for n >= 3.

a(n) = n * A000682(n). - Andrew Howroyd, Dec 06 2015