# Number of pairwise disjoint subsets of size $k$ of a set of size $n$.

I've been reading about combinatorics recently and have met the problem of choosing pairwise disjoint subsets of a set of size $n$.

I know the number of subsets of size $k$ of a set of size $n$ is given by the binomial coefficient ${n}\choose{k}$. So far I've read a bit about Stirling numbers of the second kind on Wikipedia and have seen a few answers to in-context problems on here but I haven't been able to find a good description of a general formula for the number of pairwise disjoint subsets and at least an overview of where it comes from.

I'm not sure if I should ask this as a separate question, but an example problem that I've been thinking about and haven't found a good answer for online (I've only found similar problems) is this:

Consider a group of $n$ tennis/badminton players. How many games of doubles can be picked from these $n$?

So far I can see that the number of ways of picking $4$ people for the game is ${n}\choose{4}$. I think the next thing to do is calculate the number of disjoint subsets of size $2$ of these $4$ (since one person can't be on both sides of the net and so in more than one of the subsets). Intuitively I think this should be $3$ but I can't see how to calculate it.

If it helps in giving answers I'm a first year mathematics undergraduate.

Thanks for the help!

## 1 Answer

I'll provide my idea about why the answer should be $3$ to your example:

In your example, when you chosen two out of them, you implicitly chosen another two to be in the other team, so let's write down the formula for this part first

$(\textrm{choose two out of four into A team})\cdot(\textrm{implicitly choose another two into B team})$

$${4\choose2}\cdot{2\choose2}\ ,$$

But if I would understand your question right, e.g. say the four people are $a,b,c,d$, each of them, say $a$, will only care about whom will be his/her teammate, but he/she won't care about they will be assigned to which team(in this example only two, A and B), so team name doesn't matter.

Now the key is that

1. all teams are of the same size, i.e. two-member team.
2. we continuously choose players from the same group.

so the above formula will repeat. To correct this we divide it by $2!,$ since there are two teams, then your intuition is correct

$$(\textrm{ans. from the above})\cdot\frac{1}{2!}=3.$$

I'm not very familiar with Stirling number formula you may wait for others' answer.

Consider a group of n tennis/badminton players. How many games of doubles can be picked from these n?

If you just want to choose four out of $n$, then the answer could be

$${n\choose4}\cdot{4\choose2}{2\choose2}\cdot\frac{1}{2!}.$$

But if you would mean $n$ is a multiple of $4$ and want to consider all of them grouped into 2-2 pairs, then the answer is not this formula.

• Thanks for this answer. This is the kind of formula I was looking for and it was just the idea that we are dividing by repetitions of teams that I was missing. I also see that we don't need to consider disjoint subsets to answer this question. – Tsing Shi Tao May 26 '18 at 18:05