A000682 -id:A000682 - cp's OEIS frontend

A259702 Row sums of A259701 except first column.

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

A373325 Number of semi-infinite curves of the plane with n simple, transverse self-intersections and no other self-intersections, up to an orientation-preserving homeomorphism.

Original entry on oeis.org

1, 2, 10, 66, 498, 4072, 35144, 315352, 2914074, 27553880, 265387528, 2595131328

Offset: 0

Luc Rousseau, Jun 01 2024

			Curves without self-intersection are equivalent; one might for instance take the half-line y <= 0 as their representative; so a(0) = 1.
To get a curve with n+1 self-intersections, one can start from a curve with n self-intersections; identify the cycle of oriented edges that directly surrounds the finite extremity of the curve; choose an edge from that cycle and extend the curve so that it crosses that edge.
When "outside" it might help visualization to imagine that a noncrossable oriented edge "at infinity" closes the cycle.
Thus, for a transition between 0 and 1 self-intersection, the choice is between making a loop that turns left and making a loop that turns right; so a(1) = 2.
See provided illustration for n=0..3 in section 'Links'.

Luc Rousseau, Illustration for n=0..3
Luc Rousseau, A Prolog program.

Cf. A000682, A268563.

A259703 Triangle read by rows: T(n,k) = number of permutations without overlaps in which the first increasing run has length k.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 5, 2, 2, 1, 12, 5, 4, 2, 1, 33, 13, 12, 4, 3, 1, 87, 35, 30, 12, 6, 3, 1, 252, 98, 90, 32, 21, 6, 4, 1, 703, 278, 243, 94, 54, 21, 8, 4, 1, 2105, 812, 745, 270, 175, 57, 32, 8, 5, 1, 6099, 2385, 2108, 808, 485, 181, 84, 32, 10, 5, 1

Offset: 2

N. J. A. Sloane, Jul 05 2015

The 12th row of the triangle (as given in the reference) is definitely wrong, since the first column of this triangle is known (it is A000560). The row sums are also known - see A000682.
From Roger Ford, Jul 06 2016: (Start)
To determine the first increasing run of the permutation 176852943 start on the left and move to the right counting the consecutive integers.
(1)7685(2)94(3).  This permutation a has a first run of (3-1)=2. The permutation 123465 has a first run of (5-1)=4. (1)(2)(3)(4)6(5). (End)

			Triangle begins:
     1;
     1,    1;
     2,    1,    1;
     5,    2,    2,   1;
    12,    5,    4,   2,   1;
    33,   13,   12,   4,   3,   1;
    87,   35,   30,  12,   6,   3,  1;
   252,   98,   90,  32,  21,   6,  4,  1;
   703,  278,  243,  94,  54,  21,  8,  4,  1;
  2105,  812,  745, 270, 175,  57, 32,  8,  5, 1;
  6099, 2385, 2108, 808, 485, 181, 84, 32, 10, 5, 1;
  ...

A. Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949

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

Row sums are A000682. First column is A000560.

Cf. A259701.

Overlapfree(v)={for(i=1, #v, for(j=i+1, v[i]-1, if(v[j]>v[i], return(0)))); 1}
Chords(u)={my(n=2*#u, v=vector(n), s=u[#u]); if(s%2==0, s=n+1-s); for(i=1, #u, my(t=n+1-s); s=u[i]; if(s%2==0, s=n+1-s); v[s]=t; v[t]=s); v}
FirstRunLen(v)={my(e=1); for(i=1, #v, if(v[i]==e, e++)); e-2}
row(n)={my(r=vector(n-1)); if(n>=2, forperm(n, v, if(v[1]<>1, break); if(Overlapfree(Chords(v)), r[FirstRunLen(v)]++))); r}
for(n=2, 8, print(row(n))) \\ Andrew Howroyd, Dec 07 2018

Corrected and extended by Roger Ford, Jul 06 2016

A287548 Triangle read by rows: T(n,k), where each row begins with the Catalan number for n nonintersecting arches and transitions through k generations of eliminating and reducing arch configurations to an end row entry equal to number of semi-meander solutions for n arches.

Original entry on oeis.org

1, 2, 1, 5, 3, 2, 14, 9, 7, 4, 42, 28, 23, 16, 10, 132, 90, 76, 57, 42, 24, 429, 297, 255, 199, 156, 108, 66, 1430, 1001, 869, 695, 563, 420, 304, 174, 4862, 3432, 3003, 2442, 2019, 1568, 1210, 836, 504

Offset: 1

Roger Ford, May 26 2017

			Triangle begins:
n\k    1    2    3    4    5    6    7    8
1:     1
2:     2    1
3:     5    3    2
4:     14   9    7    4
5:     42   28   23   16   10
6:     132  90   76   57   42   24
7:     429  297  255  199  156  108  66
8:     1430 1001 869  695  563  420  304  174
...
Capital letters (U,D) represent beginning and end of first and last arch. Only 1 UD ends arch sequence in next generation.
Reduction of arches:            Elimination of arches:
(middle D U = new arch U D in the next arch generation)
            /\
     /\    //\\                      /\/\/\/\  = UDududUD
    //\\/\///\\\  = UudDudUuuddD        /\
        /\  /\                         /  \
     /\//\\//\\   =  UDuuddUudD       //\/\\   =  UududD
                                        end
For n=3 C(n)=5  nonintersecting arch configurations:
   UuuddD   UududD   UudDUD   UDUudD   UDudUD   T(3,1)=5
    end      end      UDUD     UDUD     UudD    T(3,2)=3
                       UD       UD       end    T(3,3)=2

Cf. A000108, A000245, A067324, A000682.

T(n,1) = Catalan Numbers C(n)= A000108(n).
Conjectured:
T(n,2) = C(n) - C(n-1) = A000245(n-1).
T(n,3) = C(n) - C(n-1) - C(n-2) = A067324(n-3).
T(n,4) = C(n) - C(n-1) - 2*C(n-2) - C(n-3).
T(n,n) = semi-meander solutions = A000682(n-1).

A330269 The number of semi-meanders with n top arches and concentric arches within the starting arch or a starting arch with length one.

Original entry on oeis.org

1, 1, 2, 4, 8, 18, 42, 108, 282, 786, 2192, 6402, 18600, 55978, 167256, 514102, 1567976, 4896164, 15170630, 47957260, 150468678, 480371736, 1522649458, 4900568718, 15665593150, 50761432998, 163431901126, 532624603680, 1725349278270, 5650796083020, 18401781369182

Offset: 1

Roger Ford, Dec 07 2019

nonn

			For n = 5, a(5) = 8:
        /\                                  /\
       //\\                      /\        /  \          /\
      ///\\\      /\  /\        /  \      /  /\\    /\  //\\
   /\////\\\\, /\//\\//\\, /\/\//\/\\, /\//\//\\\, //\\///\\\,
                              /\
                 /\          //\\          starting arch
    /\  /\      //\\  /\    ///\\\        (1) (2) (3) (4)
   //\\//\\/\, ///\\\//\\, ////\\\\/\,     4 + 2 + 1 + 1 = 8.

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

Cf. A000682.

A000136 = Import["https://oeis.org/A000136/b000136.txt", "Table"][[All, 2]];
a[n_] := If[n == 1, 1, Sum[A000136[[k]]/k, {k, 1, n - 1}]];
a /@ Range[46] (* Jean-François Alcover, Feb 13 2020 *)

a(1) = 1, for n >= 2, a(n) = Sum_{k=1..n-1} A000682(k).

More terms from Jinyuan Wang, Dec 08 2019

A331499 T(n,k) is the number of nonintersecting arch configurations with n arches on a horizontal axis that have a starting parent arch configuration of k arches.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 4, 3, 2, 5, 10, 6, 7, 5, 14, 24, 18, 15, 19, 14, 42, 66, 42, 48, 43, 56, 42, 132, 174, 130, 116, 143, 132, 174, 132, 429, 504, 332, 374, 358, 451, 423, 561, 429, 1430, 1406, 1048, 974, 1182, 1163, 1475, 1397, 1859, 1430, 4862

Offset: 1

Roger Ford, Feb 16 2020

A parent arch configuration has exactly one exterior arch and can be derived from an initial arch configuration with more than one exterior arch by using the algorithm for decreasing arches explained below.
When concentric arches are placed below the different arch configurations, the number of components (loops formed) in each configuration will remain the same as the number components in that arch configuration's parent arch.
Algorithm: To determine the parent arch configuration, start with all the nonintersecting arch configurations with n arches and more than one exterior arch. For each starting individual arch configuration, reduce the number of arches until there is exactly one exterior arch. Join the start of the first arch with the end of the last arch. This will eliminate one arch and shrink the number of arches from n to n-1. Continue this process until there is one exterior arch.
           /\    n=5
          /  \                              /\   n=5
         /  /\\                        /\  /  \
  --> /\//\//\\\ <--              --> //\\//\/\\ <--
            /\
  -->  /\/\//\\ <--               -->  /\/\/\/\ <--
         /\                               /\
  -->   //\\/\ <--                       /  \
  -->    /\/\ <--                       //\/\\ parent arch k = 3
          /\  parent arch k = 1.

			Triangle T(n,k) begins:
  n\k    1    2    3    4    5    6    7    8    9   10    11
   1:    1
   2:    1    1
   3:    2    1    2
   4:    4    3    2    5
   5:   10    6    7    5   14
   6:   24   18   15   19   14   42
   7:   66   42   48   43   56   42  132
   8:  174  130  116  143  132  174  132  429
   9:  504  332  374  358  451  423  561  429 1430
  10: 1406 1048  974 1182 1163 1475 1397 1859 1430 4862
  11: 4210 2836 3166 3152 3906 3897 4950 4719 6292 4862 16796

Cf. A000108, A000682.

The sum of row n = A000108(n).
T(n,1) = A000682(n).
T(n,n) = A000108(n-1).
T(n,n-1) = A000108(n-2).
T(n,n-2) = A000108(n-2) + A000108(n-3) (conjectured).

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

A276051 a(n) is the number of top arches with length =1 for all semi meander solutions with n top arches.

Original entry on oeis.org

1, 2, 4, 10, 28, 80, 244, 732, 2320, 7172, 23212, 73228, 240184, 768932, 2545568, 8240604, 27468352, 89699652, 300579836, 988463844

Offset: 1

Roger Ford, Aug 17 2016

			a(4)=10       /\       /\      /\          /\
         /\/\//\\     //\\    //\\/\/\    //\\
                   /\///\\\              ///\\\/\.

Cf. A000682.

Conjectured formula for n>=3.
M(n)= number of semi meanders solutions for n top arches. A000682.
r(x)= number of top arches with no covering arch for solution x of M(n).
Example:      /\     r(x)=3
         /\/\//\\
h(x)= number of top arches with length =1 for solution x of M(n).
Example:      /\
         /\/\//\\    h(x)=3
i(x)= number of uncovered top arches with length =1 and in an internal position for solution x of M(n).  Example:()         /\   i(x)=1
                                                /\(/\)//\\
a(n+1)= sum of x=1 to M(n)for [r(x)*h(x)-i(x)] + 2*M(n)-2*M(n-1)
a(5)=(3*3-1)+(3*3-1)+(2*2-0)+(2*2-0)+2*4-2*2= 28.

a(11)-a(20) from Andrew Howroyd, Dec 07 2018

A333971 a(n) is the number of semi-meanders with n top arches that have at least one arch with length 1 adjacent to the center of the top arch configuration or at either end of the arch configuration.

Original entry on oeis.org

1, 2, 4, 8, 24, 56, 168, 432, 1320, 3608, 11216, 31952, 100720, 295600, 942272, 2828112, 9097256, 27785112, 90048656, 278899152, 909566560, 2849498656, 9342566152, 29548420688, 97323261664

Offset: 2

Roger Ford, Sep 03 2020

The number of semi-meanders with n top arches is A000682(n). The number of semi-meanders with n top arches that have a starting or ending arch of length 1 is 2*A000682(n-1). The number of semi-meanders with n top arches that have an arch adjacent to the center with length 1 is 2*A000682(n-1).

			For n = 6: (10) is an arch of length 1 that is at either end of the top arch configuration or adjacent to the center of the top arch configuration, a(6) = 24.
1111(10)0000(10), 111100(10)00(10), 1111000010(10), 1110(10)0100(10), 1110(10)001100, 111001(10)00(10), 1110001100(10), 111000(10)1100, 1101(10)0010(10), 110110(10)10(10), 110011(10)00(10), 110011(10)00(10), 1100(10)111000, 1100(10)1100(10), (10)1111(10)0000, (10)11(10)110000, (10)11(10)011000, (10)11(10)001100, (10)1101(10)1000, (10)1100111000, (10)1100(10)1100, (10)1011110000, (10)1011(10)0100, (10)10(10)110100.

Cf. A000682.

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

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

cp's OEIS Frontend

A259702 Row sums of A259701 except first column.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A373325 Number of semi-infinite curves of the plane with n simple, transverse self-intersections and no other self-intersections, up to an orientation-preserving homeomorphism.

Views

Author

Keywords

Examples

Links

Crossrefs

A259703 Triangle read by rows: T(n,k) = number of permutations without overlaps in which the first increasing run has length k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A287548 Triangle read by rows: T(n,k), where each row begins with the Catalan number for n nonintersecting arches and transitions through k generations of eliminating and reducing arch configurations to an end row entry equal to number of semi-meander solutions for n arches.

Views

Author

Keywords

Examples

Crossrefs

Formula

A330269 The number of semi-meanders with n top arches and concentric arches within the starting arch or a starting arch with length one.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A331499 T(n,k) is the number of nonintersecting arch configurations with n arches on a horizontal axis that have a starting parent arch configuration of k arches.

Views

Author

Keywords

Comments

Examples

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

A276051 a(n) is the number of top arches with length =1 for all semi meander solutions with n top arches.

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

A333971 a(n) is the number of semi-meanders with n top arches that have at least one arch with length 1 adjacent to the center of the top arch configuration or at either end of the arch configuration.

Views

Author

Keywords

Comments

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.