A032093 Number of reversible strings with n-1 beads of 2 colors. 6 beads are black. Strings are not palindromic.

3, 12, 40, 100, 226, 452, 848, 1484, 2485, 3976, 6160, 9240, 13524, 19320, 27072, 37224, 50391, 67188, 88440, 114972, 147862, 188188, 237328, 296660, 367913, 452816, 553504, 672112, 811240, 973488, 1161984, 1379856

Offset: 8

Author

Christian G. Bower

Keywords

• nonn

Comments

From Petros Hadjicostas, May 19 2018: (Start)

Let k be an integer >= 2. The g.f. of the BHK[k] transform of the sequence (c(n): n>=1), with g.f. C(x) = Sum_{n>=1} c(n)*x^n, is A_k(x) = (C(x)^k - C(x^2)^(k/2))/2 if k is even, and A_k(x) = (C(x)/2)*(C(x)^{k-1} - C(x^2)^{(k-1)/2}) if k is odd. This follows easily from the formulae in C. G. Bower's web link below about transforms.

When k is odd and c(n) = 1 for all n>=1, we get C(x) = x/(1-x) and A_k(x) = (1/2)*(x/(1-x))*((x/(1-x))^{k-1} - (x^2/(1-x^2))^{(k-1)/2}). If (a_k(n): n>=1) is the output sequence (with g.f. A_k(x)), then it can be proved (using Taylor expansions) that a_k(n) = (1/2)*(binomial(n-1, n-k) - binomial(floor((n-1)/2), floor((n-k)/2))) for n >= k+1. (Clearly, a_k(1) = ... = a_k(k) = 0.)

In this sequence, k = 7, and (according to C. G. Bower) a(n) = a_{k=7}(n) is the number of reversible non-palindromic compositions of n with 7 positive parts. If n = b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + b_7 is such a composition of n (with b_i >=1), then it is equivalent to the composition n = b_7 + b_6 + b_5 + b_4 + b_3 + b_2 + b_1, and each equivalent class has two elements because here linear palindromes are not allowed as compositions of n.

The fact that we are finding the BHK[7] transform of 1, 1, 1, ... means that each part of each composition of n can have exactly one color (see Bower's link below about transforms).

In each such composition replace each b_i with one black (B) ball followed by b_i - 1 white (W) balls. Then drop the first black (B) ball. We then get a reversible non-palindromic string of length n-1 that has 6 black balls and n-7 white balls. This process, applied to the equivalent compositions n = b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + b_7 = b_7 + b_6 + b_5 + b_4 + b_3 + b_2 + b_1, gives two strings of length n-1 with 6 black balls and n-7 white balls that are mirror images of each other.

Hence, for n>=2, a(n) = a_{k=7}(n) is also the number of reversible non-palindromic strings of length n-1 that have k-1 = 6 black balls and n-k = n-7 white balls. (Clearly, a(n) = a_{k=7}(n) > 0 only for n >= 8. For n=7, the composition 1+1+1+1+1+1+1, which corresponds to string BBBBBB, is discarded because it is palindromic.)

(End)

Examples

			From _Petros Hadjicostas_, May 19 2018: (Start)
For n=8, we have the following 3 reversible non-palindromic compositions with 7 parts of n: 1+1+1+1+1+1+2 (= 2+1+1+1+1+1+1), 1+1+1+1+1+2+1 (= 1+2+1+1+1+1+1), and 1+1+1+1+2+1+1 (= 1+1+2+1+1+1+1). Using the process described in the comments, we get the following reversible non-palindromic strings with 6 black balls and n-7=1 white balls: BBBBBBW (= WBBBBBB), BBBBBWB (= BWBBBBB), and BBBBWBB (= BBWBBBB).
For n=9, we get the following 12 compositions and 12 corresponding strings:
1+1+1+1+1+1+3 <-> BBBBBBWW
1+1+1+1+1+3+1 <-> BBBBBWWB
1+1+1+1+3+1+1 <-> BBBBWWBB
1+1+1+1+1+2+2 <-> BBBBBWBW
1+1+1+1+2+1+2 <-> BBBBWBBW
1+1+1+2+1+1+2 <-> BBBWBBBW
1+1+2+1+1+1+2 <-> BBWBBBBW
1+2+1+1+1+1+2 <-> BWBBBBBW
1+1+1+1+2+2+1 <-> BBBBWBWB
1+1+1+2+1+2+1 <-> BBBWBBWB
1+1+2+1+1+2+1 <-> BBWBBBWB
1+1+1+2+2+1+1 <-> BBBWBWBB
(End)
		

Links

• C. G. Bower, Transforms (2)
• Index entries for linear recurrences with constant coefficients, signature (4, -3, -8, 14, 0, -14, 8, 3, -4, 1).

Crossrefs

Cf. A002620, A006584, A032091, A032092, A032094, A239572, A282011.

Formula

"BHK[ 7 ]" (reversible, identity, unlabeled, 7 parts) transform of 1, 1, 1, 1, ...

Empirical G.f.: -x^8*(x^2+3)/((x-1)^7*(x+1)^3). - Colin Barker, Nov 24 2012

From Petros Hadjicostas, May 19 2018: (Start)

a(n) = (1/2)*(binomial(n-1, n-7) - binomial(floor((n-1)/2), floor((n-7)/2))) for n >= 8.

G.f.: (1/2)*(x/(1-x))*((x/(1-x))^6 - (x^2/(1-x^2))^3), which is the same as the g.f. given by Colin Barker above.

(End)

Extensions

Definition changed slightly by Harvey P. Dale, Oct 02 2017