A049856 a(n) = (Sum{k=0..n-1} a(k)) - a(n-3), with a(0)=0, a(1)=0, a(2)=1.

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

Author

Clark Kimberling

Keywords

• nonn
• easy
• changed

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

For n>=4, a(n) is the number of binary strings of length n-3 without any maximal runs of ones of length 2. - Félix Balado, Aug 25 2025

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

Crossrefs

Cf. A049858.

Programs

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

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