login
Number of ascent sequences of length n avoiding the pattern 0000.
2

%I #20 Feb 12 2020 08:09:38

%S 1,1,2,5,14,47,180,773,3701,19488,111890,695786,4656185,33356828,

%T 254675642,2063984616,17694054723,159958176316,1520689121858,

%U 15165205111010

%N Number of ascent sequences of length n avoiding the pattern 0000.

%H Paul Duncan and Einar Steingrimsson, <a href="https://arxiv.org/abs/1109.3641">Pattern avoidance in ascent sequences</a>, arXiv:1109.3641 [math.CO], 2011.

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

%p b:= proc(n, i, t, p) option remember; `if`(n=0, 1, add(

%p `if`(coeff(p, x, j)=3, 0, b(n-1, j, t+

%p `if`(j>i, 1, 0), p+x^j)), j=1..t+1))

%p end:

%p a:= n-> b(n, 0$3):

%p seq(a(n), n=0..12);

%t 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]];

%t Table[Print["a(",n,") = ",a[n]];a[n],{n, 0, 15}] (* _Vincenzo Librandi_, Feb 12 2020 *)

%Y Column k=3 of A294220.

%Y Cf. A022493.

%K nonn,more

%O 0,3

%A _Alois P. Heinz_, Aug 06 2018

%E a(18) from _Vaclav Kotesovec_, Aug 20 2018

%E a(19) from _Vaclav Kotesovec_, Aug 23 2018