A001011 -id:A001011 - 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

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

Original entry on oeis.org

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

N. J. A. Sloane

nonn

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 = 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

Cf. A000560, A000682.

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

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

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.

A001010 Number of symmetric foldings of a strip of n stamps.

Original entry on oeis.org

1, 2, 2, 4, 6, 8, 18, 20, 56, 48, 178, 132, 574, 348, 1870, 1008, 6144, 2812, 20314, 8420, 67534, 24396, 225472, 74756, 755672, 222556, 2540406, 693692, 8564622, 2107748, 28941258, 6656376, 98011464, 20548932, 332523306, 65573260, 1130110294, 205022836, 3846372944, 659806116, 13109737832, 2084555444, 44735866296, 6755838520

Offset: 1

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

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

Jean-François Alcover, Table of n, a(n) for n = 1..52
R. Dickau, Symmetric Stamp Foldings
R. Dickau, Symmetric Stamp Foldings [Cached copy, pdf format, with permission]
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]
Frank Ruskey, Information on Stamp Foldings
Eric Weisstein's World of Mathematics, Stamp Folding.
Index entries for sequences obtained by enumerating foldings

Cf. A007822, A000682.

A000682 = Import["https://oeis.org/A000682/b000682.txt", "Table"][[All, 2]];
A007822 = Cases[Import["https://oeis.org/A007822/b007822.txt", "Table"], {, }][[All, 2]];
a[n_] := Which[n == 1, 1, EvenQ[n], 2*A000682[[n/2 + 1]], OddQ[n], 2*A007822[[(n - 1)/2 + 1]]];
Array[a, 52] (* Jean-François Alcover, Sep 03 2019, updated Jul 13 2022 *)

a(1) = 1, a(2n-1) = 2*A007822(n), a(2n) = 2*A000682(n+1). - Sean A. Irvine, Mar 18 2013; corrected by Hunter Hogan, Aug 08 2025

A086441 Number of inequivalent ways a semi-infinite curve can cross a straight line n times.

Original entry on oeis.org

1, 1, 2, 4, 11, 27, 79, 213, 644, 1840, 5660

Offset: 1

N. J. A. Sloane, Sep 09 2003

This uses a too broad notion of equivalence. Besides the obvious reflection in a plane perpendicular to the straight line, if the end of the curve is in a free region of the plane, it is extended to infinity and the direction of the curve can then be reversed. A000560 uses a better definition of equivalence.

			The a(3) = 2 solutions with 3 crossings. The line is drawn horizontally. The curve starts at oo and ends at X. The crossings are indicated by stars.
       --        X
      /  \      /
-----*----*----*----
    /      \  /
   /        --
  /
oo
         ---
        /   \
       /  X  \
      /   |   \
-----*----*----*----
    /     |   /
   /      .---
  /
oo

Index entries for sequences obtained by enumerating foldings

Isomorphism classes (using too generous a definition of isomorphism) from A000682. Cf. A000560, A001011.

A110837 Number of ways to fold a strip of n stamps taking account of order and direction of folds.

Original entry on oeis.org

1, 2, 8, 36, 176, 864, 4304, 21448, 107168, 535488, 2677088, 13383712, 66916832, 334575552, 1672869152, 8364302864, 41821471424, 209107142784, 1045535499584, 5227676426944, 26138381063744, 130691899964544, 653459494468544, 3267297445575296, 16336487201109056

Offset: 1

Henry Bottomley, Sep 16 2005

nonn

			a(3) = 8 since with an initial strip of three stamps there are two possible folding positions for the initial fold, each of which could be folded up or down, so there are four possible initial folds, each leaving one possible folding position which can be folded up or down, making eight possible folding patterns.

Seiichi Manyama, Table of n, a(n) for n = 1..1000
Index entries for sequences obtained by enumerating foldings

Cf. A001011, A075496.

a:= proc(n) option remember; `if`(n=1, 1,
      2*add(max(a(k), a(n-k)), k=1..n-1))
    end:
seq(a(n), n=1..25);  # Alois P. Heinz, Jan 08 2023

a[n_] := a[n] = If[n==1, 1, 2*Sum[Max[a[k], a[n-k]], {k, 1, n-1}]];
Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Jan 10 2023, after Alois P. Heinz *)

a(n) = 2 * Sum_{0

a(n) ~ 0.054816154756...*5^n.

A371606 Number of ways to fold with complete turns a strip of n blank double-sided sticky stamps.

Original entry on oeis.org

1, 1, 2, 5, 14, 38, 116, 337, 1024, 3022, 9068, 26736, 79165, 231933, 679344, 1976199, 5738101

Offset: 1

Klemen Klanjscek, Mar 29 2024

The unlabeled sticky stamps have glue on both sides. Once two stamps are glued they cannot be separated. When constructing a folding we are not allowed to make partial folds (turns less than 180 degrees).

First 6 terms agree with the sequence A001011, afterwards a(n) < A001011(n).

			For n = 7 foldings (1 6 5 4 3 2 7), (4 5 6 1 7 2 3), (3 4 5 6 1 7 2), and (1 7 2 3 4 5 6) cannot be produced if stamps are sticky on both sides and we are only allowed to do complete folds. If stamps are not sticky and we are still only allowed to do complete folds, these foldings are still possible. For example, folding strategy for (1 6 5 4 3 2 7):
Unfolded:
 <1--2--3--4--5--6--7>
Step 1:
 /-3--4--5--6--7>
 \-2--1>
 Step 2:
 <7--6--5--4-\
         /-3-/
         \-2--1>
Step 3:
 <7--6-\
   /-5-/
   \-4-\
   /-3-/
   \-2--1>
Step 4:
 /---6-\
 | /-5-/
 | \-4-\
 | /-3-/
 | \-2--1>
 \---7>
Step 5:
    <1---\
 /---6-\ |
 | /-5-/ |
 | \-4-\ |
 | /-3-/ |
 | \-2---/
 \---7>
If stamps are sticky, this strategy fails, because after the first step stamps 1 and 4 cannot be separated (every other strategy also fails).

Klemen Klanjscek, Python program for counting sticky unlabeled stamp foldings

Cf. A001011.

Python
```
# See Link
```

a(15)-a(17) from Klemen Klanjscek, Jul 09 2024

Showing 1-8 of 8 results.

cp's OEIS Frontend

A003054 Erroneous version of A001011 ("folding a strip of stamps").

Views

Author

Keywords

References

Links

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

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

Views

Author

Keywords

References

Links

Crossrefs

Formula

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A001010 Number of symmetric foldings of a strip of n stamps.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A086441 Number of inequivalent ways a semi-infinite curve can cross a straight line n times.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A110837 Number of ways to fold a strip of n stamps taking account of order and direction of folds.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A371606 Number of ways to fold with complete turns a strip of n blank double-sided sticky stamps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions