|
%I M0709
%S 0,1,2,3,5,9,16,28,49,86,151,265,465,816,1432,2513,4410,7739,13581,
%T 23833,41824,73396,128801,226030,396655,696081,1221537,2143648,
%U 3761840,6601569,11584946,20330163,35676949,62608681,109870576,192809420,338356945,593775046
%N For n = 0, 1, 2, a(n) = n; thereafter, a(n) = 2*a(n-1)-a(n-2)+a(n-3).
%C Number of compositions of n into parts congruent to {1,2} mod 4. - _Vladeta Jovovic_, Mar 10 2005
%C a(n)/a(n-1) tends to 1.75487766625...; an eigenvalue of the matrix M and a root to the characteristic polynomial. - _Gary W. Adamson_, May 25 2007
%C Starting with offset 1 = INVERT transform of (1, 1, 0, 0, 1, 1, 0, 0,...). [From Gary W. Adamson, May 04 2009]
%D R. L. Graham and N. J. A. Sloane, Anti-Hadamard matrices, Linear Alg. Applic., 62 (1984), 113-137.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A005314/b005314.txt">Table of n, a(n) for n=0..400</a>
%H P. Chinn and S. Heubach, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">Integer Sequences Related to Compositions without 2's</a>, J. Integer Seqs., Vol. 6, 2003.
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=426">Encyclopedia of Combinatorial Structures 426</a>
%H _Simon 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 _Simon 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 <a href="/index/Rec#order_03">Index to sequences with linear recurrences with constant coefficients</a>, signature (2,-1,1)
%F G.f.: x/(1-2*x+x^2-x^3). a(n) = Sum_{k=0..[(2n-1)/3]} binomial(n-1-[k/2], k), where [x]=floor(x). - Paul D. Hanna, Oct 22 2004
%F a(n) = Sum [k=0..n, C(n-k, 2k+1) ].
%F 23*a_n = 3*P_{2n+2} + 7*P_{2n+1} - 2*P_{2n}, where P_n are the Perrin numbers, A001608. - D. E. Knuth, Dec 09 2008
%F G.f. (z-1)*(1+z**2)/(-1+2*z+z**3-z**2) for the augmented version 1, 1, 2, 3, 5, 9, 16, 28, 49, 86, 151,... was given in _Simon Plouffe_'s thesis of 1992.
%F a(n) = a(n-1)+a(n-2)+a(n-4) = a(n-2)+A049853(n-1) = a(n-1)+A005251(n) = sum_{i <= n} A005251(i).
%F a(n) = Sum(binomial(n-k, 2k+1), {k=0...(n-1)/3}) - Richard Ollerton (r.ollerton(AT)uws.edu.au), May 12 2004
%F M^n*[1,0,0] = [a(n-2), a(n-1), a]; where M = the 3 X 3 matrix [0,1,0; 0,0,1; 1,-1,2]. Example M^5*[1,0,0] = [3,5,9]. - _Gary W. Adamson_, May 25 2007
%F a(n) = A000931(2*n + 4). - _Michael Somos_, Sep 18 2012
%F a(n) = A077954(-n - 2). - _Michael Somos_, Sep 18 2012
%F G.f.: 1/( 1 - sum(k>=0, x*(x-x^2+x^3)^k ) ) - 1. [_Joerg Arndt_, Sep 30 2012]
%F G.f.: 1/x^5/(Q(0)-1) - (1-2*x-x^2+x^3+x^4)/x^6, where Q(k)= 1 + (k+1)*x/(1 - x - x*(1-x)/(x + (k+1)*(1-x)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Apr 24 2013
%e x + 2*x^2 + 3*x^3 + 5*x^4 + 9*x^5 + 16*x^6 + 28*x^7 + ...
%t LinearRecurrence[{2, -1, 1}, {0, 1, 2}, 100] (* From Vladimir Joseph Stephan Orlovsky, Jul 03 2011 *)
%o (PARI) a(n)=sum(k=0,(2*n-1)\3,binomial(n-1-k\2,k))
%o (Haskell)
%o a005314 n = a005314_list !! n
%o a005314_list = 0 : 1 : 2 : zipWith (+) a005314_list
%o (tail $ zipWith (-) (map (2 *) $ tail a005314_list) a005314_list)
%o -- _Reinhard Zumkeller_, Oct 14 2011
%o (PARI) {a(n) = if( n<0, polcoeff( x^2 / (1 - x + 2*x^2 - x^3) + x * O(x^-n), -n), polcoeff( x / (1 - 2*x + x^2 - x^3) + x * O(x^n), n)))} /* Michael Somos, Sep 18 2012 */
%Y Equals row sums of triangle A099557. - Paul D. Hanna, Oct 22 2004
%Y Cf. A099557, A005251.
%K nonn,changed
%O 0,3
%A _N. J. A. Sloane_.
%E More terms and additional formulae from _Henry Bottomley_, Jul 21 2000
%E Plouffe's g.f. edited by R. J. Mathar, May 12 2008
|
