login
A264695
Number of equidistributed binary strings of length n.
1
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
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
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