

A032087


Number of reversible strings with n beads of 4 colors. If more than 1 bead, not palindromic.


5



4, 6, 24, 120, 480, 2016, 8064, 32640, 130560, 523776, 2095104, 8386560, 33546240, 134209536, 536838144, 2147450880, 8589803520, 34359607296, 137438429184, 549755289600, 2199021158400, 8796090925056, 35184363700224, 140737479966720, 562949919866880
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

From Petros Hadjicostas, Jun 30 2018: (Start)
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_{k1}(x) = (C(x)/2)*(C(x)^{k1}  C(x^2)^{(k1)/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.)
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*(1C(x))*(1C(x^2))) + C(x). (The extra C(x) is due of course to the special assumption made for the BHK[k=1] transform.)
Here, BHK(c(n): n >= 1)(m) indicates the mth 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 mth 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).
For the current sequence, c(1) = 4, and c(n) = 0 for all n >= 2, and thus, C(x) = 4x. Substituting into the above formula for A(x), and doing the algebra, we get A(x) = 2*x*(25*x8*x^2+32*x^3) / ((2*x+1)*(2*x1)*(4*x1)), which is R. J. Mathar's formula below.
(End)
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


LINKS

Colin Barker, Table of n, a(n) for n = 1..1000
C. G. Bower, Transforms (2)
Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.
Elizabeth Wilmer, Notes on Stephan's conjectures 72, 73 and 74
Elizabeth Wilmer, Notes on Stephan's conjectures 72, 73 and 74 [cached copy]
Index entries for linear recurrences with constant coefficients, signature (4,4,16).


FORMULA

"BHK" (reversible, identity, unlabeled) transform of 4, 0, 0, 0, ...
a(2*n+1) = 2^(4*n+1)  2^(2*n+1), a(2*n) = 2^(4*n1)  2^(2*n) + 2^(2*n1), a(1)=4.
From R. J. Mathar, Mar 20 2009: (Start)
a(n) = 4*a(n1) + 4*a(n2)  16*a(n3) for n > 4.
G.f.: 2*x*(5*x+28*x^2+32*x^3) / ((2*x+1)*(2*x1)*(4*x1)).
(End)
From Colin Barker, Mar 08 2017: (Start)
a(n) = 2^(n1) * (2^n1) for n > 1 and even.
a(n) = 2^(2*n1)  2^n for n > 1 and odd.
(End)


MATHEMATICA

Join[{4}, LinearRecurrence[{4, 4, 16}, {6, 24, 120}, 24]] (* JeanFrançois Alcover, Oct 11 2017 *)


PROG

(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


CROSSREFS

Column 4 of A293500 for n>1.
(A000302  A056450) / 2 for n>1.
Cf. A088037.
Cf. A026337 (bisection), A032121.
Sequence in context: A067001 A057343 A000287 * A165164 A241602 A136591
Adjacent sequences: A032084 A032085 A032086 * A032088 A032089 A032090


KEYWORD

nonn,easy


AUTHOR

Christian G. Bower


STATUS

approved



