Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So what I'm thinking is $$ \binom{10}{2}\binom{8}{2} \ldots \binom{2}{2} $$

But that's far from what the answer is.

share|improve this question
    
Number of combinations of 2 from 10, divided by 2, since the conversation is order-independent. –  mbaitoff Feb 1 '13 at 7:32

3 Answers 3

up vote 5 down vote accepted

Presumably this is to be interpreted as asking for the number of different ways to pair up $10$ people. Imagine numbering them $1$ through $10$. There are $9$ choices for the person to be paired with Nr. $1$. Once that pair has been determined, find a partner for the lowest-numbered person remaining; that will be either Nr. $2$ or Nr. $3$, depending on who Nr. $1$’s partner is. Either way, there are $7$ possible choices for his partner, because $3$ people are out of the running: he himself, and the first pair. That gives us $9\cdot7$ ways to choose the first two pairs. Now find a partner for the lowest-numbered person remaining: there are $5$ available choices, since we have to exclude the first two pairs and the person for whom we’re finding a partner. Putting the pieces together, we can form the first three pairs in $9\cdot7\cdot5$ ways.

Can you finish the analysis from there?

Added: Judging by your calculation, you’re thinking of choosing a pair, then a pair from the remaining $8$, and so on. The problem is that you might choose the same set of $5$ pairs in $5!$ different orders, so you’re overcounting by a factor of $5!$. And indeed,

$$\binom{10}2\binom82\dots\binom22=\frac{10!}{2^5}=5\cdot9\cdot4\cdot7\cdot3\cdot5\cdot2\cdot3\cdot1\cdot1=5!(9\cdot7\cdot5\cdot3\cdot1)\;.$$

share|improve this answer
    
This is so much more intuitive than the textbook solution: $(10!/(2!^5))/5!$ What's the reasoning for how they got this expression? –  AlanH Feb 1 '13 at 7:36
1  
@Alan: Does the addition explain their calculation, or should I say a little more? –  Brian M. Scott Feb 1 '13 at 7:38
    
Yeah that explains it. Thanks for the intuitive explanation. –  AlanH Feb 1 '13 at 7:40
    
@Alan: You’re welcome! –  Brian M. Scott Feb 1 '13 at 7:40
1  
For the answer involving $10!$, we line up the people ($10!$ ways to do this) and pair first with second, third with fourth, and so on. But interchanging first and second and/or third and fourth, and so on, gives same teams, so we are overcounting by a factor of $2^5$. So we divide by $2^5$ to compensate. Also, the same set of pairs can be selected in $5!$ ways, so need to further divide by $5!$. –  André Nicolas Feb 1 '13 at 8:19

We assume that a telephone conversations involve two people. So the question comes down to finding how to divide a group of $10$ into $5$ groups of $2$.

Line up the people in order of height, or student number.

Person $1$ can choose her partner in $9$ ways. For each such choice, the first person in the list who has not yet been partnered can choose her partner in $7$ ways. Now the first person not yet partnered can choose her partner in $5$ ways, and so on.

So the total number of ways is $(9)(7)(5)(3)(1)$.

Another way: We choose $2$ people from the $10$, then choose $2$ people from the remaining $8$, and so on.

There are $\binom{10}{2}\binom{8}{2}\binom{6}{2}\binom{4}{2}$ ways to do this. But the number just calculated grossly overcounts the number of ways to divide our people into telephone teams of $2$. This is because the product just obtained counts the each pairing $5!$ times, since it takes order of choosing into account. To get the right count, we must therefore divide by $5!%.

Remark: There are many other reasonable ways of doing the counting. In this problem, it is all too easy to overcount.

share|improve this answer

The question is that of the number of perfect matchings in a complete graph on $10$ vertices. The number $M(n)$ of such matchings in a complete graph on $2n$ vertices satisfies the recurion $M(n)=(2n-1)M(n-1)$ (with $M(0)=1$) since there are $2n-1$ candidates to be matched to the first vertex and after that it remains to choose a perfect matching on the complete graph on the remaining $2(n-1)$ points. Thus $M(n)=(2n-1)\times(2n-3)\times\cdots\times3\times1$, a number that is denoted by some people as $(2n-1)!!$ (in spite of the ambiguity of this notation with "factorial of the factorial"). This number comes up in very many problemns, see for instance the descriptions in OEIS A001147. One that seems t be missing from that list is that it is the dimension of the Brauer algebra for $n$.

Of course you can compute $9\times7\times5\times3\times1=945$ without difficulty.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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