login
Number of ways of folding a strip of n labeled stamps.
(Formerly M1420 N0557)
9

%I M1420 N0557 #80 Sep 06 2019 11:08:01

%S 1,2,5,12,33,87,252,703,2105,6099,18689,55639,173423,526937,1664094,

%T 5137233,16393315,51255709,164951529,521138861,1688959630,5382512216,

%U 17547919924,56335234064,184596351277,596362337295,1962723402375

%N Number of ways of folding a strip of n labeled stamps.

%D A. Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D M. B. Wells, Elements of Combinatorial Computing. Pergamon, Oxford, 1971, p. 238.

%H T. D. Noe, <a href="/A000560/b000560.txt">Table of n, a(n) for n = 2..44</a> (derived from A000682)

%H CombOS - Combinatorial Object Server, <a href="http://combos.org/meander">Generate meanders and stamp foldings</a>

%H P. Di Francesco, O. Golinelli and E. Guitter, <a href="https://arxiv.org/abs/hep-th/9607039">Meanders: a direct enumeration approach</a>, arXiv:hep-th/9607039, 1996; Nucl. Phys. B 482 [FS] (1996), 497-535.

%H R. Dickau, <a href="http://www.robertdickau.com/stampfolding.html">Stamp Folding</a>

%H R. Dickau, <a href="/A000136/a000136_2.pdf">Stamp Folding</a> [Cached copy, pdf format, with permission]

%H I. Jensen, <a href="http://www.ms.unimelb.edu.au/~iwan/">Home page</a>

%H I. Jensen, <a href="http://dx.doi.org/10.1088/0305-4470/33/34/301">A transfer matrix approach to the enumeration of plane meanders</a>, J. Phys. A 33, 5953-5963 (2000).

%H I. Jensen and A. J. Guttmann, <a href="http://dx.doi.org/10.1088/0305-4470/33/21/101">Critical exponents of plane meanders</a> J. Phys. A 33, L187-L192 (2000).

%H J. E. Koehler, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80048-1">Folding a strip of stamps</a>, J. Combin. Theory, 5 (1968), 135-152.

%H W. F. Lunnon, <a href="http://dx.doi.org/10.1090/S0025-5718-1968-0221957-8">A map-folding problem</a>, Math. Comp. 22 (1968), 193-199.

%H David Orden, <a href="http://mappingignorance.org/2014/07/07/many-ways-can-fold-strip-stamps/">In how many ways can you fold a strip of stamps?</a>, 2014.

%H A. Panayotopoulos, P. Vlamos, <a href="https://doi.org/10.1007/s11786-015-0234-0">Partitioning the Meandering Curves</a>, Mathematics in Computer Science (2015) p 1-10.

%H Albert Sade, <a href="/A000108/a000108_17.pdf">Sur les Chevauchements des Permutations</a>, published by the author, Marseille, 1949. [Annotated scanned copy]

%H J. Sawada and R. Li, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p43">Stamp foldings, semi-meanders, and open meanders: fast generation algorithms</a>, Electronic Journal of Combinatorics, Volume 19 No. 2 (2012), P#43 (16 pages).

%H J. Touchard, <a href="http://dx.doi.org/10.4153/CJM-1950-035-6">Contributions à l'étude du problème des timbres poste</a>, Canad. J. Math., 2 (1950), 385-398.

%H M. B. Wells, <a href="/A000170/a000170.pdf">Elements of Combinatorial Computing</a>, Pergamon, Oxford, 1971. [Annotated scanned copy of pages 237-240]

%H <a href="/index/Fo#fold">Index entries for sequences obtained by enumerating foldings</a>

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

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

%t A000682 = Import["https://oeis.org/A000682/b000682.txt", "Table"][[All, 2]];

%t a[n_] := A000682[[n + 1]]/2;

%t a /@ Range[2, 44] (* _Jean-François Alcover_, Sep 03 2019 *)

%t A000136 = Import["https://oeis.org/A000136/b000136.txt", "Table"][[All, 2]];

%t a[n_] := A000136[[n + 1]]/(2 n + 2);

%t a /@ Range[2, 44] (* _Jean-François Alcover_, Sep 06 2019 *)

%Y Cf. A000136, A000682, A001011.

%K nonn,nice

%O 2,2

%A _N. J. A. Sloane_, _Stéphane Legendre_

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