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

2, 6, 16, 32, 60, 100, 160, 240, 350, 490, 672, 896, 1176, 1512, 1920, 2400, 2970, 3630, 4400, 5280, 6292, 7436, 8736, 10192, 11830, 13650, 15680, 17920, 20400, 23120, 26112, 29376, 32946, 36822, 41040, 45600, 50540, 55860, 61600, 67760, 74382, 81466, 89056

Offset: 6

Author

Christian G. Bower

Keywords

• nonn
• easy

Comments

Also, number of 4-element subsets of the set {1,...,n-1} whose elements sum up to an odd integer, i.e., 4th column of the triangle A159916, cf. there. - M. F. Hasler, May 01 2009

Also, if the offset is changed to 3, so that a(3)=2, a(n) = number of non-equivalent (mod D_3) ways to place 2 indistinguishable points on a triangular grid of side n so that they are not adjacent. - Heinrich Ludwig, Mar 23 2014

Also, the number of binary strings of length n with exactly one pair of consecutive 0s and exactly three pairs of consecutive 1s. - Jeremy Dover, Jul 07 2016

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

Hence, for n >= 2, a(n) = a_{k=5}(n) is also the number of reversible non-palindromic strings of length n-1 that have k-1 = 4 black balls and n-k = n-5 white balls. (Clearly, a(n) = a_{k=5}(n) > 0 only for n >= 6. For n=5, the composition 1+1+1+1+1, which corresponds to string BBBB, is discarded because it is palindromic.)

For k = 3 (an odd integer) we have a_k(n) = A002620(n-2) (for n >= 4), while for k = 7 (also an odd integer), we have a_k(n) = A032093(n) (for n >= 8).

For k = 4 (which is even), we have a_k(n) = A006584(n-2) (for n >= 5), while for k = 6 and k = 8 (which are also even integers), we get sequences A032092 and A032094, respectively. When k is even, the g.f. in these cases is A_k(x) = (C(x)^k - C(x^2)^(k/2))/2, where C(x) = x/(1-x). The formula for a_k(n) (given above) needs to be modified as well.

(End)

The formula for a(n) for this sequence was Ralf Stephan's conjecture 73. It was solved by Elizabeth Wilmer (see Proposition 2 in one of the links below). There is a minor typo in the original conjecture. - Petros Hadjicostas, Jul 04 2018

Examples

			From _Petros Hadjicostas_, May 19 2018: (Start)
For n=6, we have the following reversible non-palindromic compositions with 5 parts of n: 1+1+1+1+2 (= 2+1+1+1+1) and 1+1+1+2+1 (= 1+2+1+1+1). Using the process described in the comments, we get the following reversible non-palindromic strings with 4 black balls and n-5=1 white balls: BBBBW (= WBBBB) and BBBWB (= BWBBB).
For n=7, we get the following 6 compositions and 6 corresponding strings:
1+1+1+1+3 <-> BBBBWW
1+1+1+3+1 <-> BBBWWB
1+1+1+2+2 <-> BBBWBW
1+1+2+1+2 <-> BBWBBW
1+1+2+2+1 <-> BBWBWB
1+2+1+1+2 <-> BWBBBW
(End)
		

Links

• Colin Barker, Table of n, a(n) for n = 6..1000
• C. G. Bower, Transforms (2)
• Hamzeh Mujahed, Benedek Nagy, Hyper-Wiener Index on Rows of Unit Cells of the BCC Grid, Comptes rendus de l’Académie bulgare des Sciences, Tome 71, No 5, 2018, 675-684. See p. 8.
• Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.
• Elizabeth Wilmer, Notes on Stephan's conjectures 72, 73 and 74 [broken link].
• Elizabeth Wilmer, Notes on Stephan's conjectures 72, 73 and 74 [cached copy].
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-5,5,1,-3,1)

Crossrefs

Cf. A002620, A006584, A032092, A032093, A032094, A239572.

a(n+6) = 2*A002624(n).

Fourth column of A274228. - Jeremy Dover, Jul 07 2016

Programs

Mathematica

Table[If[EvenQ[n],(n^4-10n^3+32n^2-32n)/48,(n^4-10n^3+32n^2-38n+15)/48], {n,6,50}] (* or *)
LinearRecurrence[{3,-1,-5,5,1,-3,1},{2,6,16,32,60,100,160},50] (* Harvey P. Dale, Apr 11 2016 *)
CoefficientList[Series[-2/((x - 1)^5 (x + 1)^2), {x, 0, 42}], x] (* Robert G. Wilson v, Jun 20 2018 *)

PARI

A032091(n)=polcoeff(2/(1-x)^5/(1+x)^2+O(x^(n-5)),n-6)
A032091(n)=((n-5)*(n-3)*(n-1)^2+if(n%2==0,6*n-15))/48 \\ M. F. Hasler, May 01 2009

Formula

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

From M. F. Hasler, May 01 2009: (Start)

G.f.: -2*x^6 / ((x-1)^5*(x+1)^2). [corrected by Colin Barker, Mar 07 2015]

a(n) = [(n-5)(n-3)(n-1)^2 + (6n-15) X[2Z](n)]/48, where X[2Z] is the characteristic function of 2Z.

(End)

From Colin Barker, Mar 07 2015: (Start)

a(n) = (n^4-10*n^3+32*n^2-32*n)/48 if n is even.

a(n) = (n^4-10*n^3+32*n^2-38*n+15)/48 if n is odd.

(End)

a(n) = (2*n^4 - 20*n^3 + 64*n^2 + 6*(-1)^n*n - 70*n - 15*(-1)^n + 15)/96. - Ilya Gutkovskiy, Jul 08 2016

From Petros Hadjicostas, May 19 2018: (Start)

a(n) = (1/2)*(binomial(n-1, n-5) - binomial(floor((n-1)/2) - floor((n-5)/2))).

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

(End)

a(n) = 2*A002624(n-6) - Robert G. Wilson v, Jun 20 2018