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,3

Comments

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

Links

Table of n, a(n) for n=0..34.

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.

Example

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.

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}]}]

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

Sequence in context: A248652 A158027 A346776 * A100249 A138477 A182240

Adjacent sequences: A371567 A371568 A371569 * A371571 A371572 A371573

Keyword

nonn

Author

Robert P. P. McKone, Mar 28 2024

Status

approved