|
%I #108 Sep 21 2018 09:20:27
%S 2,6,16,32,60,100,160,240,350,490,672,896,1176,1512,1920,2400,2970,
%T 3630,4400,5280,6292,7436,8736,10192,11830,13650,15680,17920,20400,
%U 23120,26112,29376,32946,36822,41040,45600,50540,55860,61600,67760,74382,81466,89056
%N Number of reversible strings with n-1 beads of 2 colors. 4 beads are black. String is not palindromic.
%C 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
%C 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
%C 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
%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 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.)
%C 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.
%C 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).
%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 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.
%C 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.)
%C 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).
%C 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.
%C (End)
%C 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
%H Colin Barker, <a href="/A032091/b032091.txt">Table of n, a(n) for n = 6..1000</a>
%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H Hamzeh Mujahed, Benedek Nagy, <a href="https://dx.doi.org/10.7546/CRABS.2018.05.13">Hyper-Wiener Index on Rows of Unit Cells of the BCC Grid</a>, Comptes rendus de l’Académie bulgare des Sciences, Tome 71, No 5, 2018, 675-684. See p. 8.
%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0409509">Prove or disprove: 100 conjectures from the OEIS</a>, arXiv:math/0409509 [math.CO], 2004.
%H Elizabeth Wilmer, <a href="http://www.oberlin.edu/math/faculty/wilmer/OEISconj727374.pdf">Notes on Stephan's conjectures 72, 73 and 74</a> [broken link].
%H Elizabeth Wilmer, <a href="/A032091/a032091.pdf">Notes on Stephan's conjectures 72, 73 and 74</a> [cached copy].
%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-5,5,1,-3,1)
%F "BHK[ 5 ]" (reversible, identity, unlabeled, 5 parts) transform of 1, 1, 1, 1, ...
%F From _M. F. Hasler_, May 01 2009: (Start)
%F G.f.: -2*x^6 / ((x-1)^5*(x+1)^2). [corrected by _Colin Barker_, Mar 07 2015]
%F a(n) = [(n-5)(n-3)(n-1)^2 + (6n-15) X[2Z](n)]/48, where X[2Z] is the characteristic function of 2Z.
%F (End)
%F From _Colin Barker_, Mar 07 2015: (Start)
%F a(n) = (n^4-10*n^3+32*n^2-32*n)/48 if n is even.
%F a(n) = (n^4-10*n^3+32*n^2-38*n+15)/48 if n is odd.
%F (End)
%F 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
%F From _Petros Hadjicostas_, May 19 2018: (Start)
%F a(n) = (1/2)*(binomial(n-1, n-5) - binomial(floor((n-1)/2) - floor((n-5)/2))).
%F G.f.: (1/2)*(x/(1-x))*((x/(1-x))^4 - (x^2/(1-x^2))^2).
%F (End)
%F a(n) = 2*A002624(n-6) - _Robert G. Wilson v_, Jun 20 2018
%e From _Petros Hadjicostas_, May 19 2018: (Start)
%e 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).
%e For n=7, we get the following 6 compositions and 6 corresponding strings:
%e 1+1+1+1+3 <-> BBBBWW
%e 1+1+1+3+1 <-> BBBWWB
%e 1+1+1+2+2 <-> BBBWBW
%e 1+1+2+1+2 <-> BBWBBW
%e 1+1+2+2+1 <-> BBWBWB
%e 1+2+1+1+2 <-> BWBBBW
%e (End)
%t 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 *)
%t LinearRecurrence[{3,-1,-5,5,1,-3,1},{2,6,16,32,60,100,160},50] (* _Harvey P. Dale_, Apr 11 2016 *)
%t CoefficientList[Series[-2/((x - 1)^5 (x + 1)^2), {x, 0, 42}], x] (* _Robert G. Wilson v_, Jun 20 2018 *)
%o (PARI) A032091(n)=polcoeff(2/(1-x)^5/(1+x)^2+O(x^(n-5)),n-6)
%o A032091(n)=((n-5)*(n-3)*(n-1)^2+if(n%2==0,6*n-15))/48 \\ _M. F. Hasler_, May 01 2009
%Y Cf. A002620, A006584, A032092, A032093, A032094, A239572.
%Y a(n+6) = 2*A002624(n).
%Y Fourth column of A274228. - _Jeremy Dover_, Jul 07 2016
%K nonn,easy
%O 6,1
%A _Christian G. Bower_
|
