How many routes possible in the traveling salesman problem with $n$ cities? And more...

Question

SO the general answer I come across on the internet is $(n-1)!/2$. But it would seem to be $n!$, or at least $(n-1)!$. Which one is it?

If you have 2 cities, you would have 1 path. So $(n-1)!/2$ can't hold?

EDIT: Another question. Let $P$ be the transition matrix between the routes according to the 2-opt procedure.

The pairwise exchange or 2-opt technique involves iteratively removing two edges and replacing these with two different edges that reconnect the fragments created by edge removal into a new and shorter tour.

The transition probabilities $P_{kl}$ for given $k$ and $1\leq l \leq size(P)$ can only take two values. What are the two value? I guess $P_{kk} = 0?$

Answer 1

So suppose you have $n$ cities, then for any given route, if you remove two edges then you must replace them with their cross matches. For example, lets say you have $$A\rightarrow B\rightarrow C\rightarrow D\rightarrow E$$

Then if you remove $(B, C)$ and $(E, A)$ then you must replace the with $(B, E)$ and $(A,C)$. This replacement is unequivocal.

So for any pair of edges of a tour there is exactly one unequivocal pair of edges as replacement. Furthermore, from every graph of $n$ cities and thus $n$ edges, you can select $$\dfrac{n(n-3)}{2} = \delta$$ pairs of edges which can be replaced by the 2-opt procedure. Why this holds is because, per graph you have the set of all possible pairs of edges minus the ones adjacent to each other. So one can not pair $(B,C)$ with $(A,B)$ nor $(C,D)$. Otherwise the 2-opt procedure fails. You divide by two because you have $(A,B) = (B,A)$.

Which brings you to the following: $P_{kl} = \dfrac{1}{\delta}$ if 2-opt possible, if not its 0.

Answer 2

There are $(n-1)!/2$ possible tours in the undirected form of the problem - $(n-1)!$ instead of $n!$ since it doesn't matter which node you start at, and you divide by two since e.g. for three nodes $A, B, C$, the tour $A\to B\to C\to A$ is the same as the tour $A\to C\to B\to A$.

I suppose I should add that in the undirected case, it doesn't really make sense to speak of a traveling salesman tour when $n<3$ since there can't be a cycle in the graph (and that's what a traveling salesman tour is, a Hamiltonian cycle).