2
$\begingroup$

Let $S=\{1,2,3,...,10\}$ . How many unordered pairs $A$ and $B$ are there, where $A$ and $B$ are non empty disjoint subsets of $S$ ?

Any approach for such questions ?


Total number of unordered pairs of disjoint subsets of S

This is one related question, but using the same approach as given in the above link, I am getting

$\left(\frac{3^n - 1}{2} + 1 \right) - 2^n$ for my question


But, I need a confirmation here ?

$\endgroup$
  • 2
    $\begingroup$ Yes. There are $2^n$ unordered pairs of subsets where one of the subsets is the empty set. $\endgroup$ – Callus - Reinstate Monica Jan 24 '17 at 13:53
  • $\begingroup$ I'm getting the same result as yours. See my answer. $\endgroup$ – Shaurya Gupta Jan 25 '17 at 4:55
1
$\begingroup$

We reformulate the problem somewhat and verify OPs formula \begin{align*} \frac{3^n - 1}{2} + 1 - 2^n \end{align*} by showing that the question asks in fact for famous numbers.

We consider the set $S_n=\{1,2,3,\ldots,n\}$ and ask for the number of non-empty partitions of the set \begin{align*} S_{n+1}=S_n\cup\{n+1\} \end{align*} into three non-empty sets.

Note, this number is the same as OPs question is asking for, because whenever we consider an unordered pair $(A,B)$ with $A,B\subset S_n, A\cap B=\emptyset$ we have one of two cases:

  • $A\cup B=S_n$: This corresponds to the partition $S_{n+1}=A\cup B\cup\{n+1\}$ and vice versa.

  • $A\cup B \ne S_n$: This corresponds to the partition $S_{n+1}=A\cup B\cup \left(S_{n+1}\setminus (A\cup B)\right)$ and vice versa.

The number of ways of partitioning a set of $n$ elements into $k$ nonempty sets is called Stirling number of the second kind and denoted with ${n\brace k}$. They admit the representation \begin{align*} {n\brace k}=\frac{1}{k!}\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^n \end{align*}

Here we are looking for ${n+1\brace 3}$, the number of ways of partitioning a set of $n+1$ elements into $3$ nonempty sets. We obtain for $n>0$: \begin{align*} {n+1\brace 3}&=\frac{1}{3!}\sum_{j=1}^3(-1)^{3-j}\binom{3}{j}j^{n+1}\\ &=\frac{1}{6}\left(\binom{3}{1}1^{n+1}-\binom{3}{2}2^{n+1}+\binom{3}{3}3^{n+1}\right)\\ &=\frac{1}{2}\left(3^{n}+1\right)-2^n \end{align*} which coincides with OPs result.

Note: The sequence $$\left({n\brace 3}\right)_{n\geq 0}=(0,0,0,1, 6, 25, 90, 301, 966, 3025, 9330, 28501,\ldots)$$ is archived in OEIS as A000392.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

First assume that we need ordered pairs $A$ and $B$, where $A$ and $B$ are disjoint subsets of $S$. For this, an element can either go to A or B or to neither of them. There are $3^n$ ways of doing this.

Now let's remove the case when A or B is empty.
Case 1: One is empty, other is not. There are $2 \times (2^n - 1)$ such cases.
Case 2: Both are empty: There is only $1$ such case. We need to remove these $ 2^{n+1} - 1 $ cases from $3^n$.

So we are left with $3^n - 2^{n+1} + 1$ possibilities.

But since we need unordered pairs of $A$ and $B$, we divide this by $2$ to get $\boxed{\frac{3^n + 1}{2} - 2^n}$.

One approach for solving such questions is to start with a broader case that has less restrictions and then apply restrictions on it.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @MarkusScheuer fixed mistake. $\endgroup$ – Shaurya Gupta Jan 25 '17 at 4:52
  • $\begingroup$ Well done! (+1) $\endgroup$ – Markus Scheuer Jan 25 '17 at 5:26
  • $\begingroup$ @shauryagupta Thanks for confirming :-) $\endgroup$ – Jon Garrick Jan 25 '17 at 6:02
1
$\begingroup$

Here is a proof of your second question.

Consider a set $E$ containing $n$ elements ($\mathrm{card}(E)=n$) and $q=\mathrm{card}(F)$ where :

$$F=\{(A,B)\in\mathcal{P}(E)^2;\,A\cap B=\emptyset\}$$

Since the single subset $A$ of $E$ verifying $A\cap A=\emptyset$ is $\emptyset$ itself, the answer to your question will be $1+\frac{q-1}{2}$.

Since the elements of $F$ can be classified according to their cardinal, we have :

$$F=\bigcup_{k=0}^nF_k\qquad\mathrm{where}\quad F_k=\{(A,B)\in\mathcal{P}_k(E)^2;\,A\cap B=\emptyset\}$$

where $\mathcal{P}_k(E)$ denotes the set of all subsets of $E$ whose cardinal is $k$.

This is the union of pairwise disjoint sets, and therefore :

$$q=\sum_{k=0}^n\mathrm{card}(F_k)$$

We see that $\mathrm{card}(F_k)={n\choose k}2^{n-k}$. Thus :

$$q=\sum_{k=0}^n{n\choose k}2^{n-k}=3^n$$

Finally, there are $1+\frac{3^n-1}{2}$ unordered pairs of disjoint subsets.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It seems your formula should be revised. When setting $n=2$ it produces $5$ instead of $1$, when setting $n=3$ it produces $14$ instead of $6$. $\endgroup$ – Markus Scheuer Jan 24 '17 at 21:22
  • $\begingroup$ @Markus Scheuer : I don't see what's wrong with the case $n=2$. Consider $E=\{a,b\}$; here are the $5$ unordered pairs of disjoint subsets of $E$ : $\{\emptyset,\emptyset\}$, $\{\emptyset,\{a\}\}$, $\{\emptyset,\{b\}\}$, $\{\emptyset,\{a,b\}\}$, $\{\{a\},\{b\}\}$. $\endgroup$ – Adren Jan 24 '17 at 21:35
  • 1
    $\begingroup$ We are looking for non-empty subsets $A,B$. Here we consider $\{\{a\},\{b\}\}$ as the only solution. $\endgroup$ – Markus Scheuer Jan 24 '17 at 21:41
  • 1
    $\begingroup$ Yup! In fact OPs formula is correct. :-) $\endgroup$ – Markus Scheuer Jan 24 '17 at 21:52
  • 1
    $\begingroup$ @MarkusScheuer, Jon Garrick - In didn't meant that the OP was wrong :-) Just proposed a proof of what I had understood. $\endgroup$ – Adren Jan 25 '17 at 6:04

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.