|
%I #38 Jul 25 2021 20:42:06
%S 2,2,6,4,4,12,34,20,16,8,68,100,144,314,668,360,288,128,192,400,608,
%T 2320,8816,9408,9912,6912,38204,37864,52464,108608,209664,106368,
%U 79360,32768,49152,16384
%N Number of equidistributed binary strings of length n.
%C 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.
%C a(n) is even by symmetry. - _Michael S. Branicky_, Jul 25 2021
%H Michael S. Branicky, <a href="/A264695/a264695.txt">Python program</a>
%H A. Carpi and A. de Luca, <a href="https://doi.org/10.1016/S0196-8858(03)00057-5">Uniform words</a>, Advances in Applied Mathematics, 32 (2004), 485-522.
%H Teturo Kamae and Yu-Mei Xue, <a href="http://www14.plala.or.jp/kamae/RandomnessCriterion.pdf">An Easy Criterion for Randomness</a>, Sankhya: The Indian Journal of Statistics, 2015, Volume 77-A, Part 1, pp. 126-152, DOI:10.1007/s13171-014-0054-3.
%o (Python) # see links for faster version
%o from itertools import product
%o from collections import Counter
%o def e(b):
%o if len(b) == 1: return True
%o for k in range(1, len(b)):
%o c = Counter(b[i:i+k] for i in range(len(b)-k+1))
%o if len(c) < 2**k and max(c.values()) > 1: return False
%o elif max(c.values()) - min(c.values()) > 1: return False
%o return True
%o def a(n): return 2*sum(e("0"+"".join(b)) for b in product("01", repeat=n-1))
%o print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Jul 25 2021
%K nonn,more
%O 1,1
%A _Jeffrey Shallit_, Nov 21 2015
%E a(15) from _Jeffrey Shallit_, Nov 26 2015
%E a(16)-a(20) from _Jeffrey Shallit_, Feb 25 2018
%E a(21)-a(36) from _Michael S. Branicky_, Jul 25 2021
|
