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

A259702 Row sums of A259701 except first column.

Original entry on oeis.org

0, 0, 0, 1, 2, 9, 21, 78, 199, 699, 1889, 6491, 18261, 62145, 180091, 610220, 1809045, 6118849, 18469079, 62440111, 191235803, 646681908, 2004592956, 6782895492, 21239394216, 71925883149, 227169634741, 769998727785, 2450045838331, 8312417389237, 26620229804149

Offset: 2

N. J. A. Sloane, Jul 05 2015

nonn

Albert Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949. [Annotated scanned copy]

Cf. A259701.

Cf. A301620 (essentially twice this sequence).

A000682 = Import["https://oeis.org/A000682/b000682.txt", "Table"][[All, 2]];
a[n_] := If[n <= 2, 0, A000682[[n]]/2 - A000682[[n - 1]]];
a /@ Range[2, 32] (* Jean-François Alcover, Sep 03 2019, from A301620 *)

a(n) = A000682(n)/2 - A000682(n-1) for n > 2.

a(12) from Andrew Howroyd, Dec 07 2018

More terms (using the terms of A301620) from Joerg Arndt, Dec 25 2018

A339179 Irregular triangle read by rows: for n >= 2, 2 <= k <= floor(n/2) + 1, T(n,k) = the number of semi-meanders with n top arches, a first arch of length one and k arch groupings.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 4, 2, 10, 10, 4, 24, 24, 14, 4, 66, 66, 34, 8, 174, 174, 106, 42, 8, 504, 504, 284, 98, 16, 1406, 1406, 878, 390, 114, 16, 4210, 4210, 2486, 1002, 258, 32, 12198, 12198, 7738, 3652, 1270, 290, 32, 37378, 37378, 22714, 9962, 3140, 642, 64, 111278, 111278, 71370, 34986, 13370, 3794, 706, 64

Offset: 2

Roger Ford, Nov 26 2020

			For n = 6:   /\ = arch of length one;
       /\             /\             /\             /\
      /  \           //\\           /  \           //\\       4 with 2 groupings
     /  /\\         //  \\         /    \         ///\\\
    /  /  \\       //  /\\\       //\  /\\       ////\\\\
/\ //\//\/\\\, /\ ///\//\\\\, /\ ///\\//\\\, /\ /////\\\\\,
         /\                                              /\
        //\\              /\         /\                 /  \  4 with 3 groupings
       ///\\\       /\   //\\       //\\   /\          //\  \
/\ /\ ////\\\\, /\ //\\ ///\\\, /\ ///\\\ //\\, /\ /\ ///\\/\\,
           /\                                                 2 with 4 groupings
          /  \       /\      /\
/\ /\ /\ //\/\\, /\ //\\ /\ //\\,             T(6,2) = 4, T(6,3) = 4, T(6,4) = 2;
Irregular triangle begins:
    n\k (2) (3) (4) (5) (6)
    2:   1
    3:   1
    4:   1   1
    5:   2   2
    6:   4   4   2
    7:   10  10  4
    8:   24  24  14  4
    9:   66  66  34  8
   10:   174 174 106 42  8
         ...

Cf. A259689, A301620, Row sums: A000682(n-1).

T(2,2) = T(3,2) = 1.
For n >= 4, T(n,2) = T(n,3) = A000682(n-2).
For n >= 6 and k >= 4, T(n,k) = Sum {x = k-1..floor(n/2)} (A259689(T(n-2,x))).
For n >= 4, A301620(n-3) = Sum {k = 4..floor((n+2)/2)} (T(n,k)).

A334615 a(n) is the number of semi-meanders with n top arches that has no arch of length 1 at the ends of the top arch configuration and no arch of length 1 adjacent to the center of the top arch configuration.

Original entry on oeis.org

0, 0, 0, 2, 0, 10, 6, 72, 86, 602, 982, 5426, 10558, 51246, 111602, 500076, 1177210, 5001518, 12462762, 51003906, 132711162, 528420604, 1422458280, 5547419160, 15347206464

Offset: 2

Roger Ford, Sep 08 2020

The number of semi-meanders with n top arches is A000682(n). If a formula for a(n) could be found without using the values for A000682(n) or A301620(n) then there would be a recursive formula for semi-meanders with n top arches.

			For n = 7: a(7) = 10.  11111000001100, 11110000111000, 11110000101100, 11101000110100, 11100011110000, 11100011100100, 11011000111000, 11010011101000, 11001111100000, 11001011110000.       /\
                                       /  \
                                      / /\ \
      11001011110000 -->   /\        / //\\ \    10 = arch length 1
                          //\\  /\  / ///\\\ \
                         end   center|      end
                         11       01  11    00    no 10 in designated positions.

Cf. A000682, A301620.

For n>= 4: a(n) = A301620(n) - 2*A301620(n-1) = A000682(n) - 4*A000682(n-1) + 4*A000682(n-2).

A378944 Triangle read by rows: T(n,k) = number of stamp foldings with stamp #1 first, n stamps and stamp #2 covered by exactly one fold. k = the stamp number before the fold covering stamp #2 divided by 2. See examples.

Original entry on oeis.org

2, 4, 8, 6, 20, 12, 48, 24, 28, 132, 60, 56, 348, 144, 112, 162, 1008, 396, 280, 324, 2812, 1044, 672, 648, 1076, 8420, 3024, 1848, 1620, 2152

Offset: 5

Roger Ford, Dec 11 2024

The conjectured formula for the numbers in T(n,k) involves two unsolved sequences, semi-meanders and meandric numbers.

			                          _____    __         ______________
Vertical lines = stamp#  |     |  |  |       |   __    __   |   __
Horizontal lines = folds 1  5  2  3  4       |  |  |  |  |  |  |  |
                            |  |__|  |       1  6  5  4  3  2  8  7
                            |________|          |  |__|  |__|     |
     fold 4-5 covers stamp #2  k = 4/2          |_________________|
                        Example: T(5,2)      fold 6-7 covers stamp #2 k = 6/2
                                                               Example: T(8,3)
Irregular triangle begins:
   n\k  (2)  (3)  (4)  (5)  (6)
    5:   2
    6:   4
    7:   8    6
    8:   20   12
    9:   48   24   28
   10:   132  60   56
   11:   348  144  112  162
   12:   1008 396  280  324
   13:   2812 1044 672  648  1076
   14:   8420 3024 1848 1620 2152

Cf. A000682, A005316, A077054, A301620.

T(n,k) = 2 * A000682(n+1-2*k) * A077054(k-1).

cp's OEIS Frontend

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

A259702 Row sums of A259701 except first column.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A339179 Irregular triangle read by rows: for n >= 2, 2 <= k <= floor(n/2) + 1, T(n,k) = the number of semi-meanders with n top arches, a first arch of length one and k arch groupings.

Views

Author

Keywords

Examples

Crossrefs

Formula

A334615 a(n) is the number of semi-meanders with n top arches that has no arch of length 1 at the ends of the top arch configuration and no arch of length 1 adjacent to the center of the top arch configuration.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A378944 Triangle read by rows: T(n,k) = number of stamp foldings with stamp #1 first, n stamps and stamp #2 covered by exactly one fold. k = the stamp number before the fold covering stamp #2 divided by 2. See examples.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula