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
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
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
KEYWORD
nonn,easy
AUTHOR
Creighton Dement, Nov 21 2004
EXTENSIONS
More terms from Robert G. Wilson v, Nov 26 2004
STATUS
approved