login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of circular binary sequences of length n with an odd number of 0's and no consecutive 1's.
2

%I #24 Jan 05 2025 19:51:42

%S 1,2,1,4,6,8,15,24,37,62,100,160,261,422,681,1104,1786,2888,4675,7564,

%T 12237,19802,32040,51840,83881,135722,219601,355324,574926,930248,

%U 1505175,2435424,3940597,6376022,10316620,16692640,27009261,43701902,70711161,114413064,185124226,299537288,484661515,784198804,1268860317

%N Number of circular binary sequences of length n with an odd number of 0's and no consecutive 1's.

%C 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. Also called a marked cyclic binary sequence.

%C a(n) is also equal to the number of matchings in the cycle graph C_n for which the number of edges plus the number of unmatched vertices is odd.

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

%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 Petros Hadjicostas and Lingyun Zhang, <a href="https://doi.org/10.1016/j.disc.2018.03.007">On cyclic strings avoiding a pattern</a>, Discrete Mathematics, 341 (2018), 1662-1674.

%H W. O. J. Moser, <a href="https://web.archive.org/web/2024*/https://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 G.f.: x*(1+2*x)/((1-x-x^2)*(1+x+x^2)).

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

%F a(n) = (A000204(n) + A061347(n))/2.

%F a(n) = (1/2)*A000204(n) - cos(2*Pi*n/3).

%F a(n) = A000204(n) - A100886(n-1).

%e For n = 5, the a(5) = 6 allowed sequences are 00000, 00101, 01001, 01010, 10010, 10100.

%t LinearRecurrence[{0, 1, 2, 1}, {0, 1, 2, 1}, 50]

%Y Cf. A000204, A061347, A100886.

%K nonn,easy

%O 1,2

%A _Joshua P. Bowman_, Sep 27 2023