login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000100 a(n) = number of compositions of n in which the maximal part is 3.
(Formerly M1394 N0543)
6
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

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->inf} a(n)/(a(n-1)+a(n-2)+a(n-3)) = 1 and lim_{n->inf} 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

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

Index entries for linear recurrences with constant coefficients, signature (2, 1, -1, -2, -1).

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

EXAMPLE

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

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

PROG

(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

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

CROSSREFS

Cf. A000045.

Sequence in context: A174162 A186253 A226462 * A175867 A083005 A133489

Adjacent sequences:  A000097 A000098 A000099 * A000101 A000102 A000103

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Henry Bottomley, Dec 15 2000

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 25 21:19 EDT 2017. Contains 284111 sequences.