3
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tsing Shi Tao May 26 '18 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.