%I #61 Oct 02 2024 06:48:50
%S 4,6,24,120,480,2016,8064,32640,130560,523776,2095104,8386560,
%T 33546240,134209536,536838144,2147450880,8589803520,34359607296,
%U 137438429184,549755289600,2199021158400,8796090925056,35184363700224,140737479966720,562949919866880
%N Number of reversible strings with n beads of 4 colors. If more than 1 bead, not palindromic.
%C From _Petros Hadjicostas_, Jun 30 2018: (Start)
%C Using the formulae in C. G. Bower's web link below about transforms, it can be proved that, for k >= 2, the BHK[k] transform of sequence (c(n): n >= 1), which has g.f. C(x) = Sum_{n >= 1} c(n)*x^n, has generating function B_k(x) = (1/2)*(C(x)^k - C(x^2)^{k/2}) if k is even, and B_k(x) = C(x)*B_{k-1}(x) = (C(x)/2)*(C(x)^{k-1} - C(x^2)^{(k-1)/2}) if k is odd. For k=1, Bower assumes that the BHK[k=1] transform of (c(n): n >= 1) is itself, which means that the g.f. of the output sequence is C(x). (This assumption is not accepted by all mathematicians because a sequence of length 1 is not only reversible but palindromic as well.)
%C Since a(m) = BHK(c(n): n >= 1)(m) = Sum_{k=1..m} BHK[k](c(n): n >= 1)(m) for m = 1,2,3,..., it can be easily proved (using sums of infinite geometric series) that the g.f. of BHK(c(n): n >= 1) is A(x) = (C(x)^2 - C(x^2))/(2*(1-C(x))*(1-C(x^2))) + C(x). (The extra C(x) is due of course to the special assumption made for the BHK[k=1] transform.)
%C Here, BHK(c(n): n >= 1)(m) indicates the m-th element of the output sequence when the transform is BHK and the input sequence is (c(n): n >= 1). Similarly, BHK[k](c(n): n >= 1)(m) indicates the m-th element of the output sequence when the transform is BHK[k] (i.e., with k boxes) and the input sequence is (c(n): n >= 1).
%C For the current sequence, c(1) = 4, and c(n) = 0 for all n >= 2, and thus, C(x) = 4*x. Substituting into the above formula for A(x), and doing the algebra, we get A(x) = 2*x*(2-5*x-8*x^2+32*x^3) / ((1+2*x)*(1-2*x)*(1-4*x)), which is _R. J. Mathar_'s formula below.
%C (End)
%C The formula for a(n) for this sequence was Ralf Stephan's conjecture 72. It was solved by Elizabeth Wilmer (see Proposition 1 in one of the links below). She does not accept Bower's assertion that a string of length 1 is not palindromic. - _Petros Hadjicostas_, Jul 05 2018
%H Colin Barker, <a href="/A032087/b032087.txt">Table of n, a(n) for n = 1..1000</a>
%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0409509">Prove or disprove: 100 conjectures from the OEIS</a>, arXiv:math/0409509 [math.CO], 2004.
%H Elizabeth Wilmer, <a href="https://www.semanticscholar.org/paper/Notes-on-Stephan-s-Conjectures-72-73-and-74-WILMER/ef43415527853b97626528b100c778798dc3aad1">Notes on Stephan's conjectures 72, 73 and 74</a>
%H Elizabeth Wilmer, <a href="/A032087/a032087.pdf">Notes on Stephan's conjectures 72, 73 and 74</a> [cached copy]
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,4,-16).
%F "BHK" (reversible, identity, unlabeled) transform of 4, 0, 0, 0, ...
%F a(2*n+1) = 2^(4*n+1) - 2^(2*n+1), a(2*n) = 2^(4*n-1) - 2^(2*n) + 2^(2*n-1), a(1)=4.
%F a(n) = (A000302(n) - A056450(n))/2 for n > 1.
%F From _R. J. Mathar_, Mar 20 2009: (Start)
%F a(n) = 4*a(n-1) + 4*a(n-2) - 16*a(n-3) for n > 4.
%F G.f.: 2*x*(2-5*x-8*x^2+32*x^3)/((1-2*x)*(1+2*x)*(1-4*x)). (End)
%F From _Colin Barker_, Mar 08 2017: (Start)
%F a(n) = 2^(n-1) * (2^n-1) for n > 1 and even.
%F a(n) = 2^(2*n-1) - 2^n for n > 1 and odd. (End)
%F E.g.f.: (1/4)*( exp(-2*x) - 3*exp(2*x) + 2*exp(4*x) ) + 4*x. - _G. C. Greubel_, Oct 02 2024
%t Join[{4}, LinearRecurrence[{4, 4, -16}, {6, 24, 120}, 24]] (* _Jean-François Alcover_, Oct 11 2017 *)
%o (PARI) Vec(2*x*(2 - 5*x - 8*x^2 + 32*x^3) / ((1 - 2*x)*(1 + 2*x)*(1 - 4*x)) + O(x^30)) \\ _Colin Barker_, Mar 08 2017
%o (Magma)
%o A032087:= func< n | n eq 1 select 4 else 2^(2*n-1) -(3-(-1)^n)*2^(n-2) >;
%o [A032087(n): n in [1..30]]; // _G. C. Greubel_, Oct 02 2024
%o (SageMath)
%o def A032087(n): return 2^(2*n-1) -3*2^(n-2) +(-2)^(n-2) +4*int(n==1)
%o [A032087(n) for n in range(1,31)] # _G. C. Greubel_, Oct 02 2024
%Y Column 4 of A293500 for n>1.
%Y Cf. A000302, A026337 (bisection), A032121, A056450, A088037.
%K nonn,easy
%O 1,1
%A _Christian G. Bower_