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

Author

Alois P. Heinz, Aug 06 2018

Keywords

• nonn
• more

Links

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

Crossrefs

Column k=3 of A294220.

Cf. A022493.

Programs

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

Formula

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

Extensions

a(18) from Vaclav Kotesovec, Aug 20 2018

a(19) from Vaclav Kotesovec, Aug 23 2018