# Counting the Number of Paths in the "Travelling Salesman Problem"

The "Travelling Salesman Problem" is a problem where a person has to travel between "n" cities - but choose the itinerary such that:

• Each city is visited only once
• The total distance travelled is minimized

I have heard that if a modern computer were to solve this problem for even 15 cities using "brute force" - it could take years to figure out to calculate the shortest route between these cities! For instance, look at the following link (https://www.sciencedirect.com/topics/earth-and-planetary-sciences/traveling-salesman-problem):

I am interested in learning about "how we can estimate the amount of time required for a computer to solve the Travelling Salesman Problem as the number of cities increases". For a given number of cities, naïve attempt would be to :

• A: Count the total possible number of permutations (n!)
• B: For each permutations, count the number of paths (n)
• C: Multiply each path by the amount of time required to perform a single calculation - i.e. the amount of time required to measure a path (e.g. 1 millisecond)
• Final Answer (i.e. amount of time required to consider all permutations and all paths): A * B * C

My Question: In the above text, it mentions that for "n points", there are "(n-1)!/2" number of paths - it then seems to me that path is multiplied by some "fixed amount of time" that represents the time required per calculation.

I do not know how this formula (n-1)!/2 is derived.

If I had used the logic I identified above, the the total number of paths would be n * n! .

Can someone please show me how this is done?

Thanks!

• Each permutation represents exactly one path. Feb 3 at 18:56

First of all, $$\frac12 (n-1)!$$ is counting closed tours that start somewhere, visit all the towns, and return to the start.

A permutation does not give us $$n$$ of these closed tours. It gives us only one. The permutation $$(a_1, a_2, \dots, a_n)$$ corresponds to starting at town $$a_1$$, going to town $$a_2$$, then to town $$a_3$$, and so on to $$a_n$$, then returning to $$a_1$$.

We divide by $$2n$$ because each possible closed tour is given by $$2n$$ different permutations. The permutations $$(a_1, a_2, \dots, a_n)$$ and $$(a_2, a_3, \dots, a_n, a_1)$$ and $$(a_3, a_4, \dots, a_1, a_2)$$ and so on take the same paths, just starting at a different point. (That's the factor of $$n$$.) The permutations $$(a_1, a_2, \dots, a_n)$$ and $$(a_n, a_{n-1}, \dots, a_1)$$ take the same paths, just in reverse order. (That's the factor of $$2$$.)

So the number of possible closed tours is actually $$n!/(2n)$$ or $$\frac12 (n-1)!$$.

• This fails for $n=1,2$. :)
– user
Feb 3 at 23:34
• Yes, there are not $\frac12$ closed tours when $n=1$ :) The reason it fails is that when $n=1$ or $n=2$, it is not meaningful to "reverse" a closed tour. Feb 3 at 23:44
• Thank you so much everyone! So this formula is valid from 3 onwards? Thanks! Feb 4 at 5:36
• @ Misha Lavrov : Can you please take a look at this question if you have time? math.stackexchange.com/questions/4416714/… Thank you so much! Mar 31 at 0:23