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,3

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)

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

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

Example

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

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

Prog

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

Crossrefs

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

Sequence in context: A252943 A294617 A320450 * A326175 A072337 A335056

Adjacent sequences: A100883 A100884 A100885 * A100887 A100888 A100889

Keyword

nonn,easy

Author

Creighton Dement, Nov 21 2004

Extensions

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

Status

approved