EXAMPLE 36 Traveling salesman problem

A Southeast regional salesman has eight destinations that he must travel to this month: Atlanta, Raleigh, Charleston, Nashville, Jacksonville, Richmond, Mobile, and Jackson. How many different possible routes could he take?

Solution

The salesman has different choices for where to go first. Once the first destina-tion has been chosen, there are only choices for where to go second. And once the first two destinations have been chosen, there are only choices for where to go third, and so on. Thus, by the Multiplication Law for Counting, the number of dif-ferent possible routes for the salesman is