cp's OEIS Frontend

A005252 a(n) = Sum_{k=0..floor(n/4)} binomial(n-2k,2k).

%I A005252 M1048 #177 Jul 02 2025 16:01:54
%S A005252 1,1,1,1,2,4,7,11,17,27,44,72,117,189,305,493,798,1292,2091,3383,5473,
%T A005252 8855,14328,23184,37513,60697,98209,158905,257114,416020,673135,
%U A005252 1089155,1762289,2851443,4613732,7465176,12078909,19544085,31622993
%N A005252 a(n) = Sum_{k=0..floor(n/4)} binomial(n-2k,2k).
%C A005252 The Twopins/t sequence (see Guy).
%C A005252 Number of closed walks of length n at a vertex of the graph with adjacency matrix [1,1,0,0;0,0,0,1;1,0,0,0;0,0,1,1]. - _Paul Barry_, Mar 15 2004
%C A005252 a(n+3) = number of n-bit sequences that avoid both 010 and 0110. Example: for n=3, there are 8 3-bit sequences and only 010 fails to qualify, so a(6)=7. - _David Callan_, Mar 25 2004
%C A005252 a(n) is the number of length n binary words that have an even number of 0's and every 0 is immediately followed by a 1. a(6) = 7 because we have: 010111, 011011, 011101, 101011, 101101, 110101, 111111. - _Geoffrey Critzer_, Jan 08 2014
%C A005252 a(n) is the number of vertices of the Fibonacci cube Gamma(n-1) having an even number of ones. The Fibonacci cube Gamma(n) can be defined as the graph whose vertices are the binary strings of length n without two consecutive 1's and in which two vertices are adjacent when their Hamming distance is exactly 1. Example: a(4) = 2; indeed, the Fibonacci cube Gamma(3) has the five vertices 000, 010, 001, 100, 101, two of which have an even number of ones. See the E. Munarini et al. reference, p. 323. - _Emeric Deutsch_, Jun 28 2015
%C A005252 a(n) is the number of even permutations p of 1,2,...,n such that |p(i)-i| <= 1 for i=1,2,...,n. - _Dmitry Efimov_, Jan 08 2016
%C A005252 This sequence (prefixed with 0) is an autosequence of the first kind, whose second kind companion is (2 followed by abs(A111734)). - _Jean-François Alcover_, Oct 30 2017
%C A005252 a(n+1) is the number of n-bit sequences such that 1's appear in groups of three or more. Example: for n = 5, a(6) = 7 because we have 00000, 00111, 01110, 11100, 11110, 01111, 11111. Source: exercise 1.11 in I. Stewart. - _João Camarneiro_, Dec 23 2024
%D A005252 John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 205 of first edition.
%D A005252 R. K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15.
%D A005252 David J. C. MacKay, Information Theory, Inference and Learning Algorithms, CUP, 2003, p. 251.
%D A005252 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A005252 Ian Stewart, Galois theory, CRC Press, Boca Raton, FL, 2015, p. 32.
%D A005252 E. L. Tan, On the cycle graph of a graph and inverse cycle graphs, Ph.D. Dissertation, Univ. of Philippines, Diliman, Quezon City, 1987.
%D A005252 E. L. Tan, On Fibonacci numbers and cycle graphs, Matimyas Matemaka (Published by the Mathematical Society of the Philippines), 13 (No. 2, 1990), 1-4.
%H A005252 T. D. Noe, <a href="/A005252/b005252.txt">Table of n, a(n) for n = 0..500</a>
%H A005252 R. Austin and R. K. Guy, <a href="https://www.fq.math.ca/Scanned/16-1/austin.pdf">Binary sequences without isolated ones</a>, Fib. Quart., 16 (1978), 84-86.
%H A005252 R. K. Guy, <a href="/A005251/a005251_1.pdf">Anyone for Twopins?</a>, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]
%H A005252 V. C. Harris and C. C. Styles, <a href="https://www.fq.math.ca/Scanned/2-4/harris.pdf">A generalization of Fibonacci numbers</a>, Fib. Quart. 2 (1964) 277-289, sequence u(n,2,2).
%H A005252 V. E. Hoggatt, Jr., <a href="/A005676/a005676.pdf">7-page typed letter to N. J. A. Sloane with suggestions for new sequences</a>, circa 1977.
%H A005252 V. E. Hoggatt, Jr. and M. Bicknell, <a href="https://www.fq.math.ca/Scanned/7-4/hoggatt-a.pdf">Diagonal sums of generalized Pascal triangles</a>, Fib. Quart., 7 (1969), 341-358, 393.
%H A005252 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=424">Encyclopedia of Combinatorial Structures 424</a>
%H A005252 Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Janjic/janjic73.html">Binomial Coefficients and Enumeration of Restricted Words</a>, Journal of Integer Sequences, 2016, Vol 19, #16.7.3
%H A005252 S. Klavzar, <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/FibonacciCubesRevised.pdf">Structure of Fibonacci cubes: a survey</a>, J. Comb. Optim. 25 (2013), 505-522, DOI:<a href="https://doi.org/10.1007/s10878-011-9433-z">10.1007/s10878-011-9433-z</a>.
%H A005252 E. Munarini and N. Z. Salvi, <a href="https://doi.org/10.1016/S0012-365X(01)00407-1">Structural and enumerative properties of the Fibonacci cubes</a>, Discrete Math., 255, 2002, 317-324.
%H A005252 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 A005252 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A005252 E. L. Tan, <a href="/A005252/a005252.pdf">Letter to N. J. A. Sloane, Feb 1992</a>
%H A005252 OEIS Wiki, <a href="https://oeis.org/wiki/Autosequence">Autosequence</a>.
%H A005252 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,0,1).
%F A005252 Second differences give sequence shifted twice. - E. L. Tan, Univ. Phillipines.
%F A005252 G.f.: (1-x)/((1-x-x^2)*(1-x+x^2)). _Simon Plouffe_ in his 1992 dissertation.
%F A005252 From _Paul Barry_, Mar 15 2004: (Start)
%F A005252 a(n) = Fibonacci(n+1)/2 + A010892(n)/2;
%F A005252 a(n) = (((1+sqrt(5))/2)^(n+1)/sqrt(5) - ((1-sqrt(5))/2)^(n+1)/sqrt(5) + cos(Pi*n/3) + sin(Pi*n/3)/sqrt(3))/2. (End)
%F A005252 a(n) = 2*a(n-1) - a(n-2) + a(n-4); a(0) = a(1) = a(2) = a(3) = 1. - _Philippe Deléham_, May 01 2006
%F A005252 a(n) = A173021(2^(n-1) - 1) for n > 0. - _Reinhard Zumkeller_, Feb 07 2010
%F A005252 Limit_{n->oo} a(n)/a(n+1) = (sqrt(5) - 1)/2. - _Sergei N. Gladkovskii_, Jan 05 2014
%F A005252 G.f.: (1 + Q(0)*x^4/2)/(1-x), where Q(k) = 1 + 1/(1 - x*( 4*k + 2 - x + x^3)/( x*( 4*k + 4 - x + x^3) + 1/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jan 07 2014
%F A005252 a(n) = Fibonacci(n+1) + (-1)^(n+1)*A106511(n+2). - _Katharine Ahrens_, May 05 2019
%F A005252 E.g.f.: exp(x/2)*(15*(cos(sqrt(3)*x/2) + cosh(sqrt(5)*x/2)) + 5*sqrt(3)*sin(sqrt(3)*x/2) + 3*sqrt(5)*sinh(sqrt(5)*x/2))/30. - _Stefano Spezia_, Aug 03 2022
%p A005252 ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,X))), X = Sequence(b,card >= 2)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=2..40); # _Zerinvary Lajos_, Mar 26 2008
%t A005252 Table[Sum[Binomial[n-2k,2k],{k,0,Floor[n/4]}],{n,0,50}] (* or *) LinearRecurrence[{2,-1,0,1},{1,1,1,1},50] (* _Harvey P. Dale_, Dec 09 2011 *)
%t A005252 Table[HypergeometricPFQ[{1/4-n/4, 1/2-n/4, 3/4-n/4, -n/4}, {1/2, 1/2-n/2, -n/2}, 16], {n, 0, 38}] (* _Jean-François Alcover_, Oct 04 2012 *)
%o A005252 (Haskell)
%o A005252 a005252 n = sum $ map (\x -> a007318 (n - x) x) [0, 2 .. 2 * div n 4]
%o A005252 -- _Reinhard Zumkeller_, Jul 05 2013
%o A005252 (PARI) Vec((1-x)/((1-x-x^2)*(1-x+x^2)) + O(x^100)) \\ _Altug Alkan_, Jan 08 2015
%o A005252 (PARI) a(n) = fibonacci(n+1)>>1 + (n%6<2); \\ _Kevin Ryde_, Apr 29 2021
%o A005252 (Magma) I:=[1,1,1,1]; [n le 4 select I[n] else 2*Self(n-1)-Self(n-2)+Self(n-4): n in [1..50]]; // _Vincenzo Librandi_, Jan 09 2016
%Y A005252 First differences of A024490.
%Y A005252 Cf. A005251, A005676, A007318, A010892.
%Y A005252 Cf. A106511, A111734, A173021.
%K A005252 nonn,easy,nice
%O A005252 0,5
%A A005252 _N. J. A. Sloane_
%E A005252 More terms from (and formula corrected by) _James Sellers_, Feb 06 2000
%E A005252 Definition revised at the suggestion of Alessandro Orlandi by _N. J. A. Sloane_, Aug 16 2009