login
a(0)=1, a(1)=1; for n>1, a(n) = Sum_{i=0..n/2} binomial(n-i-1,i)*a(n-2i-1) + ((n+1) mod 2).
1

%I #9 Jan 18 2019 20:53:15

%S 1,1,2,3,6,13,29,72,185,499,1414,4132,12554,39332,126815,420769,

%T 1430790,4986139,17772536,64708212,240482750,911008926,3515571177,

%U 13807269626,55147622607,223864614364,922952281744,3862571220690,16399630000144

%N a(0)=1, a(1)=1; for n>1, a(n) = Sum_{i=0..n/2} binomial(n-i-1,i)*a(n-2i-1) + ((n+1) mod 2).

%H G. C. Greubel, <a href="/A079512/b079512.txt">Table of n, a(n) for n = 0..925</a>

%H S. Kitaev, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00452-1">Multi-avoidance of generalized patterns</a>, Discrete Math., 260 (2003), 89-100.

%p with(combinat): a := array(0..50): a[0] := 1: a[1] := 1: for n from 2 to 50 do: a[n] := 0: for i from 0 to floor((n-1)/2.) do: a[n] := a[n]+binomial(n-i-1,i)*a[n-2*i-1]: od:a[n] := a[n]+((n+1) mod 2): od:seq(a[n],n=0..50);

%t a[0] = a[1] = 1; a[n_] := a[n] = Sum[ Binomial[n - i - 1, i]*a[n - 2i - 1], {i, 0, Floor[n/2]}] + Mod[n + 1, 2]; Table[a[n], {n, 0, 30}]

%o (PARI) {a(n) = sum(j=0, floor(n/2), binomial(n-j-1,j)*a(n-2*j-1)) + lift(Mod(n+1,2))};

%o vector(30, n, n--; if(n==0 && n==1, 1, a(n))) \\ _G. C. Greubel_, Jan 17 2019

%K easy,nonn

%O 0,3

%A _N. J. A. Sloane_, Jan 21 2003

%E More terms from Mark Hudson (mrmarkhudson(AT)hotmail.com), Jan 22 2003