|
|
A366045
|
|
Number of circular binary sequences of length n with an odd number of 0's and no three consecutive 1's.
|
|
1
|
|
|
1, 2, 4, 4, 11, 20, 36, 64, 121, 222, 408, 748, 1379, 2536, 4664, 8576, 15777, 29018, 53372, 98164, 180555, 332092, 610812, 1123456, 2066361, 3800630, 6990448, 12857436, 23648515, 43496400, 80002352, 147147264, 270646017, 497795634, 915588916, 1684030564
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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 circular compositions of n into an odd number of 1's, 2's, and 3's.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: x*(1+2*x+3*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)=1, a(2)=2, a(3)=4, a(4)=4, a(5)=11, a(6)=20.
|
|
EXAMPLE
|
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.
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.
|
|
MATHEMATICA
|
LinearRecurrence[{0, 1, 2, 3, 2, 1}, {1, 2, 4, 4, 11, 20}, 50]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|