A264695 Number of equidistributed binary strings of length n.

2, 2, 6, 4, 4, 12, 34, 20, 16, 8, 68, 100, 144, 314, 668, 360, 288, 128, 192, 400, 608, 2320, 8816, 9408, 9912, 6912, 38204, 37864, 52464, 108608, 209664, 106368, 79360, 32768, 49152, 16384

Offset

1,1

Comments

A string w is equidistributed if the number of occurrences of any two factors (contiguous subwords) in w differ by at most 1. Here are examples of equidistributed words for the first few lengths: 0, 01, 010, 0110, 00110, 001101, 0011010, 01001110,011100010, 0101110001, 01011100010, 010111000110.

a(n) is even by symmetry. - Michael S. Branicky, Jul 25 2021

Links

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

Michael S. Branicky, Python program

A. Carpi and A. de Luca, Uniform words, Advances in Applied Mathematics, 32 (2004), 485-522.

Teturo Kamae and Yu-Mei Xue, An Easy Criterion for Randomness, Sankhya: The Indian Journal of Statistics, 2015, Volume 77-A, Part 1, pp. 126-152, DOI:10.1007/s13171-014-0054-3.

Prog

(Python) # see links for faster version
from itertools import product
from collections import Counter
def e(b):
    if len(b) == 1: return True
    for k in range(1, len(b)):
        c = Counter(b[i:i+k] for i in range(len(b)-k+1))
        if len(c) < 2**k and max(c.values()) > 1: return False
        elif max(c.values()) - min(c.values()) > 1: return False
    return True
def a(n): return 2*sum(e("0"+"".join(b)) for b in product("01", repeat=n-1))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Jul 25 2021

Crossrefs

Sequence in context: A343187 A009279 A059943 * A112336 A028390 A036500

Adjacent sequences: A264692 A264693 A264694 * A264696 A264697 A264698

Keyword

nonn,more

Author

Jeffrey Shallit, Nov 21 2015

Extensions

a(15) from Jeffrey Shallit, Nov 26 2015

a(16)-a(20) from Jeffrey Shallit, Feb 25 2018

a(21)-a(36) from Michael S. Branicky, Jul 25 2021

Status

approved