1
$\begingroup$

Say we have a set S with elements $s_1,s_2,...,s_N$. I'm looking for the number of ways of making M subsets of S such that the union of the subsets is S, that is: $S_1 \cup S_2 \cup ... \cup S_M = S$, where each of the $S_i$ subsets is made up of only elements from S but are not necessarily disjoint (i.e. they can have 0 to all shared elements).


I can derive the condition for M=2 but want to generalize to any M. For M=2, the number of ways can be derived as follows:

A given $s_i$ must be in at least one of the subsets $S_1$ and $S_2$, so it can either be in $S_1$ only, in $S_2$ only, or in both $S_1$ and $S_2$. Therefore, for every $s_i$, there are 3 possibilities, so if the set $S$ has N elements, then there are $3^N$ ways of creating the subsets. However, this result is double counting because e.g. assigning $s_1$ to $S_1$ and then $s_2,...,s_N$ to $S_2$ is the same as assigning $s_1$ to $S_2$ and then $s_2,...,s_N$ to $S_1$. However, there is one case that is NOT double counted, which is $S_1=S_2=S$. So, before dividing by 2, we must subtract 1. And then we add back that 1 at the end. So, for M=2, we have:

Number of ways = $\frac{3^N - 1}{2}+1$

How can I generalize this to arbitrary M? I think I can replace the 3^N in the above equation with $$(\sum_{i=1}^{M}\binom{M}{i})^N$$ but am not sure how to deal with subtracting out the over counting.

$\endgroup$
  • $\begingroup$ Why do you divide by $2$ ? $\endgroup$ – Jorge Fernández Hidalgo Sep 26 '16 at 0:15
  • $\begingroup$ Oh, you count permutations of $S_1,S_2\dots S_n$ as equal? That makes the problem a lot tougher. $\endgroup$ – Jorge Fernández Hidalgo Sep 26 '16 at 0:16
1
$\begingroup$

So you want to find the number of ways to select subsets $S_1,S_2\dots S_M$ of $\{1,2,\dots N\}$ so that $S_1\cup S_2\cup \dots \cup S_M=\{1,2,\dots N\}$.

What we do is flip the problem around (this works sometimes in combinatorics),instead of selecting each subset, for each element $j$ in $\{1,2,\dots N\}$ we select which subsets are going to contain $j$.

Clearly there are $2^M-1$ options (because at least one of the subsets must contain $j$). Since we must make this choice for every $j\in \{1,2,\dots N\}$ we conclude there are $(2^M-1)^N$ ways to select subsets $S_1,S_2\dots S_M$ of $\{1,2,3\dots N\}$ such that their union is all of $\{1,2,3\dots N\}$

$\endgroup$
  • $\begingroup$ Thanks, true, we can rewrite the $(\sum_{i=1}^{M}\binom{M}{i})^N$ as $(2^M-1)^N$ which could be helpful, but how can we address the issue of overcounting? When M=2, it's easy because a particular way is only either double counted or single counted. But in the M>2 case, the difficulty is that something could be single counted, double counted, triple counted, etc., and the number of times it's overcounted depends on which M choose i it corresponds to. This is the part that I'm not so clear how to fix. $\endgroup$ – sambajetson Sep 26 '16 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.