A111734 -id:A111734 - cp's OEIS frontend

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

1, 1, 1, 1, 2, 4, 7, 11, 17, 27, 44, 72, 117, 189, 305, 493, 798, 1292, 2091, 3383, 5473, 8855, 14328, 23184, 37513, 60697, 98209, 158905, 257114, 416020, 673135, 1089155, 1762289, 2851443, 4613732, 7465176, 12078909, 19544085, 31622993

Offset: 0

N. J. A. Sloane

The Twopins/t sequence (see Guy).
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
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
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
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
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
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
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

John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 205 of first edition.
R. K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15.
David J. C. MacKay, Information Theory, Inference and Learning Algorithms, CUP, 2003, p. 251.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Ian Stewart, Galois theory, CRC Press, Boca Raton, FL, 2015, p. 32.
E. L. Tan, On the cycle graph of a graph and inverse cycle graphs, Ph.D. Dissertation, Univ. of Philippines, Diliman, Quezon City, 1987.
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.

T. D. Noe, Table of n, a(n) for n = 0..500
R. Austin and R. K. Guy, Binary sequences without isolated ones, Fib. Quart., 16 (1978), 84-86.
R. K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,2,2).
V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
V. E. Hoggatt, Jr. and M. Bicknell, Diagonal sums of generalized Pascal triangles, Fib. Quart., 7 (1969), 341-358, 393.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 424
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3
S. Klavzar, Structure of Fibonacci cubes: a survey, J. Comb. Optim. 25 (2013), 505-522, DOI:10.1007/s10878-011-9433-z.
E. Munarini and N. Z. Salvi, Structural and enumerative properties of the Fibonacci cubes, Discrete Math., 255, 2002, 317-324.
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
E. L. Tan, Letter to N. J. A. Sloane, Feb 1992
OEIS Wiki, Autosequence.
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,1).

First differences of A024490.
Cf. A005251, A005676, A007318, A010892.
Cf. A106511, A111734, A173021.

a005252 n = sum $ map (\x -> a007318 (n - x) x) [0, 2 .. 2 * div n 4]
-- Reinhard Zumkeller, Jul 05 2013

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

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

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

Vec((1-x)/((1-x-x^2)*(1-x+x^2)) + O(x^100)) \\ Altug Alkan, Jan 08 2015

a(n) = fibonacci(n+1)>>1 + (n%6<2); \\ Kevin Ryde, Apr 29 2021

Second differences give sequence shifted twice. - E. L. Tan, Univ. Phillipines.
G.f.: (1-x)/((1-x-x^2)*(1-x+x^2)). Simon Plouffe in his 1992 dissertation.
From Paul Barry, Mar 15 2004: (Start)
a(n) = Fibonacci(n+1)/2 + A010892(n)/2;
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)
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
a(n) = A173021(2^(n-1) - 1) for n > 0. - Reinhard Zumkeller, Feb 07 2010
Limit_{n->oo} a(n)/a(n+1) = (sqrt(5) - 1)/2. - Sergei N. Gladkovskii, Jan 05 2014
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
a(n) = Fibonacci(n+1) + (-1)^(n+1)*A106511(n+2). - Katharine Ahrens, May 05 2019
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

More terms from (and formula corrected by) James Sellers, Feb 06 2000

Definition revised at the suggestion of Alessandro Orlandi by N. J. A. Sloane, Aug 16 2009

A007039 Number of cyclic binary n-bit strings with no alternating substring of length > 2.

Original entry on oeis.org

2, 2, 2, 6, 12, 20, 30, 46, 74, 122, 200, 324, 522, 842, 1362, 2206, 3572, 5780, 9350, 15126, 24474, 39602, 64080, 103684, 167762, 271442, 439202, 710646, 1149852, 1860500, 3010350, 4870846, 7881194, 12752042, 20633240, 33385284, 54018522, 87403802, 141422322

Offset: 1

N. J. A. Sloane

John W. Layman observes that the second differences give the sequence shifted to the right.

			G.f. = 2*x + 2*x^2 + 2*x^3 + 6*x^4 + 12*x^5 + 20*x^6 + 30*x^7 + 46*x^8 + ...

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1000
Z. Agur, A. S. Fraenkel, and S. T. Klein, The number of fixed points of the majority rule, Discr. Math., 70 (1988), 295-302.
Matthew Macauley, Jon McCammond, and Henning S. Mortveit, Dynamics groups of asynchronous cellular automata, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35.
A. McLeod and W. O. J. Moser, Counting cyclic binary strings, Math. Mag., 80 (No. 1, 2007), 29-37.
W. O. J. Moser, On cyclic binary n-bit strings, Report from the Department of Mathematics and Statistics, McGill University, 1991. (Annotated scanned copy)
W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31 (1993), no. 1, 2-6.
E. Munarini and N. Z. Salvi, Circular Binary Strings without Zigzags, Integers: Electronic Journal of Combinatorial Number Theory 3 (2003), #A19. See relation (8) on page 5.
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,1).

Cf. A000032, A007040, A057079, A111734.

CoefficientList[Series[2*(1+x)*(1-2*x+2*x^2)/((1-x+x^2)*(1-x-x^2)),{x,0,40}],x] (* Vincenzo Librandi, Apr 16 2012 *)
a[n_ /; n<4] = 2; a[4] = 6; a[n_] := a[n] = 2*a[n-1] - a[n-2] + a[n-4]; Array[a, 39] (* Jean-François Alcover, Oct 08 2017 *)

Vec(2*x*(1-x+2*x^3)/((1-x-x^2)*(1-x+x^2))+O(x^66)) \\ Joerg Arndt, Oct 27 2015

For n >= 5, a(n) = 2a(n-1) - a(n-2) + a(n-4). - David W. Wilson
G.f.: 2*x*(1+x)*(1-2*x+2*x^2)/((1-x+x^2)*(1-x-x^2)). - Colin Barker, Mar 28 2012
a(n) = A000032(n) + A057079(n + 1). - John M. Campbell, Dec 29 2016
a(n) = abs(A111734(n)). - Alois P. Heinz, Oct 08 2017
E.g.f.: 2*exp(x/2)*(cos(sqrt(3)*x/2) + cosh(sqrt(5)*x/2)) - 4. - Stefano Spezia, Mar 09 2025

A226956 a(0)=a(1)=1, a(n+2) = a(n+1) + a(n) - A128834(n).

Original entry on oeis.org

1, 1, 2, 2, 3, 5, 9, 15, 24, 38, 61, 99, 161, 261, 422, 682, 1103, 1785, 2889, 4675, 7564, 12238, 19801, 32039, 51841, 83881, 135722, 219602, 355323, 574925, 930249, 1505175, 2435424, 3940598, 6376021, 10316619, 16692641, 27009261, 43701902, 70711162, 114413063, 185124225, 299537289

Offset: 0

Paul Curtz, Jun 24 2013

a(n) and differences:
    1,  1, 2, 2, 3, 5, 9, 15, 24, 38, ...             a(n)
    0,  1, 0, 1, 2, 4, 6,  9, 14, 23, 38, ...         b(n)
    1, -1, 1, 1, 2, 2, 3,  5,  9, 15, 24, 38, ...     a(n-2)
   -2,  2, 0, 1, 0, 1, 2,  4,  6,  9, 14, 23, 38, ... b(n-2)
    4, -2, 1,-1, 1, 1, 2,  2,  3,  5,  9, ...         a(n-4)
   -6,  3,-2, 2, 0, 1, 0,  1,  2,  4,  6,  9, ...     b(n-4)
    9, -5, 4,-2, 1,-1, 1,  1,  2,  2,  3,  5, 9, ...  a(n-6)
  -14,  9,-6, 3,-2, 2, 0,  1   0,  1,  2, ...         b(n-6)
   23,-15, 9,-5, 4,-2, 1, -1,  1,  1,  2,  2, ...     a(n-8)
a(n)-b(n+1) = period 6: repeat 0, 1, 1, 0, -1, -1 = A128834(n).
Diagonals with the same number give 1, 2, 9, 38, ... = A001077(n).
Second column: the (n+2)-th term is identical to a(n+1) signed.
a(n+1) is identical to its twice shifted inverse binomial transform signed.
a(n+1)/a(n) tends to A001622 (the golden ratio) as n -> infinity.

			a(0) = a(1) = 1.
a(2) = a(3) = 2.
a(4) = 2*a(3) - a(2) + a(0) = 4-2+1 = 3.
a(5) = 6-2+1 = 5.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,1)

Cf. Diagonals in A024490.

I:=[1, 1, 2, 2]; [n le 4 select I[n] else 2*Self(n-1) - Self(n-2) + Self(n-4): n in [1..30]]; // G. C. Greubel, Jan 15 2018

a[n_] := (LucasL[n] + {0, 1, 1, 0, -1, -1}[[Mod[n, 6] + 1]])/2; Table[a[n], {n, 0, 42}] (* Jean-François Alcover, Jun 28 2013, after R. J. Mathar *)
LinearRecurrence[{2,-1,0,1}, {1,1,2,2}, 30] (* G. C. Greubel, Jan 15 2018 *)

x='x+O('x^30); Vec((x-1)*(1+x^2)/((x^2+x-1)*(x^2-x+1))) \\ G. C. Greubel, Jan 15 2018

a(n+6) - a(n-6) = 20*A000045(n).
a(n) = 2*a(n-1) - a(n-2) + a(n-4).
a(n) = 3*a(n-3) + 5*a(n-6) + a(n-9) (plus many similar by telescoping the fundamental recurrence).
a(n+3) - a(n-3) = 2*A000032(n).
G.f.: (x-1)*(1+x^2) / ( (x^2+x-1)*(x^2-x+1) ). - R. J. Mathar, Jun 26 2013
2*a(n) = A000032(n) + A010892(n-1). - R. J. Mathar, Jun 26 2013
a(n+5) = a(n+4) + a(n+2) + A108014(n).
a(2n+1) + A226447(2n+2) = 2*A182895(n).
a(n) - a(n-2) = 0,2,1,1,1,3,6,... = abs(A111734(n-2)).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A007039 Number of cyclic binary n-bit strings with no alternating substring of length > 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A226956 a(0)=a(1)=1, a(n+2) = a(n+1) + a(n) - A128834(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula