# [Math] Number of Possible Pairs from Two Sets

combinatoricsdiscrete mathematicssolution-verification

The Question:

We have 18 distinct gadgets and 22 distinct widgets. We want to pick five
pairs, each with one gadget and with one widget. In how many different
ways can the five pairs be chosen?

There are $18 \choose 5$ ways to pick the gadgets and $22 \choose 5$ ways to pick the widgets. Then we want to find all the ways in which we can pair up the picked gadgets and widgets. Let's take a fixed gadget. We can pair it with five widgets. For the next gadget, we can pair it with four widgets, etc. So there are $5!$ ways to pair the gadgets with widgets, and $5$ ways to choose the way in which we order the gadgets to begin with.

So the total number of ways is $5! \cdot 5 \cdot {18 \choose 5} \cdot {22 \choose 5}$.

Does that look right? I'm sceptical of my answer.

You’re right to be skeptical: you have an extra factor of $5$.
There are indeed $\binom{18}5\binom{22}5$ ways to pick $5$ gadgets and $5$ widgets. Now order the gadgets arbitrarily; there are $5!$ ways to line up the widgets next to them, so there are $5!\binom{18}5\binom{22}5$ ways to form the $5$ pairs. Once you establish some fixed ordering of the gadgets, you’re done with them: there is no $5$-way choice involved. The point is that it doesn’t actually matter what ordering of the gadgets you use: each one leads to the same $5!$ possible pairings.
As a check, there are $\binom{18}5$ ways to pick $5$ gadgets. Line them up. There are $22$ ways to pick a widget for the first gadget, $21$ ways to pick a widget for the second gadget, and so on, for a total of
$$\binom{18}5\cdot22\cdot21\cdot20\cdot19\cdot18=\binom{18}5\cdot\frac{22!}{17!}=\binom{18}5\binom{22}55!\;.$$