[seqfan] All k-bit substrings of a binary string

rhhardin at att.net rhhardin at att.net
Tue Aug 11 19:25:52 CEST 2009

Empirical, but not producing a useful series contribution

How many binary strings of length N are there that have an equal number of
every possible k-bit substring?

ie if k=2, how many strings with an equal number of 00 01 10 and 11's.

Considering only N>k, it's nonzero only for N = n*2^k + k - 1, n=1..

and the number a(n,k) is, via numerology, ((2*n)!/(n!^2))^(2^(k-1))

that is, 1 2 4 8 ... powers of A000984.

It's perhaps obvious for k=1.

rhhardin at mindspring.com
rhhardin at att.net (either)

More information about the SeqFan mailing list