|
%I M0709 #174 Apr 14 2024 03:22:07
%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 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
%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 Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, <a href="https://arxiv.org/abs/2006.13002">From Unequal Chance to a Coin Game Dance: Variants of Penney's Game</a>, arXiv:2006.13002 [math.HO], 2020.
%H Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, <a href="https://doi.org/10.37236/9482">Permutations avoiding a simsun pattern</a>, The Electronic Journal of Combinatorics (2020) Vol. 27, Issue 3, P3.45.
%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 Christian Ennis, William Holland, Omer Mujawar, Aadit Narayanan, Frank Neubrander, Marie Neubrander, and Christina Simino, <a href="https://arxiv.org/abs/2107.01029">Words in Random Binary Sequences I</a>, arXiv:2107.01029 [math.GM], 2021.
%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="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 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 From _Paul D. Hanna_, Oct 22 2004: (Start)
%F G.f.: x/(1-2*x+x^2-x^3).
%F a(n) = Sum_{k=0..[(2n-1)/3]} binomial(n-1-[k/2], k), where [x]=floor(x). (End)
%F a(n) = Sum_{k=0..n} binomial(n-k, 2*k+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. (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.
%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_{k=0..floor((n-1)/3)} binomial(n-k, 2*k+1). - _Richard L. Ollerton_, 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_{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
%F 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
%F a(n+2) = n + 2 + Sum_{k=0..n} (n-k)*a(k). - _Greg Dresden_ and _Yichen P. Wang_, Sep 16 2021
%F 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
%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)
%p A005314 := proc(n)
%p option remember ;
%p if n <=2 then
%p n;
%p else
%p 2*procname(n-1)-procname(n-2)+procname(n-3) ;
%p end if;
%p end proc:
%p seq(A005314(n),n=0..20) ; # _R. J. Mathar_, Feb 25 2024
%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
%o (SageMath)
%o def A005314(n): return sum( binomial(n-k, 2*k+1) for k in range(floor((n+2)/3)) )
%o [A005314(n) for n in range(51)] # _G. C. Greubel_, Nov 10 2023
%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,changed
%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
|
