[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