A259689 -id:A259689 - cp's OEIS frontend

A260785 Leading diagonal of triangle in A259689: a(n)= number of permutations without overlaps that generate exactly 2 permutations without overlaps in a(n+1).

1, 2, 2, 6, 10, 32, 68, 220, 528, 1724, 4460, 14664, 39908, 131944, 372448, 1237016, 3589384, 11967140, 35479312, 118675768, 357957984, 1200724776, 3673173656, 12351611656, 38232022416

Offset: 2

N. J. A. Sloane, Aug 04 2015

From Roger Ford, Oct 12 2015: (Start)
a(n)= Number of semi-meander solutions for n with 2 returns to the x axis (or number of 2 distinct arch groups).
Example:  n=5  -= return to x axis
      /\             /\                        /\
     //\\           /  \             /\       //\\
    ///\\\         /  /\\      /\   //\\     ///\\\
/\-////\\\\-   /\-//\//\\\-   //\\-///\\\-  ////\\\\-/\-
     /\
    /  \           /\
   //\  \         //\\   /\
  ///\\/\\-/\-   ///\\\-//\\-      a(5)=6.
a(n)= Number of hills (arches with a peak at 1 and no covering arches) for semi-meander solutions with n-1 arches.
Example:  n=5   semi-meander solutions with 4 arches (/\)= hill
                              /\              /\
         /\    /\            //\\            //\\
(/\)(/\)//\\  //\\(/\)(/\)  ///\\\(/\)  (/\)///\\\  a(5)=6.
(End)
From Roger Ford, Jan 27 2018: (Start)
a(n)= Number of solutions for folding a strip of n stamps with stamp 1 on top and each solution ordering having the absolute value of the difference of the stamp number before and after stamp n equal to 1. (If stamp n is the last stamp in the solution ordering then add a(1) to the end of the ordering.)
Example:  n=5
12354  |3-4| = 1,  14325(1)  |2-1| = 1,  12453  |4-3| = 1,
14532  |4-3| = 1,  15234  |1-2| = 1,  13542  |3-4| = 1,  a(5)=6.
(End)

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

Column k=2 of A259689.

Corrected and extended by Roger Ford, Oct 12 2015

a(14)-(26) from Andrew Howroyd, Dec 05 2018

A000682 Semi-meanders: number of ways a semi-infinite directed curve can cross a straight line n times.

Original entry on oeis.org

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

A301620 a(n) is the total number of top arches with exactly one covering arch for semi-meanders with n top arches.

Original entry on oeis.org

0, 0, 2, 4, 18, 42, 156, 398, 1398, 3778, 12982, 36522, 124290, 360182, 1220440, 3618090, 12237698, 36938158, 124880222, 382471606, 1293363816, 4009185912, 13565790984, 42478788432, 143851766298, 454339269482, 1539997455570, 4900091676662, 16624834778474, 53240459608298

Offset: 1

Roger Ford, Mar 24 2018

nonn

For n>2, a(n-2) is the number of ways to fold a strip of n stamps with leaf 1 on top and the n leaf not adjacent to the n-1 leaf. Example n = 6, a(6-2) = 4: 125436, 126345, 154362, 163452. - Roger Ford, Mar 29 2019

For n>2, a(n-2) is the number of ways to fold a strip of n stamps with leaf 1 on top and leaf 2 not in the second position and not in the n-th position. Example, for n = 6, a(6-2) = 4: 143265, 156234, 165234, 143256. - Roger Ford, Mar 12 2021

			For n = 4, a(4) = 4.  + + are underneath the starting and ending of each arch with exactly one covering arch.
          /\                  /\
         //\\         /\     //\\       /\
      /\///\\\,  /\/\//\\,  ///\\\/\,  //\\/\/\ .
         +  +         ++     +  +       ++

Jean-François Alcover, Table of n, a(n) for n = 1..43

Cf. A000682, A259689.

A000682 = Import["https://oeis.org/A000682/b000682.txt", "Table"][[All, 2]];
a[n_] := A000682[[n + 2]] - 2*A000682[[n + 1]];
Array[a, 30] (* Jean-François Alcover, Sep 02 2019 *)

a(n) = A000682(n+2) - 2*A000682(n+1).
a(n) = Sum_{k=3..floor((n+3)/2)} (A259689(n+1,k)*(k-2)). - Roger Ford, Dec 10 2018
a(n) = 2*A259702(n+2). - Roger Ford, Dec 24 2018

A380369 Triangle read by rows: T(n,k) is the number of open meanders with 2n crossings and k exterior top arches, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 7, 6, 1, 0, 36, 32, 12, 1, 0, 221, 202, 94, 20, 1, 0, 1530, 1417, 728, 220, 30, 1, 0, 11510, 10752, 5854, 2090, 445, 42, 1, 0, 92114, 86554, 48942, 19300, 5160, 812, 56, 1, 0, 773259, 729716, 423778, 178478, 54758, 11396, 1372, 72, 1, 0, 6743122, 6384353, 3781926, 1669062, 561514, 138866, 23072, 2184, 90, 1

Offset: 0

Andrew Howroyd, Feb 01 2025

			Triangle begins:
  1;
  0,     1;
  0,     2,     1;
  0,     7,     6,     1;
  0,    36,    32,    12,     1;
  0,   221,   202,    94,    20,    1;
  0,  1530,  1417,   728,   220,   30,   1;
  0, 11510, 10752,  5854,  2090,  445,  42,  1;
  0, 92114, 86554, 48942, 19300, 5160, 812, 56, 1;
  ...
The T(2,1) = 2 open meanders are:
         __           __
        /  \         /  \
   ... / /\ \..  .. / /\ \ ...
      / /  \/       \/  \ \
The T(2,2) = 1 open meander is:
   ... /\../\ ...
      /  \/  \

Andrew Howroyd, Table of n, a(n) for n = 0..230

Row sums are A077054.
Main diagonal is A000012.
Second diagonal is A002378.
Cf. A005316, A006660 (bisection gives column 1), A077056 (total number of exterior top arches), A259689 (for semi-meanders), A259974.

A077056(n) = Sum_{k=1..n} k*T(n,k).

T(n,1) = A006660(2*n + 1).

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

A365679 a(n) is the number of exterior top arches (no covering arch) for semi-meanders in generation n+1 that are generated by semi-meanders with n top arches and floor((n+2)/2) exterior top arches using the exterior arch splitting algorithm.

Original entry on oeis.org

4, 10, 14, 32, 40, 88, 104, 224, 256, 544, 608, 1280, 1408, 2944, 3200, 6656, 7168, 14848, 15872, 32768, 34816, 71680, 75776, 155648, 163840, 335872, 352256, 720896, 753664, 1540096, 1605632, 3276800, 3407872, 6946816, 7208960, 14680064

Offset: 2

Roger Ford, Sep 15 2023

nonn

b(n) = the number of exterior top arches for all semi-meanders with n top arches and floor((n+2)/2) exterior top arches = (floor(n/2)+1) * 2^(floor((n-1)/2)). For n>=2, lim_{n->oo} a(n)/b(n) = 3.

			For n=4, the number of semi-meanders with 4 top arches and 3 exterior top arches is equal to A259689(4,3) = 2:
       /\    /\
/\ /\ //\\, //\\ /\ /\ = 6 exterior arches. These 6 arches will generate 6 solutions in the n+1 generation using the exterior arch splitting algorithm.
     _____           __                                    __           _____
    /   /\\    /\   //\\    _____                _____    //\\   /\    //\   \
/\ //\ //\\\, //\\ ///\\\, //\ /\\ /\ /\, /\ /\ //\ /\\, ///\\\ //\\, ///\\ /\\ /\
These 6 solutions have 14 exterior arches. Therefore a(4) = 14.

Index entries for linear recurrences with constant coefficients, signature (0, 4, 0, -4).

Cf. A259689.

a[n_]:=(2*n-Floor[(n-1)/2]) * 2^Floor[(n-1)/2]; Array[a,36,2] (* Stefano Spezia, Sep 16 2023 *)

a(n) = (2*n-floor((n-1)/2)) * 2^floor((n-1)/2).

a(30) corrected by Georg Fischer, Jun 03 2024

A366415 a(n) is the number of exterior top arches (no covering arch) for semi-meanders in generation n+1 that are generated by semi-meanders with n top arches and floor(n/2) exterior top arches using the exterior arch splitting algorithm.

Original entry on oeis.org

10, 34, 78, 222, 362, 938, 1326, 3246, 4242, 10002, 12438, 28566, 34330, 77338, 90654, 201246, 231458, 507938, 575526, 1251366, 1400874, 3022890, 3350574, 7184430, 7897138, 16842802, 18382902, 39026742, 42336314, 89522234, 96600126, 203554878

Offset: 4

Roger Ford, Oct 10 2023

b(n) = ((n-4)*2^floor((n-1)/2)+2)*floor(n/2) is the number of exterior top arches for all semi-meander solutions with n top arches and floor(n/2) exterior top arches. Conjecture: for n>=5, lim_{n->oo} a(n)/b(n) = 3.

			For n=5, the number of semi-meanders with 5 top arches and 2 exterior top arches is equal to A259689(5,2) = 6:
     __                                __
    //\\          __        ____      //\\        __          ____
   ///\\\    __  //\\      /  /\\    ///\\\      //\\  __    //\  \
/\////\\\\, //\\///\\\, /\//\//\\\, ////\\\\/\, ///\\\//\\, ///\\/\\/\
There are 12 exterior arches for the 6 solutions.
Solutions for generation n+1 using the exterior arch splitting algorithm:
      __
     //\\                        __                      ____
    ///\\\         __           //\\     __             /____\
   ////\\\\   __  //\\         ///\\\   //\\  __       //  __\\   __    __
/\/////\\\\\,//\\///\\\/\,/\/\////\\\\,///\\\//\\/\,/\///\//\\\\,//\\/\//\\/\
    __
   //\\                      __                        ____
  ///\\\         __         //\\               __     /____\
 ////\\\\       //\\  __   ///\\\         __  //\\   //__  \\       __    __
/////\\\\\/\,/\///\\\//\\,////\\\\/\/\,/\//\\///\\\,////\\/\\\/\,/\//\\/\//\\
These 12 solutions have 34 exterior arches. Therefore a(5) = 34.

Paolo Xausa, Table of n, a(n) for n = 4..1000
Michael LaCroix, Approaches to the Enumerative Theory of Meanders, 2003, pg. 31-31, Demonstrates arch splitting with semi-meander models.
Index entries for linear recurrences with constant coefficients, signature (1,7,-7,-18,18,20,-20,-8,8).

Cf. A259689, A365679.

LinearRecurrence[{1, 7, -7, -18, 18, 20, -20, -8, 8}, {10, 34, 78, 222, 362, 938, 1326, 3246, 4242}, 50] (* Paolo Xausa, May 28 2024 *)

For n>2:
a(2*n) = (3*n-1)*((2*n-4)*2^(n-1) + 2) - (3*n-3)*((2*n-5)*2^(n-1) + 2) + a(2*n-1);
a(2*n+1) = 3*n*((2*n-3)*2^n + 2) - 3*n*((2*n-4)*2^(n-1) + 2) + a(2*n).
G.f.: 2*x^4*(5 + 12*x - 13*x^2 - 12*x^3 + 6*x^4)/((1 - x)^2*(1 + x)*(1 - 2*x^2)^3). - Stefano Spezia, Nov 07 2023

cp's OEIS Frontend

A260785 Leading diagonal of triangle in A259689: a(n)= number of permutations without overlaps that generate exactly 2 permutations without overlaps in a(n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

A301620 a(n) is the total number of top arches with exactly one covering arch for semi-meanders with n top arches.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A380369 Triangle read by rows: T(n,k) is the number of open meanders with 2n crossings and k exterior top arches, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

A365679 a(n) is the number of exterior top arches (no covering arch) for semi-meanders in generation n+1 that are generated by semi-meanders with n top arches and floor((n+2)/2) exterior top arches using the exterior arch splitting algorithm.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A366415 a(n) is the number of exterior top arches (no covering arch) for semi-meanders in generation n+1 that are generated by semi-meanders with n top arches and floor(n/2) exterior top arches using the exterior arch splitting algorithm.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A322507 a(n) is the number of arches for semi-meanders with n top arches that have exactly two covering arches.

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions