0,4

Might be called the Middle Sequence, since it is a cross between the Fibonacci sequence A000045 and the Padovan sequence A000931. - Kyle Ledbetter Lucas, Jun 13 2009

A Lam{\'e} sequence of higher order.

Could have begun 1,0,0,1,1,1,2,3,4,6,9,... but that would spoil many nice properties.

Number of tilings of a 3 X n rectangle with straight trominoes.

Number of ways to arrange n-1 tatami mats in a 2 X (n-1) room such that no 4 meet at a point. For example, there are 6 ways to cover a 2 X 5 room, described by 11111, 2111, 1211, 1121, 1112, 212.

Equivalently, number of ordered partitions of n-1 into parts 1 and 2 with no two 2's adjacent. E.g. there are 6 such ways to partition 5, namely 11111, 2111, 1211, 1121, 1112, 212, so a(9) = 6.

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 m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.

a(n-4) = number of n-bit sequences that start and end with 0 but avoid both 010 and 0110. - David Callan (callan(AT)stat.wisc.edu), Mar 25 2004

a(n+2) = number of n-bit 0-1 sequences that avoid both 00 and 010. - David Callan (callan(AT)stat.wisc.edu), Mar 25 2004

Also number of compositions of n+1 into parts congruent to 1 mod m. - Vladeta Jovovic (vladeta(AT)eunet.rs), Feb 09 2005

Row sums of Riordan array (1/(1-x^3), x/(1-x^3)). - Paul Barry (pbarry(AT)wit.ie), Feb 25 2005

Row sums of Riordan array (1,x(1+x^2)). - Paul Barry (pbarry(AT)wit.ie), Jan 12 2006

Starting with offset 1 = row sums of triangle A145580 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 13 2008]

Number of digits in A061582. [From Dmitry Kamenetsky (dkamen(AT)rsise.anu.edu.au), Jan 17 2009]

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 78,80.

E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.

M. Feinberg, New slants, Fib. Quart. 2 (1964), 223-227.

T. M. Green, Recurrent sequences and Pascal's triangle, Math. Mag., 41 (1968), 13-21.

J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.

D. Jarden, Recurring Sequences. Riveon Lematematika, Jerusalem, 1966.

H. Langman, Play Mathematics. Hafner, NY, 1962, p. 13.

Antonio M. Oller-Marc\'en, "The Dying Rabbit Problem Revisited", INTEGERS, 9 (2009), 129-138 [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), May 09 2009]

David Sankoff and Lani Haque, Power Boosts for Cluster Tests, in Comparative Genomics, Lecture Notes in Computer Science, Volume 3678/2005, Springer-Verlag. [Added by N. J. A. Sloane, Jul 09 2009]

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

T. D. Noe, Table of n, a(n) for n=0..500

J.-P. Allouche and T. Johnson, Narayana's Cows and Delayed Morphisms

J.-P. Allouche and T. Johnson, Narayana's Cows and Delayed Morphisms

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 373

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 14

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 376

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.

T. Sillke, The binary form of Conway's Sequence

E. Wilson, The Scales of Mt. Meru

Index entries for sequences related to linear recurrences with constant coefficients

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

a(n) = sum(binomial(n-2*i, i), i=0..n/3).

a(n) = a(n-2) + a(n-3) + a(n-4) for n>3.

a(n) = floor( d*c^n + 1/2) where c is the real root of x^3-x^2-1 and d is the real root of 31*x^3-31*x^2+9*x-1 ( c=1.465571231876768... and d= 0.611491991950812...) - Benoit Cloitre (benoit7848c(AT)orange.fr), Nov 30 2002

a(n)=sum{k=0..n, binomial(floor((n+2k-2)/3), k)}. - Paul Barry (pbarry(AT)wit.ie), Jul 06 2004

a(n)=sum{k=0..n, C(k, floor((n-k)/2))(1+(-1)^(n-k))/2}; - Paul Barry (pbarry(AT)wit.ie), Jan 12 2006

a(n)=sum{k=0..n, C((n+2k)/3,(n-k)/3)*(2*cos(2*pi*(n-k)/3)+1)/3}; - Paul Barry (pbarry(AT)wit.ie), Dec 15 2006

a(n) = term (1,1) in matrix [1,1,0; 0,0,1; 1,0,0]^n - Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jun 20 2008

Contribution from Paul D. Hanna (pauldhanna(AT)juno.com), Oct 08 2009: (Start)

G.f.: exp( Sum_{n>=1} [(1+sqrt(1+4x))^n + (1-sqrt(1+4x))^n]*(x/2)^n/n ).

Logarithmic derivative equals A001609. (End)

sage: taylor( mul(x/(1 - x - x^3) for i in xrange(1,2)),x,0,38)#>> solution: x + x^2 + x^3 + 2*x^4 + 3*x^5 + 4*x^6 + 6*x^7 + 9*x^8 + 13*x^9 + 19*x^10 + 28*x^11 + 41*x^12 + 60*x^13 + 88*x^14 + 129*x^15 + 189*x^16 + 277*x^17 + 406*x^18 + 595*x^19 + 872*x^20 + 1278*x^21 + 1873*x^22 + 2745*x^23 + 4023*x^24 + 5896*x^25 + 8641*x^26 + 12664*x^27 + 18560*x^28 + 27201*x^29 + 39865*x^30 + 58425*x^31 + 85626*x^32 + 125491*x^33 + 183916*x^34 + 269542*x^35 + 395033*x^36 + 578949*x^37 + 848491*x^38 [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 29 2009]

f := proc(r) local t1, i; t1 := []; for i from 1 to r do t1 := [op(t1), 0]; od: for i from 1 to r+1 do t1 := [op(t1), 1]; od: for i from 2*r+2 to 50 do t1 := [op(t1), t1[i-1]+t1[i-1-r]]; od: t1; end; # set r = order

with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 2)}, unlabeled]: seq(count(SeqSetU, size=j), j=3..40); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Oct 10 2006

seq(add(binomial(n-2*k, k), k=0..floor(n/3)), n=0..37); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 03 2007

BB :=-x/(-1+x^2+x^6); series(BB, x, 77); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 24 2007

A000930:=-1/(-1+z+z**3); [S. Plouffe in his 1992 dissertation.]

a := n -> (Matrix([[1, 1, 0], [0, 0, 1], [1, 0, 0]])^n)[1, 1]; seq ((a(n)), n=0..50); - Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jun 20 2008

a[0] = 1; a[1] = a[2] = 1; a[n_] := a[n] = a[n - 1] + a[n - 3]; Table[ a[n], {n, 0, 40} ]

CoefficientList[Series[1/(1-x-x^3), {x, 0, 45}], x] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 22 2007

(Other) sage: taylor( mul(x/(1 - x - x^3) for i in xrange(1, 2)), x, 0, 38)# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 29 2009]

(PARI) {a(n)=polcoeff(exp(sum(m=1, n, ((1+sqrt(1+4*x))^m + (1-sqrt(1+4*x))^m)*(x/2)^m/m)+x*O(x^n)), n)} [From Paul D. Hanna (pauldhanna(AT)juno.com), Oct 08 2009]

For Lam{\'e} sequences of orders 1 through 9 see A000045, this one, A017898-A017904.

Cf. A048715, A069241.

See also A000079, A003269, A003520, A005708, A005709, A005710.

Essentially the same as A068921 and A078012.

A145580 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 13 2008]

Cf. A001609. [From Paul D. Hanna (pauldhanna(AT)juno.com), Oct 08 2009]

Sequence in context: A017825 A159848 A017826 this_sequence A068921 A078012 A135851

Adjacent sequences: A000927 A000928 A000929 this_sequence A000931 A000932 A000933

nonn,easy,nice

N. J. A. Sloane (njas(AT)research.att.com).