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

1, 2, 5, 12, 33, 87, 252, 703, 2105, 6099, 18689, 55639, 173423, 526937, 1664094, 5137233, 16393315, 51255709, 164951529, 521138861, 1688959630, 5382512216, 17547919924, 56335234064, 184596351277, 596362337295, 1962723402375

Offset: 2

Author

N. J. A. Sloane, Stéphane Legendre

Keywords

• nonn
• nice

References

• A. Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949.
• 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 = 2..44 (derived from A000682)
• CombOS - Combinatorial Object Server, Generate meanders and stamp foldings
• P. Di Francesco, O. Golinelli and E. Guitter, Meanders: a direct enumeration approach, arXiv:hep-th/9607039, 1996; Nucl. Phys. B 482 [FS] (1996), 497-535.
• R. Dickau, Stamp Folding
• R. Dickau, Stamp Folding [Cached copy, pdf format, with permission]
• I. Jensen, Home page
• I. Jensen, A transfer matrix approach to the enumeration of plane meanders, J. Phys. A 33, 5953-5963 (2000).
• I. Jensen and A. J. Guttmann, Critical exponents of plane meanders J. Phys. A 33, L187-L192 (2000).
• J. E. Koehler, Folding a strip of stamps, J. Combin. Theory, 5 (1968), 135-152.
• 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, P. Vlamos, Partitioning the Meandering Curves, Mathematics in Computer Science (2015) p 1-10.
• Albert Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949. [Annotated scanned copy]
• 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).
• J. Touchard, Contributions à l'étude du problème des timbres poste, Canad. J. Math., 2 (1950), 385-398.
• 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. A000136, A000682, A001011.

Programs

Mathematica

A000682 = Import["https://oeis.org/A000682/b000682.txt", "Table"][[All, 2]];
a[n_] := A000682[[n + 1]]/2;
a /@ Range[2, 44] (* Jean-François Alcover, Sep 03 2019 *)
A000136 = Import["https://oeis.org/A000136/b000136.txt", "Table"][[All, 2]];
a[n_] := A000136[[n + 1]]/(2 n + 2);
a /@ Range[2, 44] (* Jean-François Alcover, Sep 06 2019 *)

Formula

a(n) = (1/2)*A000682(n+1) for n >= 2.

a(n) = A000136(n+1)/(2*n+2) for n >= 2. - Jean-François Alcover, Sep 06 2019 (from formula in A000136)

Extensions

Computed to n = 45 by Iwan Jensen - see link in A000682.