OFFSET
0,6
COMMENTS
a(n) is also the number of binary sequences of length n-1 in which the longest run of consecutive 0's is exactly three. - Geoffrey Critzer, Nov 06 2008
REFERENCES
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29.
LINKS
T. D. Noe, Table of n, a(n) for n=0..200
Nick Hobson, Python program for this sequence
J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29. (Annotated scanned copy)
Index entries for linear recurrences with constant coefficients, signature (2, 1, 0, -2, -3, -2, -1).
FORMULA
G.f.: x^4/(1 - x - x^2 - x^3)/(1 - x - x^2 - x^3 - x^4).
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-4) - 3*a(n-5) - 2*a(n-6) - a(n-7). Convolution of tribonacci and tetranacci numbers (A000073 and A000078). - Franklin T. Adams-Watters, Jan 13 2006
EXAMPLE
For example, a(6)=5 counts 1+1+4, 2+4, 4+2, 4+1+1, 1+4+1. - David Callan, Dec 09 2004
a(6)=5 because there are 5 binary sequences of length 5 in which the longest run of consecutive 0's is exactly 3; 00010, 00011, 01000, 10001, 11000. - Geoffrey Critzer, Nov 06 2008
MAPLE
a:= n-> (Matrix(7, (i, j)-> if i+1=j then 1 elif j=1 then [2, 1, 0, -2, -3, -2, -1][i] else 0 fi)^n)[1, 5]: seq(a(n), n=0..40); # Alois P. Heinz, Oct 07 2008
MATHEMATICA
a[n_] := MatrixPower[ Table[ Which[i+1 == j, 1, j == 1, {2, 1, 0, -2, -3, -2, -1}[[i]], True, 0], {i, 1, 7}, {j, 1, 7}], n][[1, 5]]; Table[a[n], {n, 0, 34}] (* Jean-François Alcover, May 28 2013, after Alois P. Heinz *)
LinearRecurrence[{2, 1, 0, -2, -3, -2, -1}, {0, 0, 0, 0, 1, 2, 5}, 40] (* Harvey P. Dale, Jul 01 2013 *)
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
More terms from Sascha Kurz, Aug 15 2002
Definition improved by David Callan and Franklin T. Adams-Watters
STATUS
approved