OFFSET
1,3
COMMENTS
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 /\
//\\///\\\, //\\//\\/\ ///\\\//\\
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
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).
LINKS
Hunter Hogan, Table of n, a(n) for n = 1..49. (first 45 terms from Iwan Jensen.)
CombOS - Combinatorial Object Server, Generate meanders and stamp foldings
Philippe Di Francesco, Olivier Golinelli, and Emmanuel Guitter, Meander, Folding and Arch Statistics, arXiv:hep-th/9506030, 1995.
Philippe Di Francesco, Olivier Golinelli, and Emmanuel Guitter, Meanders: A Direct Enumeration Approach, arXiv:hep-th/9607039, 1996.
Philippe Di Francesco, Olivier Golinelli, and Emmanuel Guitter, Meanders: A Direct Enumeration Approach, Nuclear Physics B 482 (1996), no. 3, 497-535.
Philippe Di Francesco, Matrix Model Combinatorics: Applications to Folding and Coloring, arXiv:math-ph/9911002, 1999.
Hunter Hogan, mapFolding: Create, alter, and optimize algorithms to count meanders, stamp foldings, and map foldings, GitHub repository, 2026.
Andrew Howroyd, C# Software for the Enumeration of Meanders (includes semi-meanders), 2015.
Sean A. Irvine, Java program (github).
Iwan Jensen, ORCID author profile.
Iwan Jensen, Original values a(1)..a(45) (archived copy).
Iwan Jensen, A Transfer Matrix Approach to the Enumeration of Plane Meanders, arXiv:cond-mat/0008178 [cond-mat.stat-mech], 2000 (preprint).
Iwan Jensen, A Transfer Matrix Approach to the Enumeration of Plane Meanders, Journal of Physics A: Mathematical and General 33 (34) (2000), 5953-5963.
Iwan Jensen and Anthony J. Guttmann, Critical Exponents of Plane Meanders, arXiv:cond-mat/0004321 [cond-mat.stat-mech], 2000 (preprint).
Iwan Jensen and Anthony J. Guttmann, Critical Exponents of Plane Meanders, Journal of Physics A: Mathematical and General 33 (21) (2000), L187-L192.
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]
Joe Sawada and Roy Li, Stamp Foldings, Semi-Meanders, and Open Meanders: Fast Generation Algorithms, The Electronic Journal of Combinatorics 19 (2) (2012), #P43.
Joe Sawada, STAMP FOLDINGS, SEMI-MEANDERS, OPEN MEANDERS, C program, 2008.
J. Touchard, Contributions à l'étude du problème des timbres poste, Canad. J. Math., 2 (1950), 385-398.
FORMULA
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) = (n-1)! - Sum_{k=3..n-1} (A223094(k) * (n-1)! / k!). - Roger Ford, Aug 23 2024
From Hunter Hogan, Oct 12 2026: (Start)
a(n) = A001010(2*n-2)/2 for n >= 3.
a(n) = (2 - (n mod 2))*A227167(n)/n for n >= 3.
a(n) = (n-1)*a(n-1) - A223094(n-1) for n >= 3.
a(n) = a(n-1) + A333971(n+1)/4 for n >= 4.
a(n) = A334615(n) + 4*a(n-1) - 4*a(n-2) for n >= 4.
a(n) = A337581(n+2)/4 for n >= 3.
a(n) = Sum_{k=1..floor(n/2)} A400429(n,k) for n >= 2. (End)
EXAMPLE
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.
MATHEMATICA
a[n_] := A000136[[n]]/n;
Array[a, 45] (* Jean-François Alcover, Sep 06 2019 *)
PROG
(C) // Semi-meander generation algorithm; see Links, Sawada.
(C#) // Semi-meander transfer matrix; see Links, Howroyd.
(Java) /* implementation extending A005316; see Links, Irvine. */
(Python) from mapFolding.basecamp import countMeanders; print(countMeanders("semi", 5)) # See Links, Hogan.
CROSSREFS
Cf. A060206, A078591, A078592, A085973, A208357, A217310, A217318, A223093, A223094, A223095, A227167, A244312, A259702, A301620, A333971, A334615, A337581.
KEYWORD
nonn,nice,changed
AUTHOR
EXTENSIONS
Sade gives the first 11 terms. Computed to n = 45 by Iwan Jensen.
Offset changed by Roger Ford, Feb 09 2018
STATUS
approved
