# Counting (and enumerating) pairs

Suppose you have 4 tickets to a gala event to be distributed to your friends.

Let's say you have 6 male friends and 7 female friends. Each ticket requires a male-female couple.

How do you count in how many ways you can match your friends to the 4 tickets? How would you enumerate all possible combinations?

-

The answer depends on whether or not the tickets are numbered.

Suppose that each ticket simply says: "Admit two people, as long as they are a male/female pair" (backward, and illegal where I live). We can proceed symmetrically as follows.

The females can be chosen in $\binom{7}{4}$ ways. For each choice of females, the males can be chosen in $\binom{6}{4}$ ways, for a total of $\binom{7}{4}\binom{6}{4}$ ways.

Now we need to do the pairing. The females line up in order of (say) height, or student number. The first female picks her partner. She has $4$ choices. Then the next female chooses. For every way that the first female chose, there are $3$ ways for the second female to choose, and so on. So once the people have been chosen, for each choice of people there are $4!$ ways to do the pairing, for a total of $$\binom{7}{3}\binom{6}{4}(4!).$$

An alternate way to do the problem is to note that the females can be chosen in $\binom{7}{4}$ ways. Line them up in order of height, and let the females, in order, make their choices. The tallest female has $6$ choices, for each such choice the second tallest female has $5$, and so on, for a total of $$\binom{7}{4}(6)(5)(4)(3).$$

Enumerating is unpleasant. Give the females names, such as A, B, C, D, E, F, G, H and also the males, say U, V, W, X, Y, Z. A sensible way of listing the choices is to list the females who were chosen in alphabetic order, with each female name followed by the name of the male she is partnered with. For example, the "word" BZDUEXGY indicates that B is partnered with Z, D with U, and so on. Now enumerate all $8$-letter words of the right shape, in lexicographic (dictionary) order.

Remark: If the tickets are numbered, we just multiply the answer above by $4!$. Alternately, line up the tickets in ticket number order. For the first ticket, there are $(7)(6)$ ways to choose the couple that will get it. For each such choice, there are $(6)(5)$ ways to choose the couple that will get the second ticket, and so on, for a total of $$(7)(6)(6)(5)(5)(4)(4)(3).\qquad$$ From this, if we wish, we can derive the answer for unnumbered tickets. For every unnumbered ticket possibility, there are $4!$ numbered ticket possibilities, so we simply divide the above expression by $4!$.

-
Very nice answer. Now, for a curved ball, what if there are feuds in the group. For example, A will only go out with U or V; B,C,D,E will go with anybody, and F,G and H will only pair up with X,Y or Z... how does that complicate matters? – Padu Merloti Feb 21 '12 at 19:08
@Padu Merloti: It complicates things a lot. We have to break things up into cases in a suitable way, for we lose the smoothness of "for every choice of $\dots$, there are $n$ choices for $\dots$." So we have to break things into cases, and/or use Inclusion/Exclusion. Can be done, but the resulting expressions are potentially quite messy. – André Nicolas Feb 21 '12 at 19:21

There are many reasonably efficient ways to do the enumeration. For example, you could argue that there are $\binom62$ ways to choose the two men who do not get tickets, $\binom73$ ways to choose the three women who do not get tickets, and then $4!$ ways to pair up the remaining four men and four women, for a total of $$\binom62\binom734!=15\cdot35\cdot24=12600\;.$$

Or you could argue that there are $\binom64\binom74$ ways to choose the four men and four women to get tickets and then $4!$ ways to pair them up, for a total of $$\binom64\binom744!=15\cdot35\cdot24=12600\;.$$

(Of course since $\binom62=\binom64$ and $\binom73=\binom74$, it’s hardly surprising that these both work!)

You could also reason that there are $6$ ways to pick the first man to get a ticket, $7$ ways to pick his partner, $5$ ways to pick the second luck man,$6$ ways to pick his partner, and so on, making a total of $$6\cdot7\cdot5\cdot6\cdot4\cdot5\cdot3\cdot4\;,$$ but then you’d have to realize that you’ve actually counted every possible set of four couples $4!$ times, once for each of the $4!$ orders in which you could have picked the same set of four couples. Thus, the correct answer by this approach is $$\frac{6\cdot7\cdot5\cdot6\cdot4\cdot5\cdot3\cdot4}{4!}\;,$$ which is of course the same $12600$ as before.

-
+1 for explanatory answer. – user21436 Feb 21 '12 at 1:17

(This answer goes into a little more detail than Kannappan's and Brian's, in case you don't know what binomial coefficients, etc, are. Also, it includes the obvious My Little Pony reference. This question was a reference to Episode 3, "The Ticket Master", right?)

First, let's choose which of the $7$ female friends will get to go to the Grand Galloping Gala. There's $7$ ways to choose the first lucky friend, $6$ ways to choose the next one, $5$ ways to choose the third one, and finally $4$ ways to choose the last one. That's a total of $7 \times 6 \times 5 \times 4 = 840$ ways to choose the female attendees in order.

Now, let's choose their pairs. There's $6$ possible male pairs for the first filly, $5$ possible second pairs, $4$ possible third pairs, and $3$ possible last ones. That's $6 \times 5 \times 4 \times 3 = 360$ ways to choose the male pairs in order.

However! We don't care which order we pick the couples in; that is, we don't care who gets picked first and who gets picked second. There are $4 \times 3 \times 2 \times 1 = 24$ ways to choose $4$ specified couple in any order ($4$ possible first couples, $3$ second, etc...), so using the previous two paragraphs, each assignment of tickets will get counted $24$ times over.

Therefore, the final answer is $840 \times 360 / 24 = 12600$ ways.

As you can see, this is far too many to enumerate directly; however, if you had a spare 7 hours and were up for the task, the easiest way would be to organize by couple (i.e. first list the ways where Rainbow Dash gets to go with Braeburn, then the ways where she gets to go with Big Macintosh, then the ways where she doesn't go at all, etc...)

Of course, this answer all assumes that the gala-goers don't take the third option that Twilight took in the original episode.

-
Obligatory warning: the links go to TvTropes. Follow them iff you want to sit up later and say, "How is it already 2 AM, and why do I have 47 tabs open?" – Lopsy Feb 21 '12 at 1:07
I have 62 tabs open at the moment even without TVTropes (to which I am in any case mostly immune). Most of them are MSE. But as an old Pomona alumnus I definitely approve of the use of 47 here! – Brian M. Scott Feb 21 '12 at 1:12

For four tickets, you need $4$ male friends. So, there are $\displaystyle \binom 6 4$ ways of choosing $4$ male friends. Again, for four tickets, $4$ female friends are chosen in $\displaystyle \binom 7 4$. Now, for the pairing, it can be done in $4!$ ways. $$\binom 64 \binom 744! ~~\text{ ways}$$

-
@BrianM.Scott Corrected, Thank You. I had been thinking that something would get adjusted. While I reasoned out in an odd way I had written it previously, I was mistaken. MSE helps organise a lot. – user21436 Feb 21 '12 at 1:12
@Brian: I am not sure. Now you have $12600$ ways of choosing the four couples, I could see a case for $4!$ ways of matching the chosen couples to the tickets, i.e. $302400$ "ways you can match your friends to the 4 tickets" as in the question. – Henry Feb 21 '12 at 1:42
@Henry: I agree that there’s an interpretation for which the larger number is right; I just think that it’s sufficiently less likely to be the right one that it would need to be mentioned explicitly if one used it. – Brian M. Scott Feb 21 '12 at 1:44