0
$\begingroup$

There is a group of 9 people. Each person shakes hands with exactly two others. I need to consider 2 handshaking arrangements different if and only if at least two people who shake hands under one arrangement do not shake hands under the other arrangement. I need to find the number of such arrangements possible. The condition which is given is troubling. Can anyone help me with a simple combinatorial solution for this

$\endgroup$
1
$\begingroup$

The graph will be a union of cycles. The sizes of these cycles add up to $9$. As every cycle has size at least $3$, there are only four possibilities:

One cycle of lenght $9$.

Two cycles of lengths $3,6$.

Two cycles of lengths $4,5$.

Three cycles of lengths $3,3,3$.

Each of these four cases lead to a simple combinatorial problem. I show you the first and the last cases, you can finish the rest.

Preliminary calculation: Given $k\geq 3$ people, there are $(k-1)!/2$ ways to form a $k$-cycle out of them. Indeed, there are $(k-1)!$ cyclic orders of them, and each cyclic order defines the same cycle graph as the reverse cyclic order, and there are no other coincidences.

First case: the graph is a $9$-cycle. There are $(9-1)!/2=20160$ ways to make them form a $9$-cycle.

Last case: the graph is a union of three $3$-cycles. There are $\frac{9!}{(3!)^3\cdot 3!}=280$ ways to partition the $9$ people into three groups of $3$, and this uniquely determines a solution, as three people form a uique $3$-cycle.

Have fun with the rest of the proof, no new idea is needed.

$\endgroup$
7
  • $\begingroup$ Pardon my ignorance what does "circles" mean in your solution? $\endgroup$ – saisanjeev Aug 15 '18 at 14:40
  • $\begingroup$ Did I write that anywhere? If I did, it is equivalent to cycle. $\endgroup$ – A. Pongrácz Aug 15 '18 at 14:49
  • $\begingroup$ Is something still unclear? Do you find the answer acceptable? $\endgroup$ – A. Pongrácz Aug 15 '18 at 16:16
  • $\begingroup$ yeah I actually didn't understand how you made those cycle lengths,etc $\endgroup$ – saisanjeev Aug 17 '18 at 7:39
  • $\begingroup$ Be more specific, please. $\endgroup$ – A. Pongrácz Aug 17 '18 at 8:24

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.