How many ways to partition $n$ elements into two nonempty subsets? 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\}$.
 A: 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 $$
A: 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$.
A: 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$ )
