$8$ friends meet at a restaurant. Each friend shakes hands with exactly $2$ other people. Find $N$, the number of possible lists of pairs of friends that shook hands with each other.
Shaking hands problem
-
0Try it with 3 friends, instead of 8. Try it for 4 friends. See if you get any ideas that way. β 2012-10-06
2 Answers
HINT: Let $F$ be the set of friends. Define a relation $\sim$ on $F$ by $x\sim y$ if and only if $x=y$ or $x$ and $y$ shook hands. Show that the transitive closure of $\sim$ is an equivalence relation. Show that each $\sim$-equivalence class can be listed $\langle x_1,\dots,x_n\rangle$ in such a way that $x_1\sim x_2\sim\ldots\sim x_n\sim x_1$. In graph-theoretic terms, the handshake graph is a union of pairwise disjoint cycles. Each cycle must be of length at least $3$, so the only possibilities are a $3$-cycle and a $5$-cycle, two $4$-cycles, or an $8$-cycle. Deal with each of the three types separately. The basic tasks are:
- to determine how many distinct handshake graphs of each type there are; and
- given a cycle of friends, to determine in how many ways the pairs shaking hands can be listed.
-
0@Marc: Itβs pretty obvious from the rest of the answer what I have in mind. β 2012-10-06
If I understand the problem correctly, you are trying to count the number of simple (no loops, no double edges) graphs on $8$ points where each vertex has degree exactly $2$. (This assumes that "lists" is interpreted as "sets": you do care who shook hands with who, but not in which order those pairs are listed.) Equivalently these are partitions of $8$ into non-oriented cycles of length at least $3$ each, so you can have cycles of lengths $3$ and $5$, of lengths $4$ and $4$, or one of length $8$.
Let me try two different approaches, one by recursion on the number $n$ of people, one by counting per cycle type. If you consider person $N$, then she either is in a cycle of length $3$ or in one of length at least $4$. In the former case taking out the $3$ cycle will leave a valid solution for $n-3$ people, but who form some subset of the first $n-1$. So you need to multiply the number of such solutions by the number $\binom{n-1}{n-3}$ of such subsets (there is only one way to arrange the other $3$ into a non-oriented cycle). In the latter case leaving out person $n$ while letting her two partners shake hands (which they did not do before) leads to a solution for $n-1$ people. But person $n$ can be inserted at each of the $n-1$ handshakes of the solution, so we must multiply be that. This leads to the following recursion relation for the number $N(n)$: $ N(n)=\binom{n-1}2N(n-3)+(n-1)N(n-1)\qquad\text{for }n\geq3. $ Together with the value $N(0)=1$, $N(1)=N(2)=0$ we find $N(3)=1$, $N(4)=3$, $N(5)=12$, $N(6)=10+60=70$, $N(7)=15\times3+420=465$ and $N(8)=21\times12+7\times465=3507$.
Counting by cycle type, we should note that for $m\geq3$ there are $\frac{(m-1)!}2$ ways to arrange $m$ elements into a non-oriented cycle (as there are $(m-1)!$ ways to arrange them into an oriented cycle). One can partition $8$ in $\binom83=56$ ways into subsets of sizes $3+5$, in $\binom84/2=35$ ways into sizes $4+4$ (the division by $2$ is because one cannot distinguish the subsets). Then we find $ 56\times1\times12+35\times3\times3+1\times\frac{7!}2=3507 $
Having two methods has the great advantage of allowing a check: while doing these calculations I initially made errors in both variants, but was able to trace them back and correct them until they gave the same result. In this particular case I found the cycle type computation was both faster and less error-prone, but the recursion is certainly easier to teach to a computer.
-
0Great solution. I was just counting the 8-length cycle and getting the answer as $2502$. β 2012-10-06