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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .