A032092 Number of reversible strings with n-1 beads of 2 colors. 5 beads are black. String is not palindromic.

3, 9, 28, 60, 126, 226, 396, 636, 1001, 1491, 2184, 3080, 4284, 5796, 7752, 10152, 13167, 16797, 21252, 26532, 32890, 40326, 49140, 59332, 71253, 84903, 100688, 118608, 139128, 162248, 188496, 217872, 250971, 287793, 329004, 374604, 425334, 481194, 543004

Offset: 7

Author

Christian G. Bower

Keywords

• nonn
• easy

Comments

If the offset is changed to 3, this is the 2nd Witt transform of A000217 [Moree]. - R. J. Mathar, Nov 08 2008

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 even and c(n) = 1 for all n >= 1, we get C(x) = x/(1-x) and A_k(x) = (1/2)*((x/(1-x))^k - (x^2/(1-x^2))^{k/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((n/2)-1, (n-k)/2)) for even n >= k+1 and a_k(n) = (1/2)*binomial(n-1, n-k) for odd n >= k+1. (Clearly, a_k(1) = ... = a_k(k) = 0.)

In this sequence, k = 6, and (according to C. G. Bower) a(n) = a_{k=6}(n) is the number of reversible non-palindromic compositions of n with 6 positive parts. If n = b_1 + b_2 + b_3 + b_4 + b_5 + b_6 is such a composition of n (with b_i >= 1), then it is equivalent to the composition n = 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[6] 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 5 black balls and n-6 white balls. This process, applied to the equivalent compositions n = b_1 + b_2 + b_3 + b_4 + b_5 + b_6 = b_6 + b_5 + b_4 + b_3 + b_2 + b_1, gives two strings of length n-1 with 5 black balls and n-6 white balls that are mirror images of each other.

Hence, for n >= 2, a(n) = a_{k=6}(n) is also the number of reversible non-palindromic strings of length n-1 that have k-1 = 5 black balls and n-k = n-6 white balls. (Clearly, a(n) = a_{k=6}(n) > 0 only for n >= 7.)

(End)

Examples

			From _Petros Hadjicostas_, May 19 2018: (Start)
For n=7, we have the following 3 reversible non-palindromic compositions with 6 parts of n: 1+1+1+1+1+2 (= 2+1+1+1+1+1), 1+1+1+1+2+1 (= 1+2+1+1+1+1), and 1+1+1+2+1+1 (= 1+1+2+1+1+1). Using the process described in the comments, we get the following reversible non-palindromic strings with 5 black balls and n-6 = 1 white balls: BBBBBW (= WBBBBB), BBBBWB (= BWBBBB), and BBBWBB (= BBWBBB).
For n=8, we get the following 9 compositions and 9 corresponding strings:
1+1+1+1+1+3 <-> BBBBBWW
1+1+1+1+3+1 <-> BBBBWWB
1+1+1+3+1+1 <-> BBBWWBB
1+1+1+1+2+2 <-> BBBBWBW
1+1+1+2+1+2 <-> BBBWBBW
1+1+2+1+1+2 <-> BBWBBBW
1+2+1+1+1+2 <-> BWBBBBW
1+1+1+2+2+1 <-> BBBWBWB
1+1+2+1+2+1 <-> BBWBBWB
(End)
		

Links

• Colin Barker, Table of n, a(n) for n = 7..1000
• C. G. Bower, Transforms (2)
• Pieter Moree, The formal series Witt transform, Discr. Math. no. 295 vol. 1-3 (2005) 143-160. - _R. J. Mathar_, Nov 08 2008
• Index entries for linear recurrences with constant coefficients, signature (3,0,-8,6,6,-8,0,3,-1).

Crossrefs

Cf. A002620, A006584, A032091, A032093, A032094, A282011.

Programs

Mathematica

LinearRecurrence[{3,0,-8,6,6,-8,0,3,-1},{3,9,28,60,126,226,396,636,1001},50] (* Harvey P. Dale, Mar 19 2017 *)
f[n_] := Binomial[n - 1, n - 6]/2 - If[ OddQ@ n, 0, Binomial[(n/2) - 1, (n - 6)/2]/2]; Array[a, 40, 7] (* or *)
CoefficientList[ Series[(x^7 (x^2 + 3))/((x - 1)^6 (x + 1)^3), {x, 0, 46}], x] (* Robert G. Wilson v, May 20 2018 *)

PARI

Vec(x^7*(3+x^2)/((1-x)^6*(1+x)^3) + O(x^100)) \\ Colin Barker, Mar 07 2015

Formula

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

G.f.: x^7*(3+x^2)/((1-x)^6*(1+x)^3). - R. J. Mathar, Nov 08 2008

From Colin Barker, Mar 07 2015: (Start)

a(n) = (2*n^5-30*n^4+170*n^3-480*n^2+728*n-480)/480 if n is even.

a(n) = (2*n^5-30*n^4+170*n^3-450*n^2+548*n-240)/480 if n is odd.

(End)

From Petros Hadjicostas, May 19 2018: (Start)

a(n) = (1/2)*(binomial(n-1, n-6) - binomial((n/2)-1, (n-6)/2)) if n is even.

a(n) = (1/2)*binomial(n-1, n-6) if n is odd.

G.f.: (1/2)*((x/(1-x))^6 - (x^2/(1-x^2))^3).

These formulae agree with the above formulae by R. J. Mathar and C. Barker.

(End)