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 $a=8$ different choices for where to go first. Once the first destina-tion has been chosen, there are only $b=7$ choices for where to go second. And once the first two destinations have been chosen, there are only $c=6$ 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