7

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!

Amad27
  • 10,465

1 Answers1

3

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{4!}{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$

bdavidson
  • 65
Asinomás
  • 105,651
  • 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. – Asinomás 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)$ – Asinomás Jul 20 '15 at 17:22
  • 1
    More than a "hint" :-) but I think this answer is the right way. – leonbloy Jul 20 '15 at 17:24
  • 1
    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. – Asinomás Jul 20 '15 at 17:26
  • @dREaM, no problem, this is a great answer. Just a tad more confusion. By "cycle," do you mean how many seating arrangements possible? Also, no permutations correct?

    But for the permutations, why did you leave out the $1$? You said "permutations of the elements $2, 3, 4, 5, ..., k$ and to every two of these permutations...".

    Why isnt it $k!/2$ instead of $(k-1)!/2$?

     – Amad27 Jul 20 '15 at 17:55
  • @dREaM, by cycle do you mean how many hand shakes are possible? Or like the order of arrangement? – Amad27 Jul 21 '15 at 13:25
  • @Amad27, if you place $n$ people in a circle (cycle in the graphs), you can cut each arrangement at $n$ places (between each pair of people), and this results in a total of $n!$ linear arrangements, thus there are $n! / n = (n - 1)!$ circular arrangements. But in handshaking there is no left-to-right order, so $(n - 1)! /2$. – vonbrand Jul 23 '15 at 14:15
  • @Amad27. alternatively, take the circle of people, and start at whoever is $1$ going left. Next one is one of $n - 1$ others, then $n - 2$, ..., to just $1$ option, that is $(n - 1)!$ circular orderings, But the same sequence of people in a sequence going right is the same set of handshakes, thus $(n - 1)!/2$. – vonbrand Jul 23 '15 at 14:20
  • @vonbrand, so you're finding how many possible arrangements right? Not respective to location? Because you are fixing one point correct? – Amad27 Jul 23 '15 at 14:43
  • @Amad27, yes.$$$$ – vonbrand Jul 23 '15 at 14:52