Here is the problem:
Let A be a set with n elements. Find an expression for S(n, 2), the number of partitions of A into exactly two subsets. You can either start with the general recurrence for S(n, k), or count S(n, 2) directly.
I'm having trouble understanding what exactly it wants me to do. So far I know that it wants me to find an expression that gives the number of combinations of A into sets like (x, y). I got the equation: (n – 1) * 2 for number of partitions of A into two parts, but I don't know understand what the problem means by creating two subsets. What am I doing wrong?
Best Answer
First, the problem isn't actually asking you to divide up $A$ into sets with exactly two elements -- for something like $|A|=3$, this is impossible. Instead, what they want is to consider all the ways that $A=B\cup C$, where $B\cap C=\emptyset$.
So how can we approach this? Generally, we do it by induction if we're going to do it directly. Or, if you have the recurrence for $S(n,k)$, you may as well use that.