A006979 a(n) is the number of compositions of n in which the maximum part size is 5.

0, 0, 0, 0, 0, 1, 2, 5, 12, 28, 63, 139, 303, 653, 1394, 2953, 6215, 13008, 27095, 56201, 116143, 239231, 491326, 1006420, 2056633, 4193706, 8534653, 17337764, 35162804, 71205504, 143990366, 290795624, 586566102, 1181834852, 2378701408

Offset: 0

Author

Simon Plouffe

Keywords

• nonn

Comments

a(n) is also the number of binary sequences of length n-1 in which the longest run of 0's is exactly 4. Example: a(7) = 5 because there are 5 binary sequences of length 6 in which the longest run of 0's is exactly 4: 000010, 000011, 010000, 110000, 100001. - Geoffrey Critzer, Nov 07 2008

References

• 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

• Matthew House, Table of n, a(n) for n = 0..3390
• Index entries for linear recurrences with constant coefficients, signature (2,1,0,-1,-3,-4,-3,-2,-1).

Crossrefs

Cf. A048003.

Programs

Maple

a:= n-> (Matrix(9, (i,j)-> if i=j-1 then 1 elif j=1 then [2, 1, 0, -1, -3, -4, -3, -2, -1][i] else 0 fi)^n) [1,6]: seq(a(n), n=0..40); # Alois P. Heinz, Oct 29 2008

Mathematica

CoefficientList[Series[x^5/((1 - x - x^2 - x^3 - x^4) (1 - x - x^2 - x^3 - x^4 - x^5)), {x, 0, 34}], x] (* Michael De Vlieger, Feb 11 2017 *)

Formula

G.f.: x^5 / ((1-x-x^2-x^3-x^4)*(1-x-x^2-x^3-x^4-x^5)). - Alois P. Heinz, Oct 29 2008

Extensions

More terms and better definition from Alois P. Heinz, Oct 29 2008

Offset corrected by Matthew House, Feb 11 2017