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

1, 2, 1, 4, 6, 8, 15, 24, 37, 62, 100, 160, 261, 422, 681, 1104, 1786, 2888, 4675, 7564, 12237, 19802, 32040, 51840, 83881, 135722, 219601, 355324, 574926, 930248, 1505175, 2435424, 3940597, 6376022, 10316620, 16692640, 27009261, 43701902, 70711161, 114413064, 185124226, 299537288, 484661515, 784198804, 1268860317

Offset

1,2

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 matchings in the cycle graph C_n for which the number of edges plus the number of unmatched vertices is odd.

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

Links

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

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

Formula

G.f.: x*(1+2*x)/((1-x-x^2)*(1+x+x^2)).

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

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

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

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

Example

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

Mathematica

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

Crossrefs

Cf. A000204, A061347, A100886.

Sequence in context: A048213 A338746 A283309 * A054408 A285637 A205845

Adjacent sequences: A366040 A366041 A366042 * A366044 A366045 A366046

Keyword

nonn,easy

Author

Joshua P. Bowman, Sep 27 2023

Status

approved