6
$\begingroup$

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.

Hints only please!

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

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ nice answer. But: (1) What do you mean by "make a cycle with $k$ vertices?" (2) How did you derive: $(k-1)!/2$? $\endgroup$ – Amad27 Jul 20 '15 at 17:17
  • $\begingroup$ 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. $\endgroup$ – Jorge Fernández-Hidalgo Jul 20 '15 at 17:20
  • $\begingroup$ 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)$ $\endgroup$ – Jorge Fernández-Hidalgo Jul 20 '15 at 17:22
  • 1
    $\begingroup$ More than a "hint" :-) but I think this answer is the right way. $\endgroup$ – leonbloy Jul 20 '15 at 17:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Jorge Fernández-Hidalgo Jul 20 '15 at 17:26

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.