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.

A graph of $n$ nodes is given. We have to visit each node twice. How many such traversals are there?

It's a complete graph and it's not possible to visit the nodes in a consecutive order.

Example: we have $4$ nodes, $A$, $B$, $C$ and $D$.

One possible path would be: $A B A C D B D C$ Path $A A B C D B C D$ would be invalid, since we visited the node A in a consecutive order.

I reckon there are $(2n)! / (2!)^n$ possibilities to traverse such a graph, but how do I exclude the consecutive visits ("$AA$" or "$BB$")?

share|improve this question
    
For some basic information about writing math at this site see e.g. here, here, here and here. –  Julian Kuelshammer Oct 25 '12 at 8:07
    
Thanks for the hint, Julian! –  marko.ristin Oct 25 '12 at 8:32
add comment

1 Answer

up vote 0 down vote accepted

You can do it with an inclusion-exclusion argument. Let $S$ be a set of $k$ of the vertices. Then there are $$\binom{2n-k}k\cdot k!\cdot\frac{(2n-2k)!}{2^{n-k}}=\frac{(2n-k)!}{2^{n-k}}$$ traversals that visit each of the $k$ vertices in $S$ (and possibly some other vertices as well) twice in succession: there are $\binom{2n-k}k$ ways to choose where in the traversal the $k$ vertices in $S$ will come, $k!$ ways to permute the vertices in $S$ amongst those positions, and $\frac{(2n-2k)!}{2^{n-k}}$ ways to arrange the rest of the traversal. Since there are $\binom{n}k$ sets of $k$ vertices, the number of traversals that do not visit any vertex twice in succession is

$$f(n)=\sum_{k=0}^n(-1)^k\binom{n}k\frac{(2n-k)!}{2^{n-k}}\;.\tag{1}$$

The first few values are $f(1)=0,f(2)=2,f(3)=30$, and $f(4)=864$; these are enough to identify the sequence as OEIS A114938, described as the number of permutations of the multiset $\{1,1,2,2,\dots,n,n\}$ with no two consecutive terms equal. The formula given there is $$f(n)=\sum_{k=0}^n(-1)^{n-k}\binom{n}k\frac{(n+k)!}{2^k}\;,$$ which is simply $(1)$ with $k$ replaced by $n-k$. There does not appear to be a nice closed form.

share|improve this answer
add comment

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.