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

Author

N. J. A. Sloane

Keywords

• nonn
• nice

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 /\

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

Examples

			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.
		

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

• 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

Crossrefs

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

Row sums of A259689.

Programs

Mathematica

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

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

Extensions

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

Offset changed by Roger Ford, Feb 09 2018