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

 

Logo


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

7,1

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)

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).

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)

EXAMPLE

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)

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 *)

PROG

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

CROSSREFS

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

Sequence in context: A102558 A022767 A015638 * A026524 A282081 A022631

Adjacent sequences:  A032089 A032090 A032091 * A032093 A032094 A032095

KEYWORD

nonn,easy

AUTHOR

Christian G. Bower

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 18 14:57 EDT 2018. Contains 316322 sequences. (Running on oeis4.)