# How many options there are for $n$ people to shake hands exactly $r$ times?

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.

• Shaking hands is not recommended due to the Corona Virus pandemy :) May 23, 2020 at 17:55
• @JeanMarie I agree, my professor gives very inappropriate homework May 23, 2020 at 18:00
• If I understand this correctly, you're counting the number of labeled $r$-regular graphs, which is an unsolved problem May 23, 2020 at 18:03
• 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? May 23, 2020 at 18:08
• @joriki your interpretation is correct May 23, 2020 at 18:09

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.
• There is a restriction : the number is $0$ is $n$ and $r$ are both odd ; see (math.stackexchange.com/q/2113127). May 23, 2020 at 18:59