OFFSET
0,5
COMMENTS
a(n+3) is also the number of binary words w of length n with the condition that every subword 11 of w is part of a longer subword of w containing only 1-digits. The a(3+3)=6 binary words of length 3 are 000, 001, 010, 100, 101, 111. - Alois P. Heinz, Mar 25 2009
a(n+2) is the number of compositions of n avoiding the part 3. [Joerg Arndt, Jul 13 2014]
Starting with 1 = INVERT transform of (1,1,0,1,1,1,...). Example: a(9) = 39 = (1,1,2,3,6,11,21) dot (1,1,1,1,0,1,1) = (1+1+2+3+0+11+21). - Gary W. Adamson, Apr 27 2009
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, example 11.
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3
J. J. Madden, A generating function for the distribution of runs in binary words, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=3, k=0.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1).
FORMULA
a(n) = 2*a(n-1) - a(n-3) + a(n-4) for n >= 4.
a(n+2) = Sum_{i=0..n} F(i+1)*C(n-i,i) where F=A000045. - Benoit Cloitre, Sep 21 2004
G.f.: x^2*(1-x)/(1-2*x+x^3-x^4). - Vladimir Kruchinin, May 11 2011
a(n) = A218796(n-2,0) for n>1. - Alois P. Heinz, Nov 06 2012
MAPLE
a:= n-> -(Matrix(4, (i, j)-> if i=j-1 then 1 elif j=1 then [2, 0, -1, 1][i] else 0 fi)^n)[3, 2]: seq (a(n), n=0..40); # Alois P. Heinz, Mar 25 2009
MATHEMATICA
LinearRecurrence[{2, 0, -1, 1}, {0, 0, 1, 1}, 40] (* Harvey P. Dale, Jul 23 2013 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved