2
$\begingroup$

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

  • 0
    For some basic information about writing math at this site see e.g. [here](http://meta.math.stackexchange.com/questions/5020/), [here](http://meta.stackexchange.com/a/70559/155238), [here](http://meta.math.stackexchange.com/questions/1773/) and [here](http://math.stackexchange.com/editing-help#latex).2012-10-25

1 Answers 1

0

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.