login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005314 For n = 0, 1, 2, a(n) = n; thereafter, a(n) = 2*a(n-1) - a(n-2) + a(n-3).
(Formerly M0709)
24

%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 A109134; 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,...). - _Gary W. Adamson_, May 04 2009

%C a(n-2) is the top left entry of the n-th power of the 3X3 matrix [0, 1, 0; 0, 1, 1; 1, 0, 1] or of the 3X3 matrix [0, 0, 1; 1, 1, 0; 0, 1, 1]. - _R. J. Mathar_, Feb 03 2014

%C Counts closed walks of length (n+2) at a vertex of a unidirectional triangle containing a loop on remaining two vertices. - _David Neil McGrath_, Sep 15 2014

%C Also the number of binary words of length n that begin with 1 and avoid the subword 101. a(5) = 9: 10000, 10001, 10010, 10011, 11000, 11001, 11100, 11110, 11111. - _Alois P. Heinz_, Jul 21 2016

%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="https://cs.uwaterloo.ca/journals/JIS/VOL6/Heubach/heubach5.html">Integer Sequences Related to Compositions without 2's</a>, J. Integer Seqs., Vol. 6, 2003.

%H R. L. Graham and N. J. A. Sloane, <a href="http://dx.doi.org/10.1016/0024-3795(84)90090-9">Anti-Hadamard matrices</a>, Linear Alg. Applic., 62 (1984), 113-137.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=426">Encyclopedia of Combinatorial Structures 426</a>

%H L. A. Medina and A. Straub, <a href="http://emmy.uprrp.edu/lmedina/papers/logconcave/logconcavity.pdf">On multiple and infinite log-concavity</a>, 2013, preprint Annals of Combinatorics, March 2016, Volume 20, Issue 1, pp 125-138..

%H Denis Neiter and Amsha Proag, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Proag/proag3.html">Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 1992.

%H Bojan Vučković and Miodrag Živković, <a href="https://www.researchgate.net/publication/312219294">Row Space Cardinalities Above 2^(n - 2) + 2^(n - 3)</a>, ResearchGate, January 2017, p. 3.

%H <a href="/index/Rec#order_03">Index entries for 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. - _Don 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...floor((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 a(n) = Sum_{k=0..n} binomial( n-floor((k+1)/2), n-floor((3k-1)/2) ). - _John Molokach_, Jul 21 2013

%F a(n) = sum(binomial(n-floor((4n+15-6k+(-1)^k)/12), n-floor((4n+15-6k+(-1)^k)/12)-floor((2n-1)/3)+k-1),k,1,floor((2n+2)/3)). - _John Molokach_, Jul 24 2013

%F a(n) = round(A001608(2n+1)*r) where r is the real root of 23x^3-23x^2+8x-1=0, r = 0.4114955... - _Richard Turk_, Oct 24 2019

%e G.f. = x + 2*x^2 + 3*x^3 + 5*x^4 + 9*x^5 + 16*x^6 + 28*x^7 + 49*x^8 + ...

%e From _Gus Wiseman_, Nov 25 2019: (Start)

%e a(n) is the number of subsets of {1..n} containing n such that if x and x + 2 are both in the subset, then so is x + 1. For example, the a(1) = 1 through a(5) = 9 subsets are:

%e {1} {2} {3} {4} {5}

%e {1,2} {2,3} {1,4} {1,5}

%e {1,2,3} {3,4} {2,5}

%e {2,3,4} {4,5}

%e {1,2,3,4} {1,2,5}

%e {1,4,5}

%e {3,4,5}

%e {2,3,4,5}

%e {1,2,3,4,5}

%e (End)

%t LinearRecurrence[{2, -1, 1}, {0, 1, 2}, 100] (* _Vladimir Joseph Stephan Orlovsky_, Jul 03 2011 *)

%t Table[Sum[Binomial[n - Floor[(k + 1)/2], n - Floor[(3 k - 1)/2]], {k, 0, n}], {n, 0, 100}] (* _John Molokach_, Jul 21 2013 *)

%t Table[Sum[Binomial[n - Floor[(4 n + 15 - 6 k + (-1)^k)/12], n - Floor[(4 n + 15 - 6 k + (-1)^k)/12] - Floor[(2 n - 1)/3] + k - 1], {k, 1, Floor[(2 n + 2)/3]}], {n, 0, 100}] (* _John Molokach_, Jul 25 2013 *)

%t a[ n_] := If[ n < 0, SeriesCoefficient[ x^2 / (1 - x + 2 x^2 - x^3), {x, 0, -n}], SeriesCoefficient[ x / (1 - 2 x + x^2 - x^3), {x, 0, n}]]; (* _Michael Somos_, Dec 13 2013 *)

%t RecurrenceTable[{a[0]==0,a[1]==1,a[2]==2,a[n]==2a[n-1]-a[n-2]+a[n-3]},a,{n,40}] (* _Harvey P. Dale_, May 13 2018 *)

%t Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&!MatchQ[#,{___,x_,y_,___}/;x+2==y]&]],{n,0,10}] (* _Gus Wiseman_, Nov 25 2019 *)

%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 */

%o (MAGMA) [0] cat [n le 3 select n else 2*Self(n-1) - Self(n-2) + Self(n-3):n in [1..35]]; // _Marius A. Burtea_, Oct 24 2019

%o (MAGMA) R<x>:=PowerSeriesRing(Integers(), 36); [0] cat Coefficients(R!( x/(1-2*x+x^2-x^3))); // _Marius A. Burtea_, Oct 24 2019

%Y Equals row sums of triangle A099557.

%Y Equals row sums of triangle A224838.

%Y Cf. A011973 (starting with offset 1 = Falling diagonal sums of triangle with rows displayed as centered text).

%Y First differences of A005251, shifted twice to the left.

%Y Cf. A003242, A114901, A261041, A274174.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_

%E More terms and additional formulas from _Henry Bottomley_, Jul 21 2000

%E Plouffe's g.f. edited by _R. J. Mathar_, May 12 2008

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 5 21:42 EDT 2020. Contains 333260 sequences. (Running on oeis4.)