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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A032094 Number of reversible strings with n-1 beads of 2 colors. 7 beads are black. String is not palindromic. 7
4, 16, 60, 160, 396, 848, 1716, 3200, 5720, 9696, 15912, 25152, 38760, 58080, 85272, 122496, 173052, 240240, 328900, 443872, 592020, 780208, 1017900, 1314560, 1682928, 2135744, 2689808, 3361920, 4173840, 5147328, 6310128, 7689984, 9321780, 11240400 (list; graph; refs; listen; history; text; internal format)
OFFSET

9,1

COMMENTS

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

Also 7th column of A159916, i.e., number of 7-element subsets of {1,...,n-1} whose elements add up to an odd integer. - M. F. Hasler, May 02 2009

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

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

(End)

LINKS

Colin Barker, Table of n, a(n) for n = 9..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 (4,-2,-12,17,8,-28,8,17,-12,-2,4,-1).

FORMULA

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

From  R. J. Mathar, Nov 08 2008: (Start)

G.f.: 4*x^9*(1+x^2)/((1-x)^8*(1+x)^4).

a(n) = 4*A031164(n-9). (End)

From Colin Barker, Mar 07 2015: (Start)

a(n) = (n^7-28*n^6+322*n^5-1960*n^4+6664*n^3-11872*n^2+8448*n)/10080 if n is even.

a(n) = (n^7-28*n^6+322*n^5-1960*n^4+6769*n^3-13132*n^2+13068*n-5040)/10080 if n is odd.

(End)

From Petros Hadjicostas, May 19 2018: (Start)

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

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

G.f.: (1/2)*((x/(1-x))^8 - (x^2/(1-x^2))^4).

These formulae agree with the above formulae by R. J. Mathar and Colin Barker. Clearly, the first two formulae (those about a(n)) can be combined into the one given by M. F. Hasler below in the PROG section.

(End)

MATHEMATICA

f[n_] := Binomial[n - 1, n - 8]/2 - If[ OddQ@ n, 0, Binomial[(n/2) - 1, (n - 8)/2]/2]; Array[f, 36, 9] (* or *)

CoefficientList[ Series[ 4x^9 (x^2 + 1)/((x - 1)^8 (x + 1)^4), {x, 0, 40}], x] (* or *)LinearRecurrence[{4, -2, -12, 17, 8, -28, 8, 17, -12, -2, 4, -1}, {4, 16, 60, 160, 396, 848, 1716, 3200, 5720, 9696, 15912, 25152}, 34] (* Robert G. Wilson v, May 20 2018 *)

PROG

(PARI) A032094(n)=(binomial(n--, 7)-if(n%2, binomial(n\2, 3)))\2 \\ M. F. Hasler, May 02 2009

(PARI) Vec(4*x^9*(1+x^2)/((1-x)^8*(1+x)^4) + O(x^100)) \\ Colin Barker, Mar 07 2015

CROSSREFS

Cf. A005995, A018210, A032091, A032092, A032093, A159916. - M. F. Hasler, May 02 2009 and Petros Hadjicostas, May 19 2018

Sequence in context: A207276 A047123 A297096 * A282083 A261563 A265955

Adjacent sequences:  A032091 A032092 A032093 * A032095 A032096 A032097

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 24 01:20 EDT 2018. Contains 316541 sequences. (Running on oeis4.)