A317784 Number of ascent sequences of length n avoiding the pattern 0000.

1, 1, 2, 5, 14, 47, 180, 773, 3701, 19488, 111890, 695786, 4656185, 33356828, 254675642, 2063984616, 17694054723, 159958176316, 1520689121858, 15165205111010

Offset

0,3

Links

Table of n, a(n) for n=0..19.

Paul Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv:1109.3641 [math.CO], 2011.

Formula

a(n) <= A022493(n) with equality only for n < 4.

Maple

b:= proc(n, i, t, p) option remember; `if`(n=0, 1, add(
      `if`(coeff(p, x, j)=3, 0, b(n-1, j, t+
      `if`(j>i, 1, 0), p+x^j)), j=1..t+1))
    end:
a:= n-> b(n, 0$3):
seq(a(n), n=0..12);

Mathematica

b[n_, i_, t_, p_, k_]:=b[n, i, t, p, k]=If[n==0, 1, Sum[If[Coefficient[p, x, j]==k, 0, b[n-1, j, t+If[j>i, 1, 0], p+x^j, k]], {j, 1, t+1}]]; a[n_]:=b[n, 0, 0, 0, Min[n, 3]];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 15}] (* Vincenzo Librandi, Feb 12 2020 *)

Crossrefs

Column k=3 of A294220.

Cf. A022493.

Sequence in context: A115276 A343664 A327702 * A096402 A007268 A326898

Adjacent sequences: A317781 A317782 A317783 * A317785 A317786 A317787

Keyword

nonn,more

Author

Alois P. Heinz, Aug 06 2018

Extensions

a(18) from Vaclav Kotesovec, Aug 20 2018

a(19) from Vaclav Kotesovec, Aug 23 2018

Status

approved