|
| |
|
|
A032106
|
|
Number of reversible strings with n black beads and n-1 white beads. String is not palindromic.
|
|
1
|
|
|
|
1, 1, 4, 16, 60, 226, 848, 3200, 12120, 46126, 176232, 675808, 2599688, 10028292, 38777664, 150266880, 583395120, 2268771670, 8836291640, 34461586016, 134564376232, 526024564572, 2058357329184
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
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 (e(n): n >= 1), which has g.f. E(x) = Sum_{n >= 1} e(n)*x^n, has generating function B_k(x) = (1/2)*(E(x)^k - E(x^2)^{k/2}) if k is even, and B_k(x) = E(x)*B_{k-1}(x) = (E(x)/2)*(E(x)^{k-1} - E(x^2)^{(k-1)/2}) if k is odd. For k=1, Bower assumes that the BHK[k=1] transform of (e(n): n >= 1) is itself, which means that the g.f. of the output sequence is E(x). (This assumption is not accepted by all mathematicians because a sequence of length 1 is not only reversible but palindromic as well.)
For this sequence, e(n) = 1 for all n >=1, and so E(x) = x/(1-x). We have a(n) = BHK[n]((e(n): n >= 1))(2*n) = (2*n)-th element of the output sequence of the BHK[n] transform of (1, 1, 1, ...).
For k = 2*m (with m >= 1), we have B_k(x) = (x^k/2)*(1/(1-x)^k - 1/(1-x^2)^{k/2}) = (x^k/2)*(Sum_{s >= 0} C(k+s-1, s)*x^s - Sum_{s >= 0} C((k/2)+s-1, s)*x^(2*s)). This implies a(2*m) = (1/2)*(C(4*m-1, 2*m) - C(2*m-1, m)) = (1/4) * (C(4*m, 2*m) - C(2*m, m)), which is one of Bower's formulae below.
For k = 2*m+1 (with m >= 1), we have B_k(x)=(x^k/2)*(1/(1-x))*((1/(1-x)^(k-1) - 1/(1-x^2)^{(k-1)/2}). Using Taylor expansions and series manipulations (details are omitted), we get that the coefficient of the (2*(2m+1))-th term of B_{2m+1}(x) is a(2*m+1) = (1/2)*(Sum_{0 <= s <= 2*m+1} C(2*m+s-1, s) - Sum_{0 <= s <= m} C(m+s-1, s)) = (1/2)*(C(4*m+1, 2*m+1) - C(2*m, m)). (This formula is not true for m = 0 because a(1) = 1. See the comment above about the BHK[k=1] transform.)
(End)
The formula for a(n) for this sequence was Ralf Stephan's conjecture 74. It was solved by Elizabeth Wilmer (see Proposition 3 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 04 2018
|
|
|
LINKS
|
|
|
|
FORMULA
|
"BHK[ n ](2n)" (reversible, identity, unlabeled, n parts, 2n elements) transform of 1, 1, 1, 1...
a(2n) = 1/4 * [C(4n, 2n) - C(2n, n)] and a(2n+1) = A034872(4n+2)-A034872(4n+1) for n >= 1.
a(2*n+1) = (1/2)*(C(4*n+1, 2*n+1) - C(2*n, n)) for n >= 1.
a(n) = (1/8)*(2*A000984(n) - (3-(-1)^n)*A000984(floor(n/2)) for n >= 2.
G.f.: x + f(x)/4 -(2*x+1)*f(x^2)/4, where f(x) = 1/sqrt(1-4*x) = g.f. of A000984.
(End)
|
|
|
MATHEMATICA
|
a[1] = 1; a[n_] := (1/4) If[EvenQ[n], Binomial[2n, n] - Binomial[n, n/2], Binomial[2n, n] - 2 Binomial[n-1, (n-1)/2]]; Array[a, 23] (* Jean-François Alcover, Jan 20 2019 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
