I do some ex for preparing discrete mathematics exam, i get stuck in one problem, anyone could help me?
How many ways we can partition set {1,2,…,9} into subsets of size 2
and 5?
anyway, some tutorials for solving such a question…
Edit: Like always Scott is Right…
Best Answer
A partition of $\{1,\ldots,9\}$ into sets of sizes $2$ and $5$ must contain two sets of size $2$ and one of size $5$: no other combination of $2$’s and $5$’s adds up to $9$. Thus, the question boils down to determining how many ways there are to pick a $5$-element subset of $\{1,\ldots,9\}$ and then split the remaining $4$ elements into two $2$-element subsets.
The first part of that is easy: a $9$-element set has $\binom95$ $5$-element subsets, so there are $\binom95=126$ ways to choose the $5$-element piece of our partition. The second step step is just a little trickier. You might be tempted to think that there are $\binom42=6$ ways to choose $2$ of the remaining $4$ elements for one of the $2$-element sets, leaving the other $2$ to be the other $2$-element set, but that’s not quite right. Suppose that your $5$-element set is $\{1,3,5,7,9\}$, so you’re making up two $2$-element sets from $\{2,4,6,8\}$. You might pick $\{2,6\}$ for one of your $2$-element sets, leaving $\{4,8\}$ for the other. Unfortunately, you might equally well pick $\{4,8\}$, leaving $\{2,6\}$ for the other. That figure of $\binom42$ counts these two choices separately, even though they produce the same two $2$-element sets.
You can avoid this in at least two ways. One is to notice that each pair of $2$-element sets is being counted twice, once for each of the two sets, so that instead of getting $\binom42$ pairs of $2$-element sets, we’re getting only half that many, i.e., $3$. The other is to employ a trick that’s useful quite often. No matter what $4$ elements remain after you’ve picked the $5$-element set, you can list them in numerical order; call them $n_1<n_2<n_3<n_4$. When we split them into two pairs, we have to pair one of the numbers $n_2,n_3$, and $n_4$ with the smallest one, $n_1$; obviously we can do that in $3$ ways. And once we’ve done that, there’s no more choosing to be done: the two numbers that we didn’t pair with $n_1$ form the last $2$-element set.
One way or another, we reach the final result: there are
$$\binom95\cdot3=126\cdot3=378$$
such partitions.