login
A049856
a(n) = (Sum{k=0..n-1} a(k)) - a(n-3), with a(0)=0, a(1)=0, a(2)=1.
7
0, 0, 1, 1, 2, 3, 6, 11, 21, 39, 73, 136, 254, 474, 885, 1652, 3084, 5757, 10747, 20062, 37451, 69912, 130509, 243629, 454797, 848997, 1584874, 2958580, 5522960, 10310043, 19246380, 35928380, 67069677, 125203017, 233724034, 436306771, 814480202, 1520439387
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
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.
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
a(n) = A059633(n+1) - A059633(n). - R. J. Mathar, Aug 04 2019
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
Cf. A049858.
Sequence in context: A034074 A018175 A316356 * A302017 A113409 A092684
KEYWORD
nonn,easy
STATUS
approved