A000136 -id:A000136 - cp's OEIS frontend

A000682 Semi-meanders: number of ways a semi-infinite directed curve can cross a straight line n times.

1, 1, 2, 4, 10, 24, 66, 174, 504, 1406, 4210, 12198, 37378, 111278, 346846, 1053874, 3328188, 10274466, 32786630, 102511418, 329903058, 1042277722, 3377919260, 10765024432, 35095839848, 112670468128, 369192702554, 1192724674590, 3925446804750

Offset: 1

N. J. A. Sloane

For n > 1, the number of permutations of n letters without overlaps [Sade, 1949]. - N. J. A. Sloane, Jul 05 2015
Number of ways to fold a strip of n labeled stamps with leaf 1 on top. [Clarified by Stéphane Legendre, Apr 09 2013]
From Roger Ford, Jul 04 2014: (Start)
The number of semi-meander solutions for n (a(n)) is equal to the number of n top arch solutions in the intersection of A001263 (with no intersecting top arches) and A244312 (arches forming a complete loop).
The top and bottom arches for semi-meanders pass through vertices 1-2n on a straight line with the arches below the line forming a rainbow pattern.
The number of total arches going from an odd vertex to a higher even vertex must be exactly 2 greater than the number of arches going from an even vertex to a higher odd vertex to form a single complete loop with no intersections.
The arch solutions in the intersection of A001263 (T(n,k)) and A244312 (F(n,k)) occur when the number of top arches going from an odd vertex to a higher even vertex (k) meets the condition that k = ceiling((n+1)/2).
Example: semi-meanders a(5)=10.
(A244312) F(5,3)=16 { 10 common solutions: [12,34,5 10,67,89] [16,23,45,78,9 10] [12,36,45,7 10,89] [14,23,58,67,9 10] [12,3 10,49,58,67] [18,27,36,45,9 10] [12,3 10,45,69,78] [18,25,34,67,9 10] [14,23,5 10,69,78] [16,25,34,7 10,89] } + [18,27,34,5 10,69] [16,25,3 10,49,78] [18,25,36,49,7 10] [14,27,3 10,58,69] [14,27,36,5 10,89] [16,23,49,58,7 10]
(A001263) T(5,3)=20  { 10 common solutions } + [12,38,45,67,9 10] [1 10,29,38,47,56] [1 10,25,34,69,78] [14,23,56,7 10,89] [12,3 10,47,56,89] [18,23,47,56,9 10] [1 10,29,36,45,78] [1 10,29,34,58,67] [1 10,27,34,56,89] [1 10,23,49,56,78].
(End)
From Roger Ford, Feb 23 2018: (Start)
For n>1, the number of semi-meanders with n top arches and k concentric starting arcs is a(n,k)= A000682(n-k).
                             /\          /\
Examples:  a(5,1)=4         //\\        /  \          /\
     A000682(5-1)=4        ///\\\      /  /\\        /  \       /\  /\
                        /\////\\\\, /\//\//\\\, /\/\//\/\\, /\ //\\//\\
           a(5,2)=2        /\                      a(5,3)=1   /\
     A000682(5-2)=2   /\  //\\    /\  /\     A000682(5-3)=1  //\\  /\
                     //\\///\\\, //\\//\\/\                 ///\\\//\\
           a(5,4)=1     /\
     A000682(5-4)=1    //\\
                      ///\\\
                     ////\\\\/\.   (End)
For n >= 4, 4*a(n-2) is the number of stamp foldings with leaf 1 on top, with leaf 2 in the second or n-th position, and with leaf n and leaf n-1 adjacent. Example for n = 5, 4*a(5-2) = 8: 12345, 12354, 12453, 12543, 13452, 13542, 14532, 15432. - Roger Ford, Aug 05 2019
From Martin Philp, Mar 25 2021: (Start)
The condition of having leaf n and leaf n-1 adjacent is the same as having one fewer leaf, and then counting each element twice. So the above comment is equivalent to saying:
For n >= 3, 2*a(n-1) is the number of stamp foldings with leaf 1 on top and leaf 2 in the second or n-th position. Example for n = 4, 2*a(4-1) = 4: 1234, 1243, 1342, 1432. Furthermore the number of stamp foldings with leaf 1 on top and leaf 2 in the n-th position is the same as the number of stamp foldings with leaf 1 on top and leaf 2 in the second position, as a cyclic rotation of 1 and mirroring the sequence maps one to the other. 1234, 1243 <-rot-> 2341, 2431 <-mirror-> 1432, 1342.
Hence, for n >= 2, a(n-1) is the number of stamp foldings having 1 and 2 (in this order) on top.
Not only is a(n) the number of stamp foldings with 1 on top, it is the number of stamp foldings with any particular leaf on top. This explains why A000136(n)= n*a(n).
(End)
The number of semi-meanders that in the first exterior top arch has exactly one arch of length one = Sum_{k=1..n-1} a(k).  Example: for n = 5, Sum_{k=1..4} A000682(k) = 8, 10 = arch of length one, *start and end of first exterior top arch*; *10*11001100, *10*11110000, *10*11011000, *10*10110100, *1100*111000, *1100*110010, *111000*1100, *11110000*10. - Roger Ford, Jul 12 2020

			a(4) = 4: the four solutions with three crossings are the two solutions shown in A086441(3) together with their reflections about a North-South axis.

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).

I. Jensen, Table of n, a(n) for n = 1..45
CombOS - Combinatorial Object Server, Generate meanders and stamp foldings
P. Di Francesco, O. Golinelli and E. Guitter, Meander, folding and arch statistics, arXiv:hep-th/9506030, 1995.
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.
P. Di Francesco, Matrix model combinatorics: applications to folding and coloring, arXiv:math-ph/9911002, 1999.
I. Jensen, Home page
I. Jensen, Terms a(1)..a(45)
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.
J. E. Koehler, Folding a strip of stamps, J. Combin. Theory, 5 (1968), 135-152. [Annotated, corrected, scanned copy]
M. La Croix, Approaches to the Enumerative Theory of Meanders
Stéphane Legendre, Foldings and Meanders, arXiv preprint arXiv:1302.2025 [math.CO], 2013.
Stéphane Legendre, Illustration of initial terms
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.
A. Panayotopoulos and 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.
Index entries for sequences obtained by enumerating foldings

Cf. A000136, A001011, A001997, A000560 (nonisomorphic), A086441.

Row sums of A259689.

A000136 = Import["https://oeis.org/A000136/b000136.txt", "Table"][[All, 2]];
a[n_] := A000136[[n]]/n;
Array[a, 45] (* Jean-François Alcover, Sep 06 2019 *)

a(n) = 2*A000560(n-1) for n >= 3.
For n >= 2, a(n) = 2^(n-2) + Sum_{x=3..n-2} (2^(n-x-2)*A301620(x)). - Roger Ford, Apr 23 2018
a(n) = 2^(n-2) + Sum_{j=4..n-1} (Sum_{k=3..floor((j+2)/2)} (A259689(j,k)*(k-2)*2^(n-1-j))). - Roger Ford, Dec 12 2018
a(n) = A000136(n)/n. - Jean-François Alcover, Sep 06 2019, from formula in A000136.
a(n) = (n-1)! - Sum_{k=3..n-1} (A223094(k) * (n-1)! / k!). - Roger Ford, Aug 23 2024

Sade gives the first 11 terms. Computed to n = 45 by Iwan Jensen.

Offset changed by Roger Ford, Feb 09 2018

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

Original entry on oeis.org

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

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

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.

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

Cf. A000136, A000682, A001011.

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 *)

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)

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

A001011 Number of ways to fold a strip of n blank stamps.

Original entry on oeis.org

1, 1, 2, 5, 14, 38, 120, 353, 1148, 3527, 11622, 36627, 121622, 389560, 1301140, 4215748, 14146335, 46235800, 155741571, 512559195, 1732007938, 5732533570, 19423092113, 64590165281, 219349187968, 732358098471, 2492051377341, 8349072895553, 28459491475593

Offset: 1

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

M. Gardner, Mathematical Games, Sci. Amer. Vol. 209 (No. 3, Mar. 1963), p. 262.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence - see entry 576, Fig. 17, and the front cover).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..45 [from S. Legendre, 2013]
B. Bobier and J. Sawada, A fast algorithm to generate open meandric systems and meanders, Transactions on Algorithms, Vol. 6 No. 2 (2010) 12 pages.
S. P. Castell, Computer Puzzles, Computer Bulletin, March 1975, pages 3, 33, 34. [Annotated scanned copy]
CombOS - Combinatorial Object Server, Generate meanders and stamp foldings.
Santo Diano, Letter to N. J. A. Sloane, circa Dec 01 1979.
R. Dickau, Stamp Folding.
R. Dickau, Stamp Folding. [Cached copy, PDF format, with permission]
R. Dickau, Unlabeled Stamp Foldings.
R. Dickau, Unlabeled Stamp Foldings. [Cached copy, PDF format, with permission]
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
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]
S. Legendre, Foldings and Meanders, arXiv preprint arXiv:1302.2025 [math.CO], 2013.
S. Legendre, Foldings and Meanders, Aust. J. Comb. 58(2), 275-291, 2014.
David Orden, In how many ways can you fold a strip of stamps?, 2014.
Frank Ruskey, Information on Stamp Foldings.
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).
N. J. A. Sloane, Illustration of initial terms. (Fig. 17 of the 1973 Handbook of Integer Sequences. The initial terms are also embossed on the front cover.)
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 2.
Eric Weisstein's World of Mathematics, Stamp Folding.
Index entries for sequences obtained by enumerating foldings

Cf. A000682, A086441.

A000136 = Import["https://oeis.org/A000136/b000136.txt", "Table"][[All, 2]];
A001010 = Cases[Import["https://oeis.org/A001010/b001010.txt", "Table"], {, }][[All, 2]];
a[n_] := If[n == 1, 1, (A001010[[n]] + A000136[[n]])/4];
Array[a, 45] (* Jean-François Alcover, Sep 04 2019 *)

a(n) = (A001010(n) + A000136(n)) / 4 for n >= 2. - Andrew Howroyd, Dec 07 2015

a(17) and a(20) corrected by Sean A. Irvine, Mar 17 2013

A001417 Number of ways of folding a 2 X 2 X ... X 2 n-dimensional map.

Original entry on oeis.org

1, 2, 8, 96, 4608, 798720, 361267200, 362794844160

Offset: 0

N. J. A. Sloane

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).

W. F. Lunnon, Multi-dimensional map-folding, Computer Journal 14 1971 75-80.
Index entries for sequences obtained by enumerating foldings

Cf. A000136, A000560, A195646, A001418.

a(7) from Sean A. Irvine, Dec 21 2017

A001418 Number of ways of folding an n X n sheet of stamps.

Original entry on oeis.org

1, 8, 1368, 300608, 186086600, 123912532224, 129950723279272

Offset: 1

N. J. A. Sloane

			For n = 2 the a(2) = 8 foldings of a sheet labeled 1234 in reading order are 1243, 1342, 2134, 2431, 3124, 3421, 4213, 4312.

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).

W. F. Lunnon, Multi-dimensional map-folding, Computer Journal 14 1971 75-80.
Eric Weisstein's World of Mathematics, Map Folding.
Index entries for sequences obtained by enumerating foldings.

Cf. A000136, A000560, A001417, A195646.

a(6)-a(7) from Sean A. Irvine, Jan 11 2018

Offset corrected by Anders Kaseorg, Nov 29 2024

A195646 Number of ways of folding a 3 X 3 X ... X 3 n-dimensional map.

Original entry on oeis.org

1, 6, 1368, 85109616

Offset: 0

N. J. A. Sloane, Sep 21 2011

W. F. Lunnon, A map-folding problem, Math. Comp. 22 (1968), 193-199.
W. F. Lunnon, Multi-dimensional map-folding, The Computer Journal, Volume 14, Issue 1, 1971, Pages 75-80.
Index entries for sequences obtained by enumerating foldings

Cf. A000136, A000560, A001417, A001418.

A223093 Number of foldings of n labeled stamps in which leaf 1 is inwards and leaf n outwards (or leaf 1 outwards and leaf n inwards).

Original entry on oeis.org

0, 0, 2, 4, 16, 38, 132, 342, 1144, 3134, 10370, 29526, 97458, 285458, 942920, 2822310, 9341008, 28440970, 94358558, 291294678, 968853072, 3025232480, 10086634316, 31797822936, 106265437078, 337731551446, 1131117792978, 3620119437762, 12148796744234, 39118879440938

Offset: 1

N. J. A. Sloane, Mar 29 2013

nonn

Subset of foldings of n labeled stamps (A000136). - Stéphane Legendre, Apr 09 2013

Stéphane Legendre, Table of n, a(n) for n = 1..42
S. Legendre, Foldings and Meanders, arXiv preprint arXiv:1302.2025 [math.CO], 2013.
S. Legendre, Foldings and Meanders, Aust. J. Comb. 58(2), 275-291, 2014.
Index entries for sequences obtained by enumerating foldings

A000682 = Cases[Import["https://oeis.org/A000682/b000682.txt", "Table"], {, }][[All, 2]];
A077014 = Cases[Import["https://oeis.org/A077014/b077014.txt", "Table"], {, }][[All, 2]];
a[n_] := A000682[[n + 1]] - A077014[[n + 1]];
Array[a, 30] (* Jean-François Alcover, Sep 07 2019, after Andrew Howroyd *)

a(n) = A000682(n+1) - A077014(n). - Andrew Howroyd, Dec 06 2015

A217310(n) = 2*a(n) if n is odd and A217310(n) = a(n) if n is even. - Stéphane Legendre, Jan 09 2014

Name clarified by Stéphane Legendre, Apr 09 2013

More terms from Stéphane Legendre, Apr 09 2013

cp's OEIS Frontend

A195645 Erroneous version of A000136.

Views

Author

Keywords

Comments

References

A213429 Erroneous version of A000136.

Views

Author

Keywords

Comments

References

A213439 A000136(n)/2.

Views

Author

Keywords

References

Crossrefs

A000682 Semi-meanders: number of ways a semi-infinite directed curve can cross a straight line n times.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A001011 Number of ways to fold a strip of n blank stamps.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A001417 Number of ways of folding a 2 X 2 X ... X 2 n-dimensional map.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A001418 Number of ways of folding an n X n sheet of stamps.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A195646 Number of ways of folding a 3 X 3 X ... X 3 n-dimensional map.

Views

Author

Keywords

Links

Crossrefs

A223093 Number of foldings of n labeled stamps in which leaf 1 is inwards and leaf n outwards (or leaf 1 outwards and leaf n inwards).

Views

Author