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

Question

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.

Answer 1

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.