1
$\begingroup$

How can we find the total number of ways in which we can divide $n$ elements into two subsets such that none of them are empty and the union of both sets should be equal to the whole set?

Eg. If $S=\{1,2,3\}$, the answer can be $A=\{1,2\}$, $B=\{3\}$ or $A = \{1,3\}$ and $B=\{2\}$ or $A=\{2,3\}$ and $B=\{1\}$.

$\endgroup$
3
$\begingroup$

Use the power set of $S$. For example when $S=\{1,2,3\}$ the power set is

$$ \mathcal P(S) = \Big\{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \Big\}$$

Choosing a pair $(A,B)$ of subsets such that $A\cup B=S$ and $A$ and $B$ are nonempty is equivalent to choosing any subset $A$ (besides the empty set and $S$), then let $B$ be the complement of $A$:

$$B = \{ x\in S : x\notin A \} $$

Since the power set has $2^n$ elements, there are $2^n - 2$ ways to choose the set $A$ (we excluded sets $\emptyset$ and $S$). However, we have double-counted, since for example we counted both $A=\{1,2\}$, $B=\{3\}$ and $A=\{3\}$, $B=\{1,2\}$ separately, when really they are the same. Thus we divide by $2$, so the answer is

$$ \frac{2^n - 2}{2} = 2^{n-1} - 1 $$

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

Well, the number you are searching is the Stirling number of the 2nd kind.

Let $n,k\geq 1$. Define $S(n,k)$ as the number of partitions of an $n$-element set such that each partition consists of $k$ elements (blocks).

These numbers can be computed recursively.

$S(n,k)=0$ if $k>n$.

$S(n,1) = 1$ and $S(n,n)=1$.

$S(n,k) = S(n − 1, k − 1) + k · S(n − 1, k)$ if $1<k<n$.

Your question asks for $S(n,2)$ which is $S(n,2) = S(n-1,1) + 2\cdot S(n-1,2)$. By induction, $S(n,2)=2^{n-1}-1$.

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

Choosing elements of one group determines the other group as well. So, the total number of ways needs summing over all possible ways of "choosing" elements of one group:

For any general $n$: $$\dfrac{{n \choose 1} + {n \choose 2} + \dots + {n \choose n - 1}}{2} = \dfrac{\sum\limits_{i = 0}^n {n \choose i} - {n \choose 0} - {n \choose n}}{2} = \dfrac{2^n - 2}{2} = 2^{n-1} - 1$$

We divided by $2$ because forming one group simultaneously generates the other, so we counted everything twice (eg. think how you counted a way for choosing $1$ element out of $4$ to make group $1$ and again counted it when considering a way of choosing $3$ elements to make group $2$ )

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ why -2 in above expression $\endgroup$ – akashking Sep 1 '19 at 8:21
  • $\begingroup$ @akashking Since we need to subtract $^n C _0 ( = 1)$ and $^n C _n ( = 1)$ $\endgroup$ – ab123 Sep 1 '19 at 8:23
  • $\begingroup$ For a mental image, think about cutting a pascal triangle row exactly in half and removing the first term. This is the same as taking the whole pascal row, removing the first and last term, and dividing by two .When I say exactly in half, I mean that if n is even, the term that falls exactly in the middle is also cut in half $\endgroup$ – Francisco José Letterio Sep 2 '19 at 17:51
  • $\begingroup$ also, @ab123 not that if n is even, then the term ${n \choose \lfloor n/2 \rfloor}$ should be divided by $2!$, because it's symmetric. Your equality is ok only for odd n $\endgroup$ – Francisco José Letterio Sep 2 '19 at 17:53
  • $\begingroup$ @FranciscoJoséLetterio edited for general $n$ $\endgroup$ – ab123 Sep 3 '19 at 14:27

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.