|
| |
|
|
A032091
|
|
Number of reversible strings with n-1 beads of 2 colors. 4 beads are black. String is not palindromic.
|
|
13
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
6,1
|
|
|
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
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
|
|
|
LINKS
|
|
|
|
FORMULA
|
"BHK[ 5 ]" (reversible, identity, unlabeled, 5 parts) transform of 1, 1, 1, 1, ...
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)
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
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)
|
|
|
EXAMPLE
|
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)
|
|
|
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 *)
|
|
|
PROG
|
(PARI) A032091(n)=polcoeff(2/(1-x)^5/(1+x)^2+O(x^(n-5)), n-6)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
