|
%I M1394 N0543 #116 Sep 05 2023 01:54:53
%S 0,0,0,1,2,5,11,23,47,94,185,360,694,1328,2526,4781,9012,16929,31709,
%T 59247,110469,205606,382087,709108,1314512,2434364,4504352,8328253,
%U 15388362,28417385,52451811,96771787,178473023,329042890,606466009,1117506500
%N a(n) is the number of compositions of n in which the maximal part is 3.
%C For n > 5, a(n) - (a(n-3)+a(n-2)+a(n-1)) = F(n-2) where F(i) is the i-th Fibonacci number; e.g., 11 - (1+2+5) = 3, 23 - (2+5+11) = 8; also lim_{n->oo} a(n)/(a(n-1)+a(n-2)+a(n-3)) = 1 and lim_{n->oo} a(n)*a(n-2)/a(n-1)^2 = 1. - _Gerald McGarvey_, Jun 26 2004
%C a(n) is also the number of binary sequences of length n-1 in which the longest run of 0's is exactly two. - _Geoffrey Critzer_, Nov 06 2008
%C a(n) is also the difference between the n-th tribonacci number and the n-th Fibonacci number; i.e., a(n) = A000073(n) - A000045(n). - _Gregory L. Simay_, Jan 31 2018
%C Let F_0(n) be the n-th Fibonacci number, A000045(n). Let F_1(n) = Sum_{j=1..n} A000045(n+1-j)*A000045(j). Let F_r(n) = Sum_{j=1..n} F_(r-1)(n+1-j)*A000045(j). Then the number of compositions of n having exactly r 3's as the highest part is F_r(n), and a(n+1) = F_1(n-3) + F_1(n-6) + ... - _Gregory L. Simay_, Apr 17 2018
%C The Apr 17 2018 comment can be generalized. Let F(n,k) be the n-th k-step Fibonacci number, with the convention that F(0,k)=0 and F(1,k)=1. Let F(n,k,0)= F(n,k) Let F(n, k, 1) = Sum_{j=1..n} F(n+1-j,k)*F(j,k). Let F(n,k,r) = Sum_{j=1..n} F(n+1-j, k, r-1) * A000045(j, k). Let G(n,k,r) be the number of compositions of n having k as the largest part exactly r times. Then G(n,k,r) = F(n+1 - kr, k-1, r). - _Gregory L. Simay_, May 17 2018
%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 47, ex. 4.
%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="/A000100/b000100.txt">Table of n, a(n) for n = 0..200</a>
%H Nick Hobson, <a href="/A000100/a000100.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_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-1,-2,-1).
%F G.f.: x^3/((1-x-x^2)*(1-x-x^2-x^3)).
%F a(n+3) = Sum_{k=0..n} F(k)*T(n-k), F(i)=A000045(i+1), T(i)=A000073(i+2).
%F a(n) = 2*a(n-1)+a(n-2)-a(n-3)-2*a(n-4)-a(n-5). Convolution of Fibonacci and tribonacci numbers (A000045 and A000073). - _Franklin T. Adams-Watters_, Jan 13 2006
%e For example, a(5)=5 counts 1+1+3, 2+3, 3+2, 3+1+1, 1+3+1. - _David Callan_, Dec 09 2004
%e a(5)=5 because there are 5 binary sequences of length 4 in which the longest run of consecutive 0's is exactly two: 0010, 0011, 0100, 1001, 1100. - _Geoffrey Critzer_, Nov 06 2008
%e G.f.: x^3 + 2*x^4 + 5*x^5 + 11*x^6 + 23*x^7 + 47*x^8 + 94*x^9 + 185*x^10 + 360*x^11 + ...
%p a:= n -> (Matrix(5, (i,j)-> if (i=j-1) then 1 elif j=1 then [2,1,-1,-2,-1][i] else 0 fi)^(n))[1,4]: seq(a(n), n=0..40); # _Alois P. Heinz_, Aug 04 2008
%t a[n_] := a[n] = a[n-1] + a[n-2] + a[n-3] + Fibonacci[n-2]; a[n_ /; n < 3] = 0; Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Aug 03 2012, after _Gerald McGarvey_ *)
%t a[ n_] := SeriesCoefficient[ If[ n > 0, x^3 / ((1 - x - x^2) (1 - x - x^2 - x^3)), -x^2 / ((1 + x - x^2) (1 + x + x^2 - x^3))], {x, 0, Abs@n}]; (* _Michael Somos_, Jun 01 2013 *)
%t LinearRecurrence[{2,1,-1,-2,-1},{0,0,0,1,2},40] (* _Harvey P. Dale_, Jul 22 2013 *)
%o (Haskell)
%o a000100 n = a000100_list !! (n-1)
%o a000100_list = f (tail a000045_list) [head a000045_list] where
%o f (x:xs) ys = (sum $ zipWith (*) ys a000073_list) : f xs (x:ys)
%o -- _Reinhard Zumkeller_, Jul 31 2012
%o (PARI) {a(n) = polcoeff( if( n>0, x^3 / ((1 - x - x^2) * (1 - x - x^2 - x^3)), -x^2 / ((1 + x - x^2) * (1 + x + x^2 - x^3))) + x * O(x^abs(n)), abs(n))}; /* _Michael Somos_, Jun 01 2013 */
%Y Cf. A000045.
%K nonn,easy,nice
%O 0,5
%A _N. J. A. Sloane_
%E More terms from _Henry Bottomley_, Dec 15 2000
%E Better definition from _David Callan_ and _Franklin T. Adams-Watters_
|
