Partition binary strings, subject to a restriction

Question

I'm interested in counting the number of partitions of the space of binary strings of length $k$, subject to a condition. The condition is: strings with Hamming distance equal to $k$ can't be in the same partition element. For example, if $k = 2$, 01 and 10 can't be in the same partition element.

I've been looking at the literature and I haven't been able to find a resource for this. I've also been unable to generalize this from the simple $k=2$ and $k=3$ cases that I've been able to work out by enumeration.

Any pointers, suggestions or references are much appreciated. Thanks.

Answer 1

The strings with Hamming distance $k$ come in pairs. Thus we have $2^{k-1}$ conditions that these pairs be in separate parts. If $j$ particular conditions are violated, we can treat the $j$ pairs that are in the same part as single objects, so there are $B_{2^k-j}$ partitions that violate $j$ particular conditions. Then by inclusion-exclusion the desired count is

\begin{align} \sum_{j=0}^{2^{k-1}}(-1)^j\binom{2^{k-1}}jB_{2^k-j} &= \sum_{j=0}^{2^{k-1}}(-1)^j\binom{2^{k-1}}j\frac1{\mathrm e}\sum_{l=0}^\infty\frac{l^{2^k-j}}{l!} \\ &= \frac1{\mathrm e}\sum_{l=1}^\infty\frac{l^{2^k}\left(1-\frac1l\right)^{2^{k-1}}}{l!} \\ &= \frac1{\mathrm e}\sum_{l=2}^\infty\frac{(l(l-1))^{2^{k-1}}}{l!}\;. \end{align}

This is $a_{2^{k-1}}$, where $a_n$ is OEIS sequence A020556. The entry contains a lot of information about these numbers, which it refers to as "generalised Bell numbers". The counts for $k=2,3,4$ are $7,1657,3473600465$, respectively.