# How many ways are there to shake hands?

In a group of $9$ people, each person shakes hands with exactly $2$ of the other people from the group. Let $X$ be the number of possible ways to perform these handshakes. Take $2$ handshake patterns (arrangements) distinct if and only if at minimum $2$ people who shake hands under one pattern (arrangement) don't shake hands under the other pattern (arrangement). Find $X$.

I think casework is the way to go.

$A$ shakes with $B$ & $C$. $D$ shakes with $E$ & $F$. $G$ shakes with $H$ & $I$.

Perhaps I could use a recurrence relation, but I don't see a possible way.

In total there are:

$$\binom{9}{3} \cdot \binom{6}{3} \cdot \binom{3}{3} = 1680$$

Ways to choose groups of three people.

But I dont anything else to this problem, and clearly this is the wrong answer.

• possible duplicate of Classic Hand shake question – Masacroso Jul 20 '15 at 16:56
• No, it isn't a duplicate. – Jorge Fernández Hidalgo Jul 20 '15 at 17:03
• In your example, $B$,$C$,$E$,$F$,$H$ and $I$ shake hands with only one person. – Lonidard Jul 20 '15 at 20:08

The handshakes can be modelled by a graph, you want to find the number of $2$-regular graphs on nine vertices.

It is known $2$-regular graphs have cycles as connected components.

There are three options for the number of connected components:

One connected component:

In this case the graph is a cycle on $9$ vertices, the cycle can be viewed as a permutation starting with $1$ listing vertices in order. There are $8!$ such permutations, but they give us each cycle twice (once in each order).

Hence there are $\frac{8!}{2}=20,160$ such cycles. It will be good to take note of the following formula: there are $\frac{(k-1)!}{2}$ ways to make a cycle with $k$ vertices.

Two connected components:

We have to subdivide depending on the sizes of the two components:

$3$ and $6$: first choose the three vertices in $\binom{9}{3}$ ways, after the above formula gives us $\frac{2!}{2}\frac{5!}{2}$ ways to form the cycles. So there are $\binom{9}{3}\frac{2!}{2}\frac{5!}{2}=5,040$ cycles of this kind.

$4$ and $5$: first choose the four vertices in $\binom{9}{4}$ ways,after the above formula gives us $\frac{3!}{2}\frac{6!}{2}$ ways to form the cycles. So there are $\binom{9}{4}\frac{3!}{2}\frac{4!}{2}=4,536$

Three connected components:

There are $\binom{9}{3,3,3}$ ways to split the nine vertices into the three groups. Of course this distinguishes each of the factor, so in fact the answer is $\binom{9}{3,3,3}\frac{1}{3!}=280$

So final answer is $20,160+5,040+4,536+280=30,016$

• nice answer. But: (1) What do you mean by "make a cycle with $k$ vertices?" (2) How did you derive: $(k-1)!/2$? – Amad27 Jul 20 '15 at 17:17
• well, if you have $k$ vetices $1,2,3\dots k$ how many ways can we add edges so that they form a cycle? The most usual cycle would be to connect $1$ with $2$ and $k$ and to connect $k$ with $k-1$ and $1$. And connect every other number $j$ with $j-1$ and $j+1$. This is one of the possible cycles. But there are many other cycles. You can describe a cycle by giving a list that starts in $1$ and includes each vertex $1$. For example: $1,2,3,4\dots k$ describes the cycle I mentioned at the beginning. Every cycle can be characterized with a list like that. However each cycle has two lists. – Jorge Fernández Hidalgo Jul 20 '15 at 17:20
• For example notice $1,2,3\dots k$ and $1,k,k-1,k-2\dots 3,2$ give us the same cycle. Since there are $(k-1)!$ permutations of the elements $2,3,4,5\dots k$ and to every two of these permutations there corresponds a cycle, we deduce there are $\frac{(k-1)!}{2}$ cycles on the elements $(1,2,3,4,\dots k)$ – Jorge Fernández Hidalgo Jul 20 '15 at 17:22
• More than a "hint" :-) but I think this answer is the right way. – leonbloy Jul 20 '15 at 17:24
• Oh, I'm sorry about that. For some reason my brain didn't parse that part of the question, I just realized it now, it must be the heat. – Jorge Fernández Hidalgo Jul 20 '15 at 17:26