login
Expansion of x*(1+3*x+2*x^2)/((1+x+x^2)*(1-x-x^2)).
7

%I #76 Mar 09 2024 11:35:41

%S 0,1,3,3,5,10,14,23,39,61,99,162,260,421,683,1103,1785,2890,4674,7563,

%T 12239,19801,32039,51842,83880,135721,219603,355323,574925,930250,

%U 1505174,2435423,3940599,6376021,10316619,16692642,27009260,43701901

%N Expansion of x*(1+3*x+2*x^2)/((1+x+x^2)*(1-x-x^2)).

%C This sequence was investigated in cooperation with _Paul Barry_.

%C Generating floretion: - 0.5'i - 0.5'k - 0.5j' - 0.5'ii' + 0.5'jj' - 0.5'kk' + 0.5'ik' - 0.5'ki' ("tes").

%C From _Joshua P. Bowman_, Sep 28 2023: (Start)

%C a(n) is equal to the number of circular binary sequences of length n+1 with an even number of 0's and no consecutive 1's. A circular binary sequence is a finite sequence of 0's and 1's for which the first and last digits are considered to be adjacent. Rotations are distinguished from each other.

%C a(n) is also equal to the number of matchings in the cycle graph C_{n+1} for which the number of edges plus the number of unmatched vertices is even.

%C a(n) is also equal to the number of circular compositions of n+1 into an even number of 1's and 2's. (End)

%H Wojciech Florek, <a href="/A100886/b100886.txt">Table of n, a(n) for n = 0..1001</a>

%H Joshua P. Bowman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Bowman/bowman4.html">Compositions with an Odd Number of Parts, and Other Congruences</a>, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 19.

%H Wojciech Florek, <a href="http://doi.org/10.1016/j.amc.2018.06.014">A class of generalized Tribonacci sequences applied to counting problems</a>, Appl. Math. Comput., 338 (2018), 809-821.

%H W. O. J. Moser, <a href="http://www.fq.math.ca/Scanned/31-1/moser.pdf">Cyclic binary strings without long runs of like (alternating) bits</a>, Fibonacci Quart. 31 (1993), no. 1, 2-6.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,2,1).

%F (1/2)*(a(n) + A100887(n) - A100888(n)) = A061347(n+3).

%F a(n) = (L(n+1)-A061347(n+1))/2, L=A000032; [corrected by _Wojciech Florek_, Feb 26 2018]

%F a(n) = a(n-2) + 2*a(n-3) + a(n-4), a(0) = 0, a(1) = 1, a(2) = 3, a(3) = 3.

%F a(n) = n*Sum_{j=1..floor(n/2)} binomial(2*j,n-2*j)/(2*j). - _Vladimir Kruchinin_, Apr 09 2011 (with offset 1, cf. PARI code)

%F a(n) = floor(phi^(n+1)/2), n mod 3 = 0,1; a(n) = floor((phi^(n+1)+3)/2), n mod 3 = 2, phi = (1 + sqrt(5))/2; from Binet's formula or the relation to the Lucas numbers A000032. - _Wojciech Florek_, Mar 03 2018

%F a(n) = A000032(n+1) - A366043(n+1). - _Joshua P. Bowman_, Sep 28 2023

%e When counting circular binary sequences with an even number of 0's and no consecutive 1's, the sequence "1" is not allowed because the 1 is considered to be adjacent to itself. Thus a(0)=0. For n=2, the a(2)=3 allowed sequences of length 3 are 001, 010, and 100. For n=3, the a(3)=3 allowed sequences of length 4 are 0000, 0101, and 1010. - _Joshua P. Bowman_, Sep 28 2023

%t a[0] = 0; a[1] = 1; a[2] = 3; a[3] = 3; a[n_] := a[n] = a[n - 2] + 2a[n - 3] + a[n - 4]; Table[ a[n], {n, 0, 36}]

%t (* Or *) CoefficientList[ Series[x(1 + 3x + 2x^2)/((1 + x + x^2)(1 - x - x^2)), {x, 0, 36}], x] (* _Robert G. Wilson v_, Nov 26 2004 *)

%t LinearRecurrence[{0,1,2,1},{0,1,3,3},40] (* _Harvey P. Dale_, Apr 04 2016 *)

%o (Maxima) a(n):=n*sum(binomial(k,n-k)*(if oddp(k) then 0 else 1/k),k,1,n) /* _Vladimir Kruchinin_, Apr 09 2011 */

%o (PARI)

%o a(n)=n*sum(j=1,n\2,k=2*j;binomial(k,n-k)/k);

%o vector(66,n,a(n)) /* _Joerg Arndt_, Apr 09 2011 */

%o (PARI)

%o concat([0],Vec(x*(1+3*x+2*x^2)/((1+x+x^2)*(1-x-x^2))+O(x^66))) /* _Joerg Arndt_, Apr 09 2011 */

%o (Magma) I:=[0,1,3,3]; [n le 4 select I[n] else Self(n-2)+2*Self(n-3)+Self(n-4): n in [1..40]]; // _Vincenzo Librandi_, Jul 30 2015

%Y Cf. A000032, A007040, A087204, A100887, A100888, A100889, A100890, A366043.

%K nonn,easy

%O 0,3

%A _Creighton Dement_, Nov 21 2004

%E More terms from _Robert G. Wilson v_, Nov 26 2004