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 three consecutive 1's.
1

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

%S 1,2,4,4,11,20,36,64,121,222,408,748,1379,2536,4664,8576,15777,29018,

%T 53372,98164,180555,332092,610812,1123456,2066361,3800630,6990448,

%U 12857436,23648515,43496400,80002352,147147264,270646017,497795634,915588916,1684030564

%N Number of circular binary sequences of length n with an odd 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 odd number of 1's, 2's, and 3'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_06">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,2,3,2,1).

%F G.f.: x*(1+2*x+3*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)=1, a(2)=2, a(3)=4, a(4)=4, a(5)=11, a(6)=20.

%F a(n) = A001644(n) - A366044(n).

%e a(1)=1 because 0 is the only allowed sequence of length one, and a(2)=2 because 01 and 10 are the only allowed sequences of length two.

%e The allowed sequences of length three are 000, 011, 101, and 110. The allowed sequences of length four are 0001, 0010, 0100, and 1000. Thus a(3)=a(4)=4.

%t LinearRecurrence[{0, 1, 2, 3, 2, 1}, {1, 2, 4, 4, 11, 20}, 50]

%Y Cf. A001644, A283834, A366043, A366044.

%K nonn,easy

%O 1,2

%A _Joshua P. Bowman_, Sep 27 2023