login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000682 Semi-meanders: number of ways a semi-infinite directed curve can cross a straight line n times.
(Formerly M1205 N0464)
23
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 (list; graph; refs; listen; history; text; internal format)
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 a 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>=2, a(n) = 2^(n-2)+ Sum_{x=3..n-2} (2^(n-x-2)* A301620(x)). - Roger Ford, Apr 23 2018

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

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

W. F. Lunnon, A map-folding problem, Math. Comp. 22 (1968), 193-199.

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.

Index entries for sequences obtained by enumerating foldings

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.

CROSSREFS

A000560(n) = a(n+1)/2 (for n >= 2) gives number of nonisomorphic solutions (see also A086441).

Cf. A001011, A001997.

Row sums of A259689.

Sequence in context: A084078 A137842 A049146 * A001997 A239605 A000084

Adjacent sequences:  A000679 A000680 A000681 * A000683 A000684 A000685

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

Offset changed by Roger Ford, Feb 09 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 20:40 EDT 2018. Contains 316237 sequences. (Running on oeis4.)