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
  • 2
    $\begingroup$ Yes. There are $2^n$ unordered pairs of subsets where one of the subsets is the empty set. $\endgroup$ Jan 24 '17 at 13:53
  • $\begingroup$ I'm getting the same result as yours. See my answer. $\endgroup$ 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.

$\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.

$\endgroup$
3
  • $\begingroup$ @MarkusScheuer fixed mistake. $\endgroup$ Jan 25 '17 at 4:52
  • $\begingroup$ Well done! (+1) $\endgroup$
    – epi163sqrt
    Jan 25 '17 at 5:26
  • $\begingroup$ @shauryagupta Thanks for confirming :-) $\endgroup$ 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.

$\endgroup$
8
  • $\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$
    – epi163sqrt
    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$
    – epi163sqrt
    Jan 24 '17 at 21:41
  • 1
    $\begingroup$ Yup! In fact OPs formula is correct. :-) $\endgroup$
    – epi163sqrt
    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

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .