%I A000930 M0571 N0207
%S A000930 1,1,1,2,3,4,6,9,13,19,28,41,60,88,129,189,277,406,
%T A000930 595,872,1278,1873,2745,4023,5896,8641,12664,18560,27201,
%U A000930 39865,58425,85626,125491,183916,269542,395033,578949,848491
%N A000930 a(n) = a(n-1) + a(n-3).
%C A000930 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
%C A000930 A Lam{\'e} sequence of higher order.
%C A000930 Could have begun 1,0,0,1,1,1,2,3,4,6,9,... but that would spoil many 
               nice properties.
%C A000930 Number of tilings of a 3 X n rectangle with straight trominoes.
%C A000930 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.
%C A000930 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.
%C A000930 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.
%C A000930 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
%C A000930 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
%C A000930 Also number of compositions of n+1 into parts congruent to 1 mod m. - 
               Vladeta Jovovic (vladeta(AT)eunet.rs), Feb 09 2005
%C A000930 Row sums of Riordan array (1/(1-x^3), x/(1-x^3)). - Paul Barry (pbarry(AT)wit.ie), 
               Feb 25 2005
%C A000930 Row sums of Riordan array (1,x(1+x^2)). - Paul Barry (pbarry(AT)wit.ie), 
               Jan 12 2006
%C A000930 Starting with offset 1 = row sums of triangle A145580 [From Gary W. Adamson 
               (qntmpkt(AT)yahoo.com), Oct 13 2008]
%C A000930 Number of digits in A061582. [From Dmitry Kamenetsky (dkamen(AT)rsise.anu.edu.au), 
               Jan 17 2009]
%D A000930 A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of 
               combinatorial proof, M.A.A. 2003, id. 78,80.
%D A000930 E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional 
               lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
%D A000930 M. Feinberg, New slants, Fib. Quart. 2 (1964), 223-227.
%D A000930 T. M. Green, Recurrent sequences and Pascal's triangle, Math. Mag., 41 
               (1968), 13-21.
%D A000930 J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, 
               Math. Ann., 45 (1894), 371-380.
%D A000930 D. Jarden, Recurring Sequences. Riveon Lematematika, Jerusalem, 1966.
%D A000930 H. Langman, Play Mathematics. Hafner, NY, 1962, p. 13.
%D A000930 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]
%D A000930 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]
%D A000930 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000930 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A000930 T. D. Noe, <a href="b000930.txt">Table of n, a(n) for n=0..500</a>
%H A000930 J.-P. Allouche and T. Johnson, <a href="http://www.lri.fr/~allouche/johnson2.pdf">
               Narayana's Cows and Delayed Morphisms</a>
%H A000930 J.-P. Allouche and T. Johnson, <a href="http://kalvos.org/johness1.html">
               Narayana's Cows and Delayed Morphisms</a>
%H A000930 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
               Publications/books.html">Analytic Combinatorics</a>, 2009; see page 
               373
%H A000930 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=14">
               Encyclopedia of Combinatorial Structures 14</a>
%H A000930 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=376">
               Encyclopedia of Combinatorial Structures 376</a>
%H A000930 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">
               Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures</
               a>, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 
               1992.
%H A000930 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">
               1031 Generating Functions and Conjectures</a>, Universit\'{e} du 
               Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
%H A000930 T. Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/
               series001">The binary form of Conway's Sequence</a>
%H A000930 E. Wilson, <a href="http://www.anaphoria.com/meruone.PDF">The Scales 
               of Mt. Meru</a>
%H A000930 <a href="Sindx_Rea.html#recLCC">Index entries for sequences related to 
               linear recurrences with constant coefficients</a>
%F A000930 G.f.: 1/(1-x-x^3).
%F A000930 a(n) = sum(binomial(n-2*i, i), i=0..n/3).
%F A000930 a(n) = a(n-2) + a(n-3) + a(n-4) for n>3.
%F A000930 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
%F A000930 a(n)=sum{k=0..n, binomial(floor((n+2k-2)/3), k)}. - Paul Barry (pbarry(AT)wit.ie), 
               Jul 06 2004
%F A000930 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
%F A000930 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
%F A000930 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
%F A000930 Contribution from Paul D. Hanna (pauldhanna(AT)juno.com), Oct 08 2009: 
               (Start)
%F A000930 G.f.: exp( Sum_{n>=1} [(1+sqrt(1+4x))^n + (1-sqrt(1+4x))^n]*(x/2)^n/n 
               ).
%F A000930 Logarithmic derivative equals A001609. (End)
%e A000930 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]
%p A000930 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
%p A000930 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
%p A000930 seq(add(binomial(n-2*k,k),k=0..floor(n/3)),n=0..37); - Zerinvary Lajos 
               (zerinvarylajos(AT)yahoo.com), Apr 03 2007
%p A000930 BB :=-x/(-1+x^2+x^6); series(BB,x,77); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), 
               Apr 24 2007
%p A000930 A000930:=-1/(-1+z+z**3); [S. Plouffe in his 1992 dissertation.]
%p A000930 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
%t A000930 a[0] = 1; a[1] = a[2] = 1; a[n_] := a[n] = a[n - 1] + a[n - 3]; Table[ 
               a[n], {n, 0, 40} ]
%t A000930 CoefficientList[Series[1/(1-x-x^3), {x, 0, 45}], x] - Zerinvary Lajos 
               (zerinvarylajos(AT)yahoo.com), Mar 22 2007
%o A000930 (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]
%o A000930 (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]
%Y A000930 For Lam{\'e} sequences of orders 1 through 9 see A000045, this one, A017898-A017904.
%Y A000930 Cf. A048715, A069241.
%Y A000930 See also A000079, A003269, A003520, A005708, A005709, A005710.
%Y A000930 Essentially the same as A068921 and A078012.
%Y A000930 A145580 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 13 2008]
%Y A000930 Cf. A001609. [From Paul D. Hanna (pauldhanna(AT)juno.com), Oct 08 2009]
%Y A000930 Sequence in context: A017825 A159848 A017826 this_sequence A068921 A078012 
               A135851
%Y A000930 Adjacent sequences: A000927 A000928 A000929 this_sequence A000931 A000932 
               A000933
%K A000930 nonn,easy,nice
%O A000930 0,4
%A A000930 N. J. A. Sloane (njas(AT)research.att.com).