|
|
A005252
|
|
a(n) = Sum_{k=0..floor(n/4)} binomial(n-2k,2k).
(Formerly M1048)
|
|
17
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
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) = 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
|
|
REFERENCES
|
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).
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.
|
|
LINKS
|
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]
|
|
FORMULA
|
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.
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
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
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
|
|
MAPLE
|
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
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(Haskell)
a005252 n = sum $ map (\x -> a007318 (n - x) x) [0, 2 .. 2 * div n 4]
(PARI) Vec((1-x)/((1-x-x^2)*(1-x+x^2)) + O(x^100)) \\ Altug Alkan, Jan 08 2015
(PARI) a(n) = fibonacci(n+1)>>1 + (n%6<2); \\ Kevin Ryde, Apr 29 2021
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Definition revised at the suggestion of Alessandro Orlandi by N. J. A. Sloane, Aug 16 2009
|
|
STATUS
|
approved
|
|
|
|