2
$\begingroup$

Find how many options there are for $n$ people to shake hands exactly $r$ times while:

  • The same pair of people can't shake hands more than once

  • Order of hand shakes does not matter

So the solution I thought about is ordering all people, then first deciding who the first person shakes hand with which is $2^{n-1}$ options, then who the second person shakes hands with (all options except the first person who we already counted) and so on, so in total we get $2^{\sum_{i=1}^{n}(n-i)}$ options, so the solution is $\binom{2^{\sum_{i=1}^{n}(n-i)}}{r}$.

I was wondering if there is a more elegant solution without summation. Also would be nice to confirm my solution is not wrong in some way.

$\endgroup$
5
  • 3
    $\begingroup$ Shaking hands is not recommended due to the Corona Virus pandemy :) $\endgroup$
    – Jean Marie
    May 23, 2020 at 17:55
  • 3
    $\begingroup$ @JeanMarie I agree, my professor gives very inappropriate homework $\endgroup$ May 23, 2020 at 18:00
  • $\begingroup$ If I understand this correctly, you're counting the number of labeled $r$-regular graphs, which is an unsolved problem $\endgroup$
    – stochastic
    May 23, 2020 at 18:03
  • 1
    $\begingroup$ The formulation of the problem is ambiguous. In my answer, I interpreted it to mean that all $n$ people in total do $r$ handshakes, but @stochastic apparently interpreted it to mean that each person does $r$ handshakes. Which do you mean? $\endgroup$
    – joriki
    May 23, 2020 at 18:08
  • $\begingroup$ @joriki your interpretation is correct $\endgroup$ May 23, 2020 at 18:09

1 Answer 1

2
$\begingroup$

You seem to be counting subsets and then choosing $r$ of the subsets. But the task is not to choose $r$ subsets but to choose $r$ pairs.

The solution is actually quite straightforward. There are $\binom n2$ unordered pairs of people, and the $r$ of these pairs who shake hands can be chosen in $\binom{\binom n2}r$ ways.

$\endgroup$
6
  • 1
    $\begingroup$ thanks, I see why my solution is wrong $\endgroup$ May 23, 2020 at 18:12
  • $\begingroup$ There is a restriction : the number is $0$ is $n$ and $r$ are both odd ; see (math.stackexchange.com/q/2113127). $\endgroup$
    – Jean Marie
    May 23, 2020 at 18:59
  • 1
    $\begingroup$ @JeanMarie: It seems you're operating under a different interpretation of the question than was intended; see the comments under the question. $\endgroup$
    – joriki
    May 23, 2020 at 19:36
  • $\begingroup$ @joriki I see. I should have paid more attention ! $\endgroup$
    – Jean Marie
    May 23, 2020 at 20:33
  • 1
    $\begingroup$ @paxtibimarce: I would have done it with inclusion–exclusion, too; I don't immediately see a simpler solution. Let me know if you post a question about this. $\endgroup$
    – joriki
    May 24, 2020 at 5:31

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.