|
Search: id:A000100
|
|
|
| A000100 |
|
a(n) = number of compositions of n in which the maximum part size is 3.
(Formerly M1394 N0543)
|
|
+0
4
|
|
| 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; listen)
|
|
|
OFFSET
|
0,5
|
|
|
COMMENT
|
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 (Gerald.McGarvey(AT)comcast.net), 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. [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Nov 06 2008]
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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.
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
|
|
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). - Frank Adams-Watters (FrankTAW(AT)Netscape.net), 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 (callan(AT)stat.wisc.edu), 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 [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Nov 06 2008]
|
|
MAPLE
|
(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..35); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Aug 04 2008]
|
|
CROSSREFS
|
Cf. A000045.
Sequence in context: A140992 A093053 A075712 this_sequence A083005 A133489 A060153
Adjacent sequences: A000097 A000098 A000099 this_sequence A000101 A000102 A000103
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
More terms from Henry Bottomley (se16(AT)btinternet.com), Dec 15 2000
Better definition from David Callan and Frank Adams-Watters.
|
|
|
Search completed in 0.002 seconds
|
