# Partition binary strings, subject to a restriction

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.

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
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.