%I #26 Mar 09 2024 12:31:24
%S 0,1,3,7,10,19,35,67,120,221,407,751,1378,2535,4663,8579,15776,29017,
%T 53371,98167,180554,332091,610811,1123459,2066360,3800629,6990447,
%U 12857439,23648514,43496399,80002351,147147267,270646016,497795633,915588915,1684030567,3097415114,5697034595,10478480275
%N Number of circular binary sequences of length n with an even number of 0's and no three 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 circular compositions of n into an even number of 1s, 2s, and 3s.
%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://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_06">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,2,3,2,1).
%F G.f.: x^2*(1+2*x+3*x^2)*(1+x+x^2)/((1-x-x^2-x^3)*(1+x+x^2+x^3)).
%F a(n) = (1/2)*A001644(n) - 1/2 + 2*[n==0 (mod 4)].
%F a(n) = a(n-2)+2*a(n-3)+3*a(n-4)+2*a(n-5)+a(n-6), a(1)=0, a(2)=1, a(3)=3, a(4)=7, a(5)=10, a(6)=19.
%F a(n) = A001644(n) - A366045(n).
%e The sequence ‘1’ is not allowed because the 1 is considered to be adjacent to itself. Similarly ’11’ is not allowed. Thus a(1)=0 because the sequence ‘0’ does not have an even number of 0's, and a(2)=1 because ’00’ is the only allowed sequence of length two.
%e For n=4, the a(4)=7 allowed sequences are 0000, 0011, 0101, 0110, 1001, 1010, 1100.
%t LinearRecurrence[{0, 1, 2, 3, 2, 1}, {0, 1, 3, 7, 10, 19}, 50]
%Y Cf. A001644, A366045.
%K nonn,easy
%O 1,3
%A _Joshua P. Bowman_, Sep 27 2023