Counting Principles 423city is designated as the starting point for all routes. There are n - 1 cities that remain to be
visited immediately after the starting city. Thus, there are n - 1 ways to choose the second
city to visit. For each of these n - 1 partial routes consisting of city 1 and the choice of a
second city, there are n - 2 remaining unvisited cities. In all, we have (n - 1) ... (n - i)
partial routes starting at city 1 and containing i + 1 cities. The total number of routes
starting at one city and not returning to that city until all the other cities have been visited
is (n - 1)... (n - (n - 1)) = (n - 1)!. Therefore, (n - 1)! routes exist for visiting each of
the n cities exactly once provided that one city is designated as the starting and ending city.
As the second step in this algorithm, the travel time for each of the (n - 1)! possible
routes must be calculated. Calculation of the traveling time for each possible route requires
adding the n numbers that represent the travel times of all the flights of a route. Each
addition will require at most some constant number k of such elementary operations. This
means that when n additions are performed, they are carried out by at most kn elementary
operations for some positive natural number k. Therefore, the number of elementary opera-
tions in calculating the length of all the routes is at most (n - 1)! kn (or O(n! )) operations.
For the third step, finding the minimum for a set of (n - 1)! numbers requires
(n - 1)! - 1 comparisons. Suppose the comparison of two numbers consists of some fi-
nite number 1 of elementary operations. This means that when (n - 1)! - 1 comparisons
are performed, there are at most I ((n - 1)! - 1) elementary operations for some fixed
constant 1. Putting the analysis of these three steps together gives the complexity of this
solution for the TSP. This solution will require at most kn! + 1 -((n - 1)! - 1) operations.
The order of the algorithm is O(n!).
The upper bound on the running time of our naive algorithm for the TSP looks very
bad, but in fact, it is not known whether the TSP can be solved by an algorithm with the
complexity of a polynomial in n. The problem has many practical applications, and at
times, some algorithm to solve an instance of this problem must be used, however much
time it will take.
This TSP example has provided a first illustration of the major counting principles that
we now want to introduce more formally.Counting Principles
Two principles of counting form a foundation for most counting techniques. The first prin-
ciple, called the Multiplication Principle, is used for counting the number of elements
arising from several choices that are made independently. This situation occurs, for exam-
ple, in counting the number of ways to order a meal consisting of an appetizer, a main
course, and a desert. The second principle, called the Addition Principle, is used to count
the number of elements in a set that can be partitioned into disjoint subsets. This situation
occurs, for example, in taking a census by adding the contributions from different regions.
We discuss the Multiplication Principle first and then the Addition Principle.
Suppose that Fast Lease, Inc., has three brands of microcomputers available for lease.
Each microcomputer is leased together with one of four different software packages. To
have leases available for customers to sign regardless of the options they choose, how
many different leases should be drawn up and available at any time?
The solution of this problem uses the following kind of analysis: First, a customer
must choose a microcomputer from among the three possibilities. Second, after choosing