3
$\begingroup$

This is a problem from Ross' probability book.

Problem:

Consider a group of 20 people. If everyone shakes hands with everyone else, how many handshakes take place?

Question:

I think the correct answer is $\binom{20}{2}=190$ ways to make handshake. But I don't get why the multinomial coefficient doesn't work here. Can someone tell me what's wrong with the following argument: since we are looking for number of ways to make handshakes, it is equivalent to asking how many ways of picking out 10 pairs out of 20 people. By this reason, we have that the number of ways is $\binom{20}{2,2,2,2,2,2,2,2,2,2}$.

$\endgroup$
2
  • 4
    $\begingroup$ Why do you think 10 pairs correspond to one handshake? We are not looking for how many ways to make simultaneous handshakes, but for how many handshakes have to be made so everyone shakes everybody's hand. Two different stories. $\endgroup$
    – Christoph
    Jan 11, 2015 at 22:15
  • $\begingroup$ ${20\choose 2,2,\ldots,2} = 2375880867360000$ handshakes seems a bit excessive. $\endgroup$
    – Winther
    Jan 11, 2015 at 22:27

1 Answer 1

3
$\begingroup$

I think a simple matrix is the best way of looking at this problem. Each element of this 20x20 matrix is =1 if two people (i,j) shake hands. Clearly for any two people (i,j) you need to cound the handshake only once and (i,i) is also clearly not allowed. So by symmetry you have a 20x20 matrix with only upper-triangular matrix filled with ones, exactly $\frac{400-20}{2} =190$.

$\endgroup$

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.