Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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.

share|improve this question
1  
What have you tried so far? –  Michael Albanese Oct 6 '12 at 6:48
    
I'm not finding the right approach, I tried breaking in into smaller problems(recursion) but that didn't work. I also tried to use combinatorics, but it turned out too complex. –  sudeepdino008 Oct 6 '12 at 6:52
    
Try it with 3 friends, instead of 8. Try it for 4 friends. See if you get any ideas that way. –  Gerry Myerson Oct 6 '12 at 6:57

2 Answers 2

up vote 0 down vote accepted

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:

  1. to determine how many distinct handshake graphs of each type there are; and
  2. given a cycle of friends, to determine in how many ways the pairs shaking hands can be listed.
share|improve this answer
    
That helps. Thanks! –  sudeepdino008 Oct 6 '12 at 7:18
    
@I'llsudeepdino008: You’re welcome! –  Brian M. Scott Oct 6 '12 at 7:20
    
The realtion $\sim$ is not an equivalence relation; it fails to be transitive. –  Marc van Leeuwen Oct 6 '12 at 8:27
    
@Marc: Fixed. (I think that you meant the transitive closure, since $\sim$ as defined isn’t transitive would have been more helpful, though.) –  Brian M. Scott Oct 6 '12 at 8:31
    
@BrianM.Scott: Excuse me. But I couldn't read your mind, and I had no idea what you wanted an equivalence relation for in the first place. In fact I think I still don't know. –  Marc van Leeuwen Oct 6 '12 at 8:35

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.

share|improve this answer
    
Great solution. I was just counting the 8-length cycle and getting the answer as $2502$. –  sudeepdino008 Oct 6 '12 at 8:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.