A000102 a(n) = number of compositions of n in which the maximum part size is 4.

0, 0, 0, 0, 1, 2, 5, 12, 27, 59, 127, 269, 563, 1167, 2400, 4903, 9960, 20135, 40534, 81300, 162538, 324020, 644282, 1278152, 2530407, 5000178, 9863763, 19427976, 38211861, 75059535, 147263905, 288609341, 565047233, 1105229439, 2159947998, 4217784107, 8230006378

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

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

Examples

			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
		

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

Programs

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

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

Extensions

More terms from Sascha Kurz, Aug 15 2002

Definition improved by David Callan and Franklin T. Adams-Watters