Finding the number of Partitions in a set into two subsets

Question

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?

Answer 1

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.

Answer 2

Choose one subset of $A$. The other subset in the partition is everything else. You then need to divide by $2$ because you could have chosen the other subset first and gotten the original subset as the everything else.

Answer 3

Suppose your set is $\{ 1,3,8\}$ Our partitions are $$\{\{1\},\{3,8\}\}\\ \{\{3\},\{1,8\}\}\\ \{\{8\},\{1,3\}\} $$

Each partition has 2 disjoint sets whose union is the original set.

Answer 4

I think that you need S(n, 2)=2^(n-1)+1, assuming that both sub-sets are required to not be empty.

For example n=3 gives 3 subsets (i.e {{1,2}, {3}}, {{1,3}, {2}}, and {{2,3}, {1}}).

There is a recurrence relation: S(n+1,2)=2*S(n,2)+1

This can be interpreted as saying that when you and a new element, then this element can be put in any of the previous sub-sets, or in a sub-set by itself. So, for S(4,2) you would have: {{1,2,4}, {3}}, {{1,3,4}, {2}}, and {{2,3,4}, {1}}) as well as {{1,2}, {3,4}}, {{1,3}, {2,4}}, and {{2,3}, {1,4}}), and as well as {{1,2,3}, {4}}

So S(4,2)=2*3+1=7 etc.

In general, there is a recurrence relation: S(n+1,k)=kS(n,k)+S(n,k-1) for k between 1 and n. This can be interpreted in the same way as the example where k=2. [and the sum over all k for any fixed n is the number of partitions, which is known as Bell's number]