A080937 -id:A080937 - cp's OEIS frontend

A202062 Number of ascent sequences avoiding the pattern 201.

1, 1, 2, 5, 15, 52, 201, 843, 3764, 17659, 86245, 435492, 2261769, 12033165, 65369590, 361661809, 2033429427, 11597912588, 67004252081, 391599609911, 2312726369640, 13789161819383, 82932744795049, 502777950712812, 3070529443569777, 18879637374473465, 116815588935673706, 727011479685559453

Offset: 0

N. J. A. Sloane, Dec 10 2011

nonn

It appears that no formula or g.f. is known.

Andrew Conway and Miles Conway, Table of n, a(n) for n = 0..133
Giulio Cerbai, Modified ascent sequences and Bell numbers, arXiv:2305.10820 [math.CO], 2023. See p. 27.
Giulio Cerbai, Anders Claesson and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
Andrew R. Conway, Miles Conway, Andrew Elvey Price and Anthony J. Guttmann, Pattern-avoiding ascent sequences of length 3, arXiv:2111.01279 [math.CO], Nov 01 2021.
P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
Anthony Guttmann and Vaclav Kotesovec, L-convex polyominoes and 201-avoiding ascent sequences, arXiv:2109.09928 [math.CO], 2021.

Total number of ascent sequences is given by A022493.

Number of ascent sequences avoiding 001 (and others) is A000079; 102 is A007051; 101 is A000108; 000 is A202058; 100 is A202059; 110 is A202060; 120 is A202061; 201 is A202062; 210 is A108304; 0123 is A080937; 0021 is A007317.

Guttmann and Kotesovec give asymptotics: a(n) ~ c * d^n / n^(9/2), where d = (14/3*cos(arccos(13/14)/3) + 8/3) = 7.2958969432397723745722241... is the root of the equation 1 + 5*d - 8*d^2 + d^3 = 0 and c = 35*sqrt((4107 - 84*sqrt(9289) * cos(Pi/3 + arccos(255709*sqrt(9289)/24653006)/3))/Pi)/16 = 13.4299960869439... - Vaclav Kotesovec, Sep 22 2021

a(15) from Kanstancin Novikau, Mar 21 2017

a(16)-a(27) from Ildar Gainullin, Feb 11 2020

A202059 Number of ascent sequences avoiding the pattern 100.

Original entry on oeis.org

1, 1, 2, 5, 14, 44, 153, 583, 2410, 10721, 50965, 257393, 1374187, 7722862, 45520064, 280502924, 1802060232, 12040040899, 83475921469, 599400745354, 4449689901306, 34096169966924, 269286884243138, 2189193150557825, 18297258191472880, 157049750065028868

Offset: 0

N. J. A. Sloane, Dec 10 2011

nonn

It appears that no formula or g.f. is known.

Andrew Conway and Miles Conway, Table of n, a(n) for n = 0..628
Andrew R. Conway, Miles Conway, Andrew Elvey Price and Anthony J. Guttmann, Pattern-avoiding ascent sequences of length 3, arXiv:2111.01279 [math.CO], Nov 01 2021.
P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641, 2011

Total number of ascent sequences is given by A022493. Number of ascent sequences avoiding 001 (and others) is A000079; 102 is A007051; 101 is A000108; 000 is A202058; 100 is A202059; 110 is A202060; 120 is A202061; 201 is A202062; 210 is A108304; 0123 is A080937; 0021 is A007317.

Corrected a(7), was 383, but should be 583 according to Duncan-Steimgrimsson paper and independent computation. - Andrew Baxter, Jan 06 2014
a(0) and a(15)-a(21) from Alois P. Heinz, Jan 06 2014
a(22) from Alois P. Heinz, Oct 06 2014
a(23) from Alois P. Heinz, Apr 20 2016
More terms from Anthony Guttmann, Nov 04 2021

A202060 Number of ascent sequences avoiding the pattern 110.

Original entry on oeis.org

1, 1, 2, 5, 14, 43, 143, 510, 1936, 7774, 32848, 145398, 671641, 3227218, 16084747, 82955090, 441773793, 2424845273, 13695855478, 79485625385, 473393639992, 2889930405750, 18064609329598, 115513453404597, 754956282308784, 5039064184597772, 34323984497482559

Offset: 0

N. J. A. Sloane, Dec 10 2011

nonn

It appears that no formula or g.f. is known.

Andrew Conway and Miles Conway, Table of n, a(n) for n = 0..43
Andrew R. Conway, Miles Conway, Andrew Elvey Price and Anthony J. Guttmann, Pattern-avoiding ascent sequences of length 3, arXiv:2111.01279 [math.CO], Nov 01 2021.
P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641, 2011

Total number of ascent sequences is given by A022493. Number of ascent sequences avoiding 001 (and others) is A000079; 102 is A007051; 101 is A000108; 000 is A202058; 100 is A202059; 110 is A202060; 120 is A202061; 201 is A202062; 210 is A108304; 0123 is A080937; 0021 is A007317.

a(0) and a(15)-a(17) from Alois P. Heinz, Jan 07 2014

More terms from Anthony Guttmann, Nov 04 2021

A202061 Number of ascent sequences avoiding the pattern 120.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 133, 442, 1535, 5546, 20754, 80113, 317875, 1292648, 5374073, 22794182, 98462847, 432498659, 1929221610, 8728815103, 40017844229, 185727603829, 871897549029, 4137132922197, 19828476952117, 95934298966615, 468291607852143, 2305162065138433

Offset: 0

N. J. A. Sloane, Dec 10 2011

nonn

It appears that no formula or g.f. is known.

Liang Chengwei, Shi Lecun and Cai Zhongyu, Table of n, a(n) for n = 0..500 (terms 0..74 from Andrew Conway and Miles Conway)
Andrew R. Conway, Miles Conway, Andrew Elvey Price and Anthony J. Guttmann, Pattern-avoiding ascent sequences of length 3, arXiv:2111.01279 [math.CO], Nov 01 2021.
Paul Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.

Total number of ascent sequences is given by A022493. Number of ascent sequences avoiding 001 (and others) is A000079; 102 is A007051; 101 is A000108; 000 is A202058; 100 is A202059; 110 is A202060; 120 is A202061; 201 is A202062; 210 is A108304; 0123 is A080937; 0021 is A007317.

More terms from Anthony Guttmann, Nov 04 2021

A216054 Square array T, read by antidiagonals: T(n,k) = 0 if n-k >= 1 or if k-n >= 6, T(0,0) = T(0,1) = T(0,2) = T(0,3) = T(0,4) = T(0,5) = 1, T(n,k) = T(n-1,k) + T(n,k-1).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 1, 4, 5, 0, 0, 0, 0, 5, 9, 5, 0, 0, 0, 0, 5, 14, 14, 0, 0, 0, 0, 0, 0, 19, 28, 14, 0, 0, 0, 0, 0, 0, 19, 47, 42, 0, 0, 0, 0, 0, 0, 0, 0, 66, 89, 42, 0, 0, 0, 0, 0, 0, 0, 0, 66, 155, 131, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 221, 286, 131, 0, 0

Offset: 0

Philippe Deléham, Mar 16 2013

A hexagon arithmetic of E. Lucas.

			Square array begins:
1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... row n=0
0, 1, 2, 3, 4, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... row n=1
0, 0, 2, 5, 9, 14, 19, 19, 0, 0, 0, 0, 0, 0, 0, ... row n=2
0, 0, 0, 5, 14, 28, 47, 66, 66, 0, 0, 0, 0, 0, 0, ... row n=3
0, 0, 0, 0, 14, 42, 89, 155, 221, 221, 0, 0, 0, 0, ... row n=4
0, 0, 0, 0, 0, 0, 42, 131, 286, 507, 728, 728, 0, 0, ... row n=5
0, 0, 0, 0, 0, 0, 131, 417, 924, 1652, 2380, 2380, 0, ... row n=6
...

E. Lucas, Théorie des nombres, A.Blanchard, Paris, 1958, Tome 1, p.89

Cf. A006053, A052547, A096976, A187066,

Cf. Similar sequences A216230, A216228, A216226, A216238

Clear[t]; t[0, k_ /; k <= 5] = 1; t[n_, k_] /; k < n || k > n+5 = 0; t[n_, k_] := t[n, k] = t[n-1, k] + t[n, k-1]; Table[t[n-k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Mar 18 2013 *)

T(n,n) = A080937(n).
T(n,n+1) = A080937(n+1).
T(n,n+2) = A094790(n+1).
T(n,n+3) = A094789(n+1).
T(n,n4) = T(n,n+5) = A005021(n).
Sum_{k, 0<=k<=n} T(n-k,k) = A028495(n).

A216235 Square array T, read by antidiagonals: T(n,k) = 0 if n-k >= 2 or if k-n >= 5, T(1,0) = T(0,0) = T(0,1) = T(0,2) = T(0,3) = T(0,4) = 1, T(n,k) = T(n-1,k) + T(n,k-1).

Original entry on oeis.org

1, 1, 1, 1, 2, 0, 1, 3, 2, 0, 1, 4, 5, 0, 0, 0, 5, 9, 5, 0, 0, 0, 5, 14, 14, 0, 0, 0, 0, 0, 19, 28, 14, 0, 0, 0, 0, 0, 19, 47, 42, 0, 0, 0, 0, 0, 0, 0, 66, 89, 42, 0, 0, 0, 0, 0, 0, 0, 66, 155, 131, 0, 0, 0, 0, 0, 0, 0, 0, 0, 221, 286, 131, 0, 0, 0, 0, 0, 0, 0, 0, 0, 221, 507, 417, 0, 0, 0, 0, 0, 0

Offset: 0

Philippe Deléham, Mar 14 2013

Arithmetic hexagon of E. Lucas.

			Square array begins:
  1, 1, 1,  1,  1,   0,   0,   0,   0,   0, ... row n=0
  1, 2, 3,  4,  5,   5,   0,   0,   0,   0, ... row n=1
  0, 2, 5,  9, 14,  19,  19,   0,   0,   0, ... row n=2
  0, 0, 5, 14, 28,  47,  66,  66,   0,   0, ... row n=3
  0, 0, 0, 14, 42,  89, 155, 221, 221,   0, ... row n=4
  0, 0, 0,  0, 42, 131, 286, 507, 728, 728, ... row n=5
  ...

E. Lucas, Théorie des nombres, Gauthier-Villars, Paris 1891, Tome 1, p. 89.

Cf. A005021, A080937, A094789, A094790.

Similar sequences: A216201, A216210, A216216, A216218, A216219, A216220, A216226, A216228, A216229, A216230, A216232.

T(n,n) = T(n+1,n) = A080937(n+1).
T(n,n+1) = A094790(n+1).
T(n,n+2) = A094789(n+1).
T(n,n+3) = T(n,n+4) = A005021(n).
Sum_{k=0..n} T(n-k,k) = A028495(n+1). - Philippe Deléham, Mar 23 2013

A038213 Top line of 3-wave sequence A038196, also bisection of A006356.

Original entry on oeis.org

1, 3, 14, 70, 353, 1782, 8997, 45425, 229347, 1157954, 5846414, 29518061, 149034250, 752461609, 3799116465, 19181424995, 96845429254, 488964567014, 2468741680809, 12464472679038, 62932092237197, 317738931708801

Offset: 0

Floor van Lamoen

			G.f. = 1 + 3*x + 14*x^2 + 70*x^3 + 353*x^4 + 1782*x^5 + 8997*x^6 + 45425*x^7 + ...

Johann Cigler, Number of bounded Dyck paths with "negative length", MathOverflow question, Sep 26 2020.
S. Morier-Genoud, V. Ovsienko and S. Tabachnikov, 2-frieze patterns and the cluster structure of the space of polygons, Annales de l'institut Fourier, 62 no. 3 (2012), 937-987; arXiv:1008.3359 [math.AG], 2010-2011. - _N. J. A. Sloane_, Dec 26 2012
F. v. Lamoen, Wave sequences
Index entries for linear recurrences with constant coefficients, signature (6, -5, 1).

Cf. A080937.

k=3; M(k)=matrix(k,k,i,j,min(i,j)); v(k)=vector(k,i,1); a(n)=vecmin(v(k)*M(k)^n)

{a(n) = if( n<0, n = -n; polcoeff( (1 - 4*x + 3*x^2) / (1 - 5*x + 6*x^2 - x^3) + x * O(x^n), n), polcoeff( (1 - 3*x + x^2) / (1 - 6*x + 5*x^2 - x^3) + x * O(x^n), n))}; /* Michael Somos, May 04 2012 */

Let v(3)=(1, 1, 1), let M(3) be the 3 X 3 matrix m(i, j) =min(i, j); then a(n)= min ( v(3)*M(3)^n). - Benoit Cloitre, Oct 03 2002
G.f.: -((1 + (-3 + q)*q)/(-1 + (-3 + q)*(-2 + q)*q)). - Wouter Meeussen, Mar 19 2005
G.f.: (1 - 3*x + x^2) / (1 - 6*x + 5*x^2 - x^3).
a(-n) = A080937(n) for all n in Z. a(n + 2) * a(n) - a(n + 1)^2 = a(-3 - n) for all n in Z. - Michael Somos, May 04 2012

More terms from Benoit Cloitre, Oct 03 2002

A122881 Triangle read by rows: number of Catalan paths of 2n steps of all values less than or equal to m.

Original entry on oeis.org

1, 1, 2, 1, 2, 5, 1, 2, 5, 13, 1, 2, 5, 14, 34, 1, 2, 5, 14, 42, 89, 1, 2, 5, 14, 42, 131, 233, 1, 2, 5, 14, 42, 132, 417, 610, 1, 2, 5, 14, 42, 132, 429, 1341, 1597, 1, 2, 5, 14, 42, 132, 429, 1429, 4334, 4181

Offset: 1

Gary W. Adamson, Sep 16 2006

Convergents of k-th diagonals relate to (2k+3)-polygons; e.g., right border relates to the pentagon (N=5), next border relates to the heptagon (N=7). Convergents of the diagonals are 2 + 2*cos(2*Pi/N) and are roots to Morgan-Voyce polynomials. k2 diagonal = A080937, number of Catalan paths of 2n steps of all values less than or equal to 5. k3 diagonal = A080938, number of Catalan paths of 2n steps of all values less than or equal to 7.

			For the right border, odd-indexed Fibonacci numbers (1, 2, 5, 13, 34...), we begin with (M2) = [1, 1; 1, 0], then P2 = [1, -1; -1, 2] = 1/(M2)^2. Performing (P2)^n * [1,0] we extract the left vector (1, 2, 5, 13, ...), making it the right border of the triangle, k1 diagonal.
For the next diagonal going to the left, we begin with the Heptagonal matrix M3 = [1, 1, 1; 1, 1, 0; 1, 0, 0], take the inverse square (P3) and then perform the analogous operation getting 1, 2, 5, 14, 42, ...
First few rows of the triangle are:
  1;
  1, 2;
  1, 2, 5;
  1, 2, 5, 13;
  1, 2, 5, 14, 34;
  1, 2, 5, 14, 42, 89;
  1, 2, 5, 14, 42, 131, 233;
  1, 2, 5, 14, 42, 132, 417, 610;
  ...

Cf. A112880, A001519, A000108, A080937, A080938.

Begin with polygonal matrices of the form (exemplified by the Heptagonal matrix M3: [1, 1, 1; 1, 1, 0; 1, 0, 0]). Let matrix P3 = 1 / M3^2; then for n X n matrices P2, P3, P4...perform P^n * [1, 0, 0] letting this vector = k-th diagonal of the triangle.

A123020 Expansion of (1 -5x +5x^2)/((1 -2x)(1 -4*x +x^2)).

Original entry on oeis.org

1, 1, 2, 5, 14, 43, 142, 493, 1766, 6443, 23750, 88045, 327406, 1219531, 4546622, 16958765, 63272054, 236096683, 881049142, 3287968813, 12270563966, 45793762763, 170903438510, 637817894125, 2380363943686, 8883629492011

Offset: 0

Roger L. Bagula and Gary W. Adamson, Sep 24 2006

Denominator of reduced g.f. is essentially the characteristic polynomial of [1, 1, 0; 1, 2, 1; 0, 1, 3]. - Paul Barry, Dec 17 2009

G. C. Greubel, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Morgan-Voyce Polynomials
Index entries for linear recurrences with constant coefficients, signature (6,-9,2).

Cf. A001519, A080937.

I:=[1,1,2]; [n le 3 select I[n] else 6*Self(n-1) - 9*Self(n-2) +2*Self(n-3): n in [1..31]]; // G. C. Greubel, Jul 11 2021

Table[(2^n - ChebyshevT[n + 1, 2] + 4*ChebyshevT[n, 2])/3, {n,0,30}] (* G. C. Greubel, Jul 11 2021 *)

def a(n): return (1/3)*(2^n - chebyshev_T(n+1, 2) + 4*chebyshev_T(n, 2))
[a(n) for n in (0..30)] # G. C. Greubel, Jul 11 2021

From Paul Barry, Dec 17 2009: (Start)
G.f.: 1/(1 -x -x^2/(1 -2*x -x^2/(1-3*x))) = (1-5*x+5*x^2)/(1-6*x+9*x^2-2*x^3).
a(n) = ((2+sqrt(3))/6)*(2-sqrt(3))^n + ((2-sqrt(3))/6)*(2+sqrt(3))^n + 2^n/3. (End)
a(n) = (1/3)*(2^n - ChebyshevT(n+1, 2) + 4*ChebyshevT(n, 2)). - G. C. Greubel, Jul 11 2021
3*a(n) = 2^n +A001075(n-1), n>=1. - R. J. Mathar, Aug 05 2021

Edited by N. J. A. Sloane, Jun 13 2007

New name and change of offset by G. C. Greubel, Jul 11 2021

A359311 Number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2*n steps which reach at least 6 at some point.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 12, 89, 528, 2755, 13244, 60214, 263121, 1116791, 4637476, 18936940, 76327705, 304520286, 1205152900, 4738962369, 18540020091, 72240167011, 280579954028, 1087033982059, 4203231136230, 16228518078010, 62588797371361, 241198478726775

Offset: 0

Greg Dresden, Jan 21 2023

a(n) = A000108(n) - A080937(n), which is #(Catalan paths) - #(Catalan paths of height <= 5).

			a(n) = 0 for n <= 5 because no path of length <= 10 can reach 6 and then descend to 0.
a(6) = 1 because there is one path of length 12 that reaches 6: six steps up, and six steps back down.

Cf. A000108, A080936, A080937, A289419.

a:= n-> binomial(2*n, n)/(n+1)-(<<0|1|0>,
        <0|0|1>, <1|-6|5>>^n. <<1, 1, 2>>)[1, 1]:
seq(a(n), n=0..35);  # Alois P. Heinz, Jan 21 2023

Table[Sum[Binomial[2(n + 1), (n + 1) + 7 k] - 4 Binomial[2n, n + 7k], {k,1,n}], {n,0,30}]

a(n) = Sum_{k >= 1} binomial(2*(n+1), (n+1) + 7*k) - 4*binomial(2*n, n+7*k).
From Alois P. Heinz, Jan 21 2023: (Start)
G.f.: (1-sqrt(1-4*x))/(2*x) - (1-4*x+3*x^2)/(1-5*x+6*x^2-x^3).
a(n) = Sum_{k=6..n} A080936(n,k). (End)
D-finite with recurrence -(n+1)*(n-6)*a(n) +3*(3*n^2-17*n+4)*a(n-1) +2*(-13*n^2+80*n-87)*a(n-2) +(25*n^2-161*n+246)*a(n-3) -2*(n-3)*(2*n-7)*a(n-4)=0. - R. J. Mathar, Jan 25 2023

cp's OEIS Frontend

A202062 Number of ascent sequences avoiding the pattern 201.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A202059 Number of ascent sequences avoiding the pattern 100.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A202060 Number of ascent sequences avoiding the pattern 110.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A202061 Number of ascent sequences avoiding the pattern 120.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A216054 Square array T, read by antidiagonals: T(n,k) = 0 if n-k >= 1 or if k-n >= 6, T(0,0) = T(0,1) = T(0,2) = T(0,3) = T(0,4) = T(0,5) = 1, T(n,k) = T(n-1,k) + T(n,k-1).

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

Formula

A216235 Square array T, read by antidiagonals: T(n,k) = 0 if n-k >= 2 or if k-n >= 5, T(1,0) = T(0,0) = T(0,1) = T(0,2) = T(0,3) = T(0,4) = 1, T(n,k) = T(n-1,k) + T(n,k-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A038213 Top line of 3-wave sequence A038196, also bisection of A006356.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A122881 Triangle read by rows: number of Catalan paths of 2n steps of all values less than or equal to m.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A123020 Expansion of (1 -5*x +5*x^2)/((1 -2*x)*(1 -4*x +x^2)).

Views

Author

Keywords

Comments

Links

A123020 Expansion of (1 -5x +5x^2)/((1 -2x)(1 -4*x +x^2)).