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 3 X 3 matrix [0, 1, 0; 0, 1, 1; 1, 0, 1] or of the 3 X 3 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
Also the number of binary words of length n-1 such that every two consecutive 0s are immediately followed by at least two consecutive 1s. a(4) = 5: 010, 011, 101, 110, 111. - Jerrold Grossman, May 03 2024
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
Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, From Unequal Chance to a Coin Game Dance: Variants of Penney's Game, arXiv:2006.13002 [math.HO], 2020.
Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, Permutations avoiding a simsun pattern, The Electronic Journal of Combinatorics (2020) Vol. 27, Issue 3, P3.45.
P. Chinn and S. Heubach, Integer Sequences Related to Compositions without 2's, J. Integer Seqs., Vol. 6, 2003.
Christian Ennis, William Holland, Omer Mujawar, Aadit Narayanan, Frank Neubrander, Marie Neubrander, and Christina Simino, Words in Random Binary Sequences I, arXiv:2107.01029 [math.GM], 2021.
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; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Bojan Vučković and Miodrag Živković, Row Space Cardinalities Above 2^(n - 2) + 2^(n - 3), ResearchGate, January 2017, p. 3.
Index entries for linear recurrences with constant coefficients, signature (2,-1,1).
FORMULA
From Paul D. Hanna, Oct 22 2004: (Start)
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). (End)
a(n) = Sum_{k=0..n} binomial(n-k, 2*k+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. (1-z)*(1+z^2)/(1-2*z+z^2-z^3) 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_{k=0..floor((n-1)/3)} binomial(n-k, 2*k+1). - Richard L. Ollerton, 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_{k=1..floor((2n+2)/3)} (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). - John Molokach, Jul 24 2013
a(n) = round(A001608(2n+1)*r) where r is the real root of 23*x^3 - 23*x^2 + 8*x - 1 = 0, r = 0.4114955... - Richard Turk, Oct 24 2019
a(n+2) = n + 2 + Sum_{k=0..n} (n-k)*a(k). - Greg Dresden and Yichen P. Wang, Sep 16 2021
a(n) ~ (19 - r + 11*r^2) / (23 * r^(n-1)), where r = 0.569840290998... is the root of the equation r*(2 - r + r^2) = 1. - Vaclav Kotesovec, Apr 14 2024
a(n) = n*3F2(1/3-n/3,2/3-n/3,1-n/3;-n,3/2;27/4). - R. J. Mathar, Jun 27 2024
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 + ...
From Gus Wiseman, Nov 25 2019: (Start)
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:
{1} {2} {3} {4} {5}
{1,2} {2,3} {1,4} {1,5}
{1,2,3} {3,4} {2,5}
{2,3,4} {4,5}
{1,2,3,4} {1,2,5}
{1,4,5}
{3,4,5}
{2,3,4,5}
{1,2,3,4,5}
(End)
MAPLE
A005314 := proc(n)
option remember ;
if n <=2 then
n;
else
2*procname(n-1)-procname(n-2)+procname(n-3) ;
end if;
end proc:
seq(A005314(n), n=0..20) ; # R. J. Mathar, Feb 25 2024
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 *)
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 *)
Table[Length[Select[Subsets[Range[n]], MemberQ[#, n]&&!MatchQ[#, {___, x_, y_, ___}/; x+2==y]&]], {n, 0, 10}] (* Gus Wiseman, Nov 25 2019 *)
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 */
(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
(Magma) R<x>:=PowerSeriesRing(Integers(), 36); [0] cat Coefficients(R!( x/(1-2*x+x^2-x^3))); // Marius A. Burtea, Oct 24 2019
(SageMath)
def A005314(n): return sum( binomial(n-k, 2*k+1) for k in range(floor((n+2)/3)) )
[A005314(n) for n in range(51)] # G. C. Greubel, Nov 10 2023
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
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