|
%I M1409 N0551 #55 Nov 08 2017 17:48:14
%S 0,0,0,0,1,2,5,12,27,59,127,269,563,1167,2400,4903,9960,20135,40534,
%T 81300,162538,324020,644282,1278152,2530407,5000178,9863763,19427976,
%U 38211861,75059535,147263905,288609341,565047233,1105229439,2159947998
%N a(n) = number of compositions of n in which the maximum part size is 4.
%C 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
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29.
%H T. D. Noe, <a href="/A000102/b000102.txt">Table of n, a(n) for n=0..200</a>
%H Nick Hobson, <a href="/A000102/a000102.py.txt">Python program for this sequence</a>
%H J. L. Yucas, <a href="/A006980/a006980.pdf">Counting special sets of binary Lyndon words</a>, Ars Combin., 31 (1991), 21-29. (Annotated scanned copy)
%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (2, 1, 0, -2, -3, -2, -1).
%F G.f.: x^4/(1 - x - x^2 - x^3)/(1 - x - x^2 - x^3 - x^4).
%F 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
%e For example, a(6)=5 counts 1+1+4, 2+4, 4+2, 4+1+1, 1+4+1. - _David Callan_, Dec 09 2004
%e 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
%p 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
%t 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_ *)
%t LinearRecurrence[{2,1,0,-2,-3,-2,-1},{0,0,0,0,1,2,5},40] (* _Harvey P. Dale_, Jul 01 2013 *)
%K nonn,nice,easy
%O 0,6
%A _N. J. A. Sloane_
%E More terms from _Sascha Kurz_, Aug 15 2002
%E Definition improved by _David Callan_ and _Franklin T. Adams-Watters_
|
