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

0, 1, 3, 3, 5, 10, 14, 23, 39, 61, 99, 162, 260, 421, 683, 1103, 1785, 2890, 4674, 7563, 12239, 19801, 32039, 51842, 83880, 135721, 219603, 355323, 574925, 930250, 1505174, 2435423, 3940599, 6376021, 10316619, 16692642, 27009260, 43701901

Offset: 0

Author

Creighton Dement, Nov 21 2004

Keywords

• nonn
• easy

Comments

This sequence was investigated in cooperation with Paul Barry.

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").

From Joshua P. Bowman, Sep 28 2023: (Start)

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.

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.

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)

Examples

			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
		

Links

• Wojciech Florek, Table of n, a(n) for n = 0..1001
• Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 19.
• Wojciech Florek, A class of generalized Tribonacci sequences applied to counting problems, Appl. Math. Comput., 338 (2018), 809-821.
• W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31 (1993), no. 1, 2-6.
• Index entries for linear recurrences with constant coefficients, signature (0,1,2,1).

Crossrefs

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

Programs

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

Mathematica

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}]
(* 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 *)
LinearRecurrence[{0,1,2,1},{0,1,3,3},40] (* Harvey P. Dale, Apr 04 2016 *)

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 */

PARI

a(n)=n*sum(j=1,n\2,k=2*j;binomial(k,n-k)/k);
vector(66,n,a(n)) /* Joerg Arndt, Apr 09 2011 */

PARI

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 */

Formula

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

a(n) = (L(n+1)-A061347(n+1))/2, L=A000032; [corrected by Wojciech Florek, Feb 26 2018]

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

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)

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

a(n) = A000032(n+1) - A366043(n+1). - Joshua P. Bowman, Sep 28 2023

Extensions

More terms from Robert G. Wilson v, Nov 26 2004