login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A032093 Number of reversible strings with n-1 beads of 2 colors. 6 beads are black. Strings are not palindromic. 5
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

8,1

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)

LINKS

Table of n, a(n) for n=8..39.

C. G. Bower, Transforms (2)

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)

EXAMPLE

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)

CROSSREFS

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

Sequence in context: A303348 A237036 A034956 * A007993 A293366 A080929

Adjacent sequences:  A032090 A032091 A032092 * A032094 A032095 A032096

KEYWORD

nonn

AUTHOR

Christian G. Bower

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 14:53 EDT 2018. Contains 316528 sequences. (Running on oeis4.)