# Count possible traversals in an undirected graph

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$")?

-
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

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.