# Combinatorics on subset selections

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.

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

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\}$
• 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. – sambajetson Sep 26 '16 at 17:26