How to prove a property in the set partitions problem

Question

Let $S(m,n)$ denote the set of all partitions of $\{1,\ldots,m\}$ into exactly $n$ non-empty subsets. How to prove that $S(m,2) = 2^n$ for all integer $m \geq 1$ ?

Answer 1

I'll assume you meant $S(m,2) = 2^m$ where you wrote $S(m,2) = 2^n.$

In how many ways can one partition a set of $4$ things into $2$ non-empty subsets?

\begin{align} & 1/234 \\ & 2/134 \\ & 3/124 \\ & 4/123 \\ & 12/34 \\ & 13/24 \\ & 14/23 \end{align} There are seven ways. That's less than $2^4=16.$ So the proposed proposition is false.

One thing that may make someone think it's true is that the number of subsets is $2^m,$ which in this case is $2^4=16,$ and then take each subset and its complement to form a partition. This overlooks two facts: $(1)$ Note that $12/34,$ the partition corresponding to the subset $\{1,2\},$ is not a different partition from the one corresponding to the subset $\{3,4\},$ and similarly for the other subsets of size $2,$ and the parition corresponding to $\{1\}$ is not different from that corresponding to $\{2,3,4\},$ although these are obviously different subset, and $(2)$ the empty set is one of the $2^4=16$ subsets but is not included in this enumeration of partitions.

Actually the number you need is $2^{n-1} -1.$ That can be seen as follows: There are $2^n$ subsets. Exclude the empty set and its complement, getting $2^n-2.$ Then observe that it takes two of the remaining sets to make a partition, so divide that by $2.$