# Why isn't the search space size of TSP $(n-1)!$ instead of $n!$?

I'm just learning about the travelling salesman problem, and I've been playing around with it. I'm not sure if what I've found is just a special case or not. My professor says the search space size is $$n!$$, where $$n$$ is the number of cities.

Suppose we have a table with cities $$A,B,C,D$$ on each axis, and the elements represent the distances between cities:

$$\begin{array}{|c|c|c|c|} \hline & A & B & C & D \\ \hline A&0 & 2& 3&4\\ \hline B& 2 & 0& 10&5\\ \hline C& 3 &10 &0 &15\\ \hline D& 4 & 5& 15&0\\ \hline \end{array}$$

From this, I can generate various permutations of possible tours, and their lengths: $$A \to B \to C \to D \to A : 31$$ $$A \to B \to D \to C \to A : 25$$ $$A \to C \to B \to D \to A : 22$$ $$A \to C \to D \to B \to A : 25$$ $$A \to D \to B \to C \to A : 22$$ $$A \to D \to C \to B \to A : 31$$

Now, it seems to me that each of these permutations is cyclical. In this way, $$B \to C \to D \to A \to B : 31$$ and $$A \to B \to C \to D \to A : 31$$ are equivalent, for example.

So in fact, it doesn't matter which city I choose initially, because the resulting shortest tour will be equivalent to one of the tours above.

And clearly, there are $$3!$$ of these tours, or $$(n-1)!$$ of them. So why isn't the search space size $$(n-1)!$$ instead of $$n!$$? Maybe there is a problem with my understanding of what search space size is, I'm not sure.

The search space has size $$(n-1)!$$. You can see this in many ways, for example:

1. Each tour corresponds to $$n$$ different permutations, depending on the starting point.
2. If we start describing the tour at some point $$P$$ fixed ahead of time, then the tour is given (injectively) by an arbtirary permutation of the remaining $$n-1$$ points.

The reason that sometimes $$n!$$ is used is that $$n!$$ is shorter, and the difference between $$n!$$ and $$(n-1)!$$ is not always important.

• Hi, thanks for the answer. Are you able to expand slightly on when and why the difference between $n!$ and $(n-1)!$ is not always important? The factor of $n$ between them feels quite significant to me
– Data
Jun 30, 2019 at 16:08
• Sometimes it suffices to know that $n!$ is super-exponential, or more accurately $\exp \Theta(n\log n)$. The exact value of the hidden constant doesn’t matter. At other times the difference between $n!$ and $(n-1)!$ is more significant. Jun 30, 2019 at 16:12
• @YuvalFilmus, is it true though that the cycle costs are the same no matter what the starting point is? Mar 7, 2021 at 18:32
• $a+b+c=b+c+a=c+a+b$. Mar 7, 2021 at 18:35