A000100 a(n) is the number of compositions of n in which the maximal part is 3.

0, 0, 0, 1, 2, 5, 11, 23, 47, 94, 185, 360, 694, 1328, 2526, 4781, 9012, 16929, 31709, 59247, 110469, 205606, 382087, 709108, 1314512, 2434364, 4504352, 8328253, 15388362, 28417385, 52451811, 96771787, 178473023, 329042890, 606466009, 1117506500

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

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

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

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

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

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

Examples

			For example, a(5)=5 counts 1+1+3, 2+3, 3+2, 3+1+1, 1+3+1. - _David Callan_, Dec 09 2004
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
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 + ...
		

References

• A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 47, ex. 4.
• 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,-1,-2,-1).

Crossrefs

Cf. A000045.

Programs

Haskell

a000100 n = a000100_list !! (n-1)
a000100_list = f (tail a000045_list) [head a000045_list] where
   f (x:xs) ys = (sum $ zipWith (*) ys a000073_list) : f xs (x:ys)
-- Reinhard Zumkeller, Jul 31 2012

Maple

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

Mathematica

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 *)
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 *)
LinearRecurrence[{2,1,-1,-2,-1},{0,0,0,1,2},40] (* Harvey P. Dale, Jul 22 2013 *)

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

Formula

G.f.: x^3/((1-x-x^2)*(1-x-x^2-x^3)).

a(n+3) = Sum_{k=0..n} F(k)*T(n-k), F(i)=A000045(i+1), T(i)=A000073(i+2).

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

Extensions

More terms from Henry Bottomley, Dec 15 2000

Better definition from David Callan and Franklin T. Adams-Watters