# Is there a name for the set of “unique” combinations of the powerset of $2^n$ modulo permutation?

I was studying an algorithm on $$k$$-combinations of $$n$$-bit strings and realised that, my brute-force approach would spend lots of time on "structurally equivalent" bitstring combinations, that could be transformed into another bitstring combination for which a solution had already been computed by permuting bit-positions.

For readability I'll denote $$n$$-bit strings as elements of $$2^{\{0,\dots,n-1\}}$$, e.g. 1011 $$= \{0,1,3\}$$

Then, for $$n=3$$ and $$k=2$$, the only "unique" combinations are the following: $$\{\emptyset, \{0\}\}\\ \{\emptyset, \{0, 1\}\}\\ \{\emptyset, \{0, 1, 2\}\}\\ \{\{0\}, \{1\}\}\\ \{\{0\}, \{0, 1\}\}\\ \{\{0\}, \{1, 2\}\}\\ \{\{0\}, \{0, 1, 2\}\}\\ \{\{0, 1\}, \{0, 2\}\}\\ \{\{0, 1\}, \{0, 1, 2\}\}\\$$ $$\{\{0\}, \{0, 2\}\}$$ is not "unique", as it can be mapped to $$\{\{0\}, \{0, 1\}\}$$ by permuting $$1$$ and $$2$$.

Since it seems to me that others should have had similar problems before:

Is there a name for this subset of combinations?

P.S.: My best guess at a formal definition would be a set $$X$$, such that forall $$A \in {2^n}^k$$ ($$k$$-combinations of the powerset of $$\{0,\dots,n-1\}$$) $$A \in X \Leftrightarrow A = \min\limits_\sigma(\sigma(A))$$ i.e., $$A$$ is in $$X$$, iff it is the minimal element in the set of all pictures over all permutations (lifting permutations to sets of sets and taking the minimum over the lexicographical ordering).

• You should also include the empty set in your possibilities as it represents the string with all bits $0$. Another possibility would then be $\{\emptyset,\{0\}\}$ and you can pair it with sets with $2$ or $3$ members. – Ross Millikan Oct 1 '18 at 16:52
• Thanks, you are right. In the specific application I was interested in I was only concerned with bitstrings with at least one bit set, so I forgot to include those. I have updated the question accordingly. – jk. Oct 2 '18 at 7:27

## 1 Answer

You can characterize your pairs by giving the following:

1. Number of elements in the first set, $$f$$
2. Number of elements in the second set, $$s$$
3. Number of elements in the intersection of the two sets, $$t$$

coupled with the requirement that the first set have no more elements than the second. Because you run out of distinct elements you must have $$t \ge f+s-n$$. The first set consists of the lowest $$f$$ numbers, $$0$$ through $$f-1$$. The second set consists of the lowest $$t$$ numbers and then the numbers from $$f$$ through $$f+s-1-t$$. If $$k$$ gets larger you can extend the number of elements list easily but the number of overlaps grows as $$2^k-k-1$$. I don't know of a name for it.