A371570 Number of binary necklaces of length n which have more 01 than 00 substrings.

0, 0, 2, 3, 6, 15, 29, 56, 118, 237, 467, 946, 1905, 3796, 7618, 15303, 30614, 61319, 122951, 246202, 492971, 987542, 1977560, 3959289, 7927969, 15873190, 31776708, 63614397, 127346134, 254908115, 510233309, 1021273672, 2044071894, 4091064805, 8187770675

Offset: 0

Author

Robert P. P. McKone, Mar 28 2024

Keywords

• nonn

Comments

A necklace may also be referred to as circular or cyclic strings.

Examples

			a(3) = 3: 011, 101, 110.
a(4) = 6: 0101, 0111, 1010, 1011, 1101, 1110.
a(5) = 15: 00101, 01001, 01010, 01011, 01101, 01111, 10010, 10100, 10101, 10110, 10111, 11010, 11011, 11101, 11110.
		

Crossrefs

Cf. A217464 (necklaces with equal 00 and 01), A371668 (necklaces with more 00 than 01).

Cf. A126869 (necklaces with equal 00 and 11, for n>=1), A058622 (necklaces with more 00 than 11).

Cf. A163493 (strings with equal 00 and 01), A371358 (strings with more 00 than 01), A371564 (strings with more 01 than 00).

Programs

Mathematica

tup[n_] := Tuples[{0, 1}, n];
tupToNec[n_] := Map[Append[#, #[[1]]] &, tup[n]];
cou[lst_List] := Count[lst, {0, 1}] > Count[lst, {0, 0}];
par[lst_List] := Partition[lst, 2, 1];
a[0] = 0;
a[n_] := Map[cou, Map[par, tupToNec[n]]] // Boole // Total;
Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}]

Formula

a(n) = 2^n - A217464(n) - A371668(n).

a(n) = -(((n-3)*(n-2) - 8*(n-5)^2*(n-2)*a(n-5) + 4*(n*((3n-34)*n+117)-114)*a(n-4) + 2*(((32-3n)*n-95)*n+62)*a(n-3) + (((5n-52)*n+157)*n-114)*a(n-2) + (((39-4n)*n-103)*n+58)*a(n-1))/((n-6)*(n-3)*n)) for n>=7.