A366044 Number of circular binary sequences of length n with an even number of 0's and no three consecutive 1's.

0, 1, 3, 7, 10, 19, 35, 67, 120, 221, 407, 751, 1378, 2535, 4663, 8579, 15776, 29017, 53371, 98167, 180554, 332091, 610811, 1123459, 2066360, 3800629, 6990447, 12857439, 23648514, 43496399, 80002351, 147147267, 270646016, 497795633, 915588915, 1684030567, 3097415114, 5697034595, 10478480275

Offset

1,3

Comments

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.

a(n) is also equal to the number of circular compositions of n into an even number of 1s, 2s, and 3s.

Links

Table of n, a(n) for n=1..39.

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.

Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.

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,3,2,1).

Formula

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

a(n) = (1/2)*A001644(n) - 1/2 + 2*[n==0 (mod 4)].

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.

a(n) = A001644(n) - A366045(n).

Example

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.
For n=4, the a(4)=7 allowed sequences are 0000, 0011, 0101, 0110, 1001, 1010, 1100.

Mathematica

LinearRecurrence[{0, 1, 2, 3, 2, 1}, {0, 1, 3, 7, 10, 19}, 50]

Crossrefs

Cf. A001644, A366045.

Sequence in context: A069153 A167390 A000223 * A031328 A255180 A053159

Adjacent sequences: A366041 A366042 A366043 * A366045 A366046 A366047

Keyword

nonn,easy

Author

Joshua P. Bowman, Sep 27 2023

Status

approved