# Number of ways to cover a discrete set of $n$ elements into $p$ subsets with $q$ overlaps

I am looking for the general expression for the number of ways to cover a set of $n$ elements into $p$ non-empty subsets sharing exactly $q$ elements (overlaps).

As an example, if $n=3$, one way to cover the set $[3]=\{1,2,3\}$ with $p=2$ subsets could be: $A_1=\{1,2\}$ and $A_2=\{2,3\}$, where there is $q=1$ overlap corresponding to the element $2$. The number of overlaps is counted as the number of times, elements (not necessarily distinct) are used more than once.

For example, in the case where $n=4$, $p=3$ and $q=2$ a possible covering of the set $[4]$ could be given by: $A_1=\{1,2\}$, $A_2=\{2,3\}$ and $A_3=\{3,4\}$.

In this case the subsets don't intersect $\cap^{3}_{i=1} A_i = \emptyset$, but the elements $2$ and $3$ are shared once each, hence counting for $q=2$ overlaps.

Therefore, there are some covering constraints:

1. The number of covers has to be less than the number of elements in $[n]$, i.e. $p \leq n$

2. The number of overlaps is bounded such that $0 \leq q \leq n(p-1)$, with $q=n(p-1)$ corresponding to $A_i = [n]$ for all $i \in \{1,\ldots,p\}$.

3. All elements of the initial set are used at least once, i.e. $\cup^{p}_{i=1} A_i = [n]$

4. No subset is empty, i.e. for all $i \in \{1,\ldots,p\}$, $A_i \neq \emptyset$

In the particular case where the subsets do not overlap i.e. $q=0$, this number is given by the Stirling number of the second kind $S(n,p)$.

What about the general case with a fixed number $q \geq 0$ of overlaps?

This is for $q \ge 1$:

Say you have $p$ subsets $A_1, \ldots, A_p$ of $[n]=\{1,2, \ldots, n\}$ so $B=\bigcap_{i=1}^p A_i$ and $|B|=q$. There are $\binom{n}{q}$ ways choose elements for $B$. We then consider $C_i=A_i \setminus B$ for $1 \le i \le p$ then $C_i$ are pairwise disjoint and that $\bigcup_{i=1}^p C_i=[n]\setminus B$. Observe that here at most one of the $C_i$'s can be empty so we consider two cases:

If one of the $C_i$ is empty. It suffices to partition set $[n]\setminus B$ of size $n-q$ into $p-1$ subsets which is essentially $S(n-q,p-1)$.

If no $C_i$ is empty then it suffices to partition set $[n] \setminus B$ into $p$ subsets which will give $S(n-q,p)$.

Thus, the final answer is $\binom{n}{q} \left[ S(n-q,p-1)+S(n-q,p) \right]$.

For example, if $n=3,q=2,p=2$ gives $\binom{3}{2}(S(1,2)+S(1,1))=3$ which corresponds to $\{\{1,2,3\},\{1,2\}\},\{\{1,2,3\},\{2,3\}\}$ and $\{\{1,2,3\},\{1,3\}\}$.

PS. Usually the word partition refers to ways of dividing a set into non-empty pairwise disjoint subsets so when we refer to partition into some subsets, it is automatically understood that the subsets are pairwise disjoint and their union is the set that we want to partition.

• If I'm understanding this correctly, multiple $C_i$ can be empty, for example with $A_1 = \{1\}, A_2 = \{1\}, A_3 = \{2,3\}$. Sep 7 '18 at 23:59
• But that would imply multiple $A_i$, which I don't think is what the OP wanted. In particular, we cannot count this because we can take as many $A_1$ as we want. Sep 8 '18 at 0:01
• I don't see anything suggesting that case is not counted. If you still object to this, then consider $A_1 = \{1,2\}, A_2 = \{2,3\}, A_3 = \{1,3\}$ instead. Sep 8 '18 at 0:05