A032094 - OEIS

%I #38 Jun 30 2018 20:48:58

%S 4,16,60,160,396,848,1716,3200,5720,9696,15912,25152,38760,58080,

%T 85272,122496,173052,240240,328900,443872,592020,780208,1017900,

%U 1314560,1682928,2135744,2689808,3361920,4173840,5147328,6310128,7689984,9321780,11240400

%N Number of reversible strings with n-1 beads of 2 colors. 7 beads are black. String is not palindromic.

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

%C 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

%C From _Petros Hadjicostas_, May 19 2018: (Start)

%C 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.

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

%C 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.

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

%C 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.

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

%C (End)

%H Colin Barker, <a href="/A032094/b032094.txt">Table of n, a(n) for n = 9..1000</a>

%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>

%H Pieter Moree, <a href="http://dx.doi.org/10.1016/j.disc.2005.03.004">The formal series Witt transform</a>, Discr. Math. no. 295 vol. 1-3 (2005) 143-160. - _R. J. Mathar_, Nov 08 2008

%H <a href="/index/Rec#order_12">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2,-12,17,8,-28,8,17,-12,-2,4,-1).

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

%F From  _R. J. Mathar_, Nov 08 2008: (Start)

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

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

%F From _Colin Barker_, Mar 07 2015: (Start)

%F 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.

%F 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.

%F (End)

%F From _Petros Hadjicostas_, May 19 2018: (Start)

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

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

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

%F 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.

%F (End)

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

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

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

%o (PARI) Vec(4*x^9*(1+x^2)/((1-x)^8*(1+x)^4) + O(x^100)) \\ _Colin Barker_, Mar 07 2015

%Y Cf. A005995, A018210, A032091, A032092, A032093, A159916. - _M. F. Hasler_, May 02 2009 and _Petros Hadjicostas_, May 19 2018

%K nonn,easy

%O 9,1

%A _Christian G. Bower_