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

Question

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?

Thank you for your help.

Answer 1

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.