|
%I #60 Oct 21 2022 22:12:38
%S 2,1,2,6,12,28,56,120,240,496,992,2016,4032,8128,16256,32640,65280,
%T 130816,261632,523776,1047552,2096128,4192256,8386560,16773120,
%U 33550336,67100672,134209536,268419072,536854528
%N Number of reversible strings with n beads of 2 colors. If more than 1 bead, not palindromic.
%C 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
%C 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
%C 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
%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.
%H Vincenzo Librandi, <a href="/A032085/b032085.txt">Table of n, a(n) for n = 1..1000</a>
%H M. Archibald, A. Blecher, A. Knopfmacher, M. E. Mays, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Archibald/arch3.html">Inversions and Parity in Compositions of Integers</a>, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1022">Encyclopedia of Combinatorial Structures 1022</a>
%H S. J. Cyvin et al., <a href="http://dx.doi.org/10.1021/ci00013a027">Theory of polypentagons</a>, J. Chem. Inf. Comput. Sci., 33 (1993), 466-474.
%H N. J. A. Sloane, <a href="http://arxiv.org/abs/1503.01168">On the Number of ON Cells in Cellular Automata</a>, arXiv:1503.01168 [math.CO], 2015.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ElementaryCellularAutomaton.html">Elementary Cellular Automaton</a>
%H S. Wolfram, <a href="http://wolframscience.com/">A New Kind of Science</a>
%H Wolfram Research, <a href="http://atlas.wolfram.com/">Wolfram Atlas of Simple Programs</a>
%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%H <a href="https://oeis.org/wiki/Index_to_2D_5-Neighbor_Cellular_Automata">Index to 2D 5-Neighbor Cellular Automata</a>
%H <a href="https://oeis.org/wiki/Index_to_Elementary_Cellular_Automata">Index to Elementary Cellular Automata</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,2,-4).
%F "BHK" (reversible, identity, unlabeled) transform of 2, 0, 0, 0, ...
%F a(n) = 2^(n-1)-2^floor((n-1)/2), n > 1. - _Vladeta Jovovic_, Nov 11 2001
%F G.f.: 2*x+x^2/((1-2*x)*(1-2*x^2)). - Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Mar 25 2004
%F a(n) = A005418(n+1)-A016116(n+2), n>1. - _Yosu Yurramendi_, Aug 07 2008
%F 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
%F First differences: a(n+1)-a(n) = A007179(n) = A156232(n+2)/4, n>1. - _Paul Curtz_, Nov 16 2009
%F a(n) = 2*(a(n-1) bitwiseOR a(n-2)), n>3. - _Pierre Charland_, Dec 12 2010
%F a(n) = 2*a(n-1) + 2*a(n-2) - 4*a(n-3). - _Wesley Ivan Hurt_, Jul 03 2020
%t Join[{2}, LinearRecurrence[{2, 2, -4}, {1, 2, 6}, 29]] (* _Jean-François Alcover_, Oct 11 2017 *)
%o (Magma) [2] cat [2^(n-1)-2^Floor((n-1)/2) : n in [2..40]]; // _Wesley Ivan Hurt_, Jul 03 2020
%o (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
%Y Cf. A005418, A016116. Essentially the same as A122746.
%Y Row sums of triangle A034877.
%Y Cf. A289404, A289405, A052551.
%K nonn,easy
%O 1,1
%A _Christian G. Bower_
|
