7
$\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!

$\endgroup$
3
  • $\begingroup$ possible duplicate of Classic Hand shake question $\endgroup$
    – Masacroso
    Jul 20, 2015 at 16:56
  • 2
    $\begingroup$ No, it isn't a duplicate. $\endgroup$
    – Asinomás
    Jul 20, 2015 at 17:03
  • $\begingroup$ In your example, $B$,$C$,$E$,$F$,$H$ and $I$ shake hands with only one person. $\endgroup$
    – Lonidard
    Jul 20, 2015 at 20:08

1 Answer 1

Reset to default
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$

$\endgroup$
11
  • $\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, 2015 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$
    – Asinomás
    Jul 20, 2015 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$
    – Asinomás
    Jul 20, 2015 at 17:22
  • 1
    $\begingroup$ More than a "hint" :-) but I think this answer is the right way. $\endgroup$
    – leonbloy
    Jul 20, 2015 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$
    – Asinomás
    Jul 20, 2015 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.