3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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\}$. $\endgroup$
    – mathochist
    Sep 7 '18 at 23:59
  • $\begingroup$ 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. $\endgroup$
    – Tengu
    Sep 8 '18 at 0:01
  • $\begingroup$ 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. $\endgroup$
    – mathochist
    Sep 8 '18 at 0:05
  • 1
    $\begingroup$ Link to the paper: jstor.org/stable/2690690?seq=1#metadata_info_tab_contents $\endgroup$
    – RockyRock
    Sep 11 '18 at 14:39
  • 1
    $\begingroup$ Your edited question is interesting. Unfortunately, I haven't found a good answer. I certainly need some more time to think about it. $\endgroup$
    – Tengu
    Sep 11 '18 at 23:41

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.