OFFSET
1,1
COMMENTS
a(n) is also the number of induced subgraphs with odd number of edges in the path graph P(n) if n>0. - Alessandro Cosentino (cosenal(AT)gmail.com), Feb 06 2009
A common recurrence of the bisections A020522 and A006516 means a(n+4) = 6*a(n+2) - 8*a(n), n>1. - Yosu Yurramendi, Aug 07 2008
Also, the decimal representation of the diagonal from the origin to the corner of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 566", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. - Robert Price, Jul 05 2017
REFERENCES
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 1..1000
M. Archibald, A. Blecher, A. Knopfmacher, M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
C. G. Bower, Transforms (2)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1022
S. J. Cyvin et al., Theory of polypentagons, J. Chem. Inf. Comput. Sci., 33 (1993), 466-474.
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Wolfram Research, Wolfram Atlas of Simple Programs
Index entries for linear recurrences with constant coefficients, signature (2,2,-4).
FORMULA
"BHK" (reversible, identity, unlabeled) transform of 2, 0, 0, 0, ...
a(n) = 2^(n-1)-2^floor((n-1)/2), n > 1. - Vladeta Jovovic, Nov 11 2001
G.f.: 2*x+x^2/((1-2*x)*(1-2*x^2)). - Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 25 2004
a(n+1) = A077957(n) + 2*a(n), n>1. a(n+2) = A000079(n+1) + 2*a(n), n>1. - Yosu Yurramendi, Aug 10 2008
a(n) = 2*(a(n-1) bitwiseOR a(n-2)), n>3. - Pierre Charland, Dec 12 2010
a(n) = 2*a(n-1) + 2*a(n-2) - 4*a(n-3). - Wesley Ivan Hurt, Jul 03 2020
MATHEMATICA
Join[{2}, LinearRecurrence[{2, 2, -4}, {1, 2, 6}, 29]] (* Jean-François Alcover, Oct 11 2017 *)
PROG
(Magma) [2] cat [2^(n-1)-2^Floor((n-1)/2) : n in [2..40]]; // Wesley Ivan Hurt, Jul 03 2020
(PARI) a(n)=([0, 1, 0; 0, 0, 1; -4, 2, 2]^(n-1)*[2; 1; 2])[1, 1] \\ Charles R Greathouse IV, Oct 21 2022
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved