login
This site is supported by donations to The OEIS 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)
23
0, 1, 2, 3, 5, 9, 16, 28, 49, 86, 151, 265, 465, 816, 1432, 2513, 4410, 7739, 13581, 23833, 41824, 73396, 128801, 226030, 396655, 696081, 1221537, 2143648, 3761840, 6601569, 11584946, 20330163, 35676949, 62608681, 109870576, 192809420, 338356945, 593775046 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Number of compositions of n into parts congruent to {1,2} mod 4. - Vladeta Jovovic, Mar 10 2005

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

Starting with offset 1 = INVERT transform of (1, 1, 0, 0, 1, 1, 0, 0,...). - Gary W. Adamson, May 04 2009

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

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

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

REFERENCES

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

P. Chinn and S. Heubach, Integer Sequences Related to Compositions without 2's, J. Integer Seqs., Vol. 6, 2003.

R. L. Graham and N. J. A. Sloane, Anti-Hadamard matrices, Linear Alg. Applic., 62 (1984), 113-137.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 426

L. A. Medina and A. Straub, On multiple and infinite log-concavity, 2013, preprint Annals of Combinatorics, March 2016, Volume 20, Issue 1, pp 125-138..

Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Index entries for linear recurrences with constant coefficients, signature (2,-1,1)

FORMULA

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

a(n) = Sum [k=0..n, C(n-k, 2k+1) ].

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

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.

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

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

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

a(n) = A000931(2*n + 4). - Michael Somos, Sep 18 2012

a(n) = A077954(-n - 2). - Michael Somos, Sep 18 2012

G.f.: 1/( 1 - sum(k>=0, x*(x-x^2+x^3)^k ) ) - 1. - Joerg Arndt, Sep 30 2012

a(n)= sum_{k=0..n} binomial( n-floor((k+1)/2), n-floor((3k-1)/2) ). - John Molokach, Jul 21 2013

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

EXAMPLE

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

MATHEMATICA

LinearRecurrence[{2, -1, 1}, {0, 1, 2}, 100] (* Vladimir Joseph Stephan Orlovsky, Jul 03 2011 *)

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

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

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

PROG

(PARI) {a(n) = sum(k=0, (2*n-1)\3, binomial(n-1-k\2, k))}

(Haskell)

a005314 n = a005314_list !! n

a005314_list = 0 : 1 : 2 : zipWith (+) a005314_list

   (tail $ zipWith (-) (map (2 *) $ tail a005314_list) a005314_list)

-- Reinhard Zumkeller, Oct 14 2011

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

CROSSREFS

Equals row sums of triangle A099557.

Equals row sums of triangle A224838.

Cf. A005251.

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

Sequence in context: A134009 A018160 A079960 * A099529 A088352 A002572

Adjacent sequences:  A005311 A005312 A005313 * A005315 A005316 A005317

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms and additional formulas from Henry Bottomley, Jul 21 2000

Plouffe's g.f. edited by R. J. Mathar, May 12 2008

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified June 28 09:49 EDT 2017. Contains 288813 sequences.