|
| |
|
|
A003269
|
|
a(n)=a(n-1)+a(n-4); a(0)=0, a(1)=a(2)=a(3)=1.
(Formerly M0526)
|
|
56
| |
|
|
0, 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181, 250, 345, 476, 657, 907, 1252, 1728, 2385, 3292, 4544, 6272, 8657, 11949, 16493, 22765, 31422, 43371, 59864, 82629, 114051, 157422, 217286, 299915, 413966, 571388, 788674, 1088589, 1502555, 2073943
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,6
|
|
|
COMMENTS
| This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 0...m-1. The generating function is 1/(1-x-x^m). Also a(n) = sum(binomial(n-(m-1)*i, i), i=0..n/m). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
For n>=3, a(n-3) = number of compositions of n in which each part is >=4. [From Milan R. Janjic (agnus(AT)blic.net), Jun 28 2010]
For n>=1, number of compositions of n into parts == 1 (mod 4). Example: a(8)=5 because there are 5 compositions of 8 into parts 1 or 5: (1,1,1,1,1,1,1,1), (1,1,1,5), (1,1,5,1), (1,5,1,1), (5,1,1,1). - Adi Dani, Jun 16 2011
a(n+1) is the number of compositions of n into parts 1 and 4. [Joerg Arndt, Jun 25 2011]
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=4, 2*a(n-3) equals the number of 2-colored compositions of n with all parts >=4, such that no adjacent parts have the same color.-Milan Janjic, Nov 27 2011
|
|
|
REFERENCES
| A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 120.
Russell Chamberlain, Sam Ginsburg, Manda Riehl and Chi Zhang, Generating Functions and Wilf-equivalence on Theta_k-embeddings, http://www.uwec.edu/surepam/SUREPAM%202011/Manda.pdf
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..501
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 377
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
E. Wilson, The Scales of Mt. Meru
Adi Dani, Compositions of natural numbers over arithmetic progressions
Index entries for two-way infinite sequences
Index entries for sequences related to linear recurrences with constant coefficients, signature (1,0,0,1).
|
|
|
FORMULA
| G.f.: x/(1-x-x^4).
G.f.: -1 + 1/(1-sum(k>=0, x^(4*k+1) ) ).
a(n) = a(n-3) + a(n-4) + a(n-5) + a(n-6) for n>4.
a(n) = floor(d*c^n + 1/2) where c is the positive real root of -x^4+x^3+1 and d is the positive real root of 283*x^4-18*x^2-8*x-1 ( c=1.38027756909761411... and d=0.3966506381592033124...) - Benoit Cloitre (benoit7848c(AT)orange.fr), Nov 30 2002
a(n) = term (1,2) in the 4x4 matrix [1,1,0,0; 0,0,1,0; 0,0,0,1; 1,0,0,0]^n. - Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jul 27 2008
Contribution from Paul Barry (pbarry(AT)wit.ie), Oct 20 2009: (Start)
a(n+1)=sum{k=0..n, C((n+3*k)/4,k)*((1+(-1)^(n-k))/2+cos(pi*n/2))/2};
a(n+1)=sum{k=0..n, C(k,floor((n-k)/3))(2*cos(2*pi*(n-k)/3)+1)/3}. (End)
a(n)=sum(j=0..(n-1)/3, binomial(n-1-3*j,j)); [From Vladimir Kruchinin (kru(AT)ie.tusur.ru), May 23 2011]
|
|
|
MAPLE
| with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 3)}, unlabeled]: seq(count(SeqSetU, size=j), j=4..51);
seq(add(binomial(n-3*k, k), k=0..floor(n/3)), n=0..47); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 03 2007
A003269:=z/(1-z-z**4); [S. Plouffe in his 1992 dissertation.]
ZL:=[S, {a = Atom, b = Atom, S = Prod(X, Sequence(Prod(X, b))), X = Sequence(b, card >= 3)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=3..50); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 26 2008
M := Matrix(4, (i, j)-> if j=1 then [1, 0, 0, 1][i] elif (i=j-1) then 1 else 0 fi); a := n -> (M^(n))[1, 2]; seq (a(n), n=0..48); - Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jul 27 2008
|
|
|
MATHEMATICA
| a[0] = 0; a[1] = a[2] = a[3] = 1; a[n_] := a[n] = a[n - 1] + a[n - 4]; Table[ a[n], {n, 0, 40} ]
CoefficientList[Series[x/(1 - x - x^4), {x, 0, 50}], x] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 29 2007
Table[Sum[Binomial[n - 3i - 1, i], {i, 0, 35}], {n, 0, 35}]
|
|
|
PROG
| (PARI) a(n)=polcoeff(if(n<0, (1+x^3)/(1+x^3-x^4), 1/(1-x-x^4))+x*O(x^abs(n)), abs(n))
(Haskell)
a003269 n = a003269_list !! n
a003269_list = 0 : 1 : 1 : 1 : zipWith (+) a003269_list
(drop 3 a003269_list)
-- Reinhard Zumkeller, Feb 27 2011
|
|
|
CROSSREFS
| Cf. A000045, A000079, A000930, A003520, A005708, A005709, A005710, A005711, A017898, A048718.
See A017898 for an essentially identical sequence.
A017817(n)=a(-4-n)*(-1)^n.
Sequence in context: A017836 A099559 A017898 * A087221 A206739 A107586
Adjacent sequences: A003266 A003267 A003268 * A003270 A003271 A003272
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Mohammad K. Azarian (ma3(AT)evansville.edu)
Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
Initial 0 prepended by N. J. A. Sloane (njas(AT)research.att.com), Apr 09 2008
|
| |
|
|
