Cm APT min lR
Counting and Combinatorics
How many passwords can be formed using five letters and two special characters? How
long would it take a computer to generate all such passwords as a way of compromising
computer security? How many ways can 25 people be arranged for a group photo? How
many ways can the manager of a tour of European capitals order the cities to be visited?
How many ways can $100 be divided among four students? How many lottery tickets
are needed to cover all the possibilities? Counting techniques introduced in this chapter
provide tools for answering questions like these.
Counting techniques are also used in the study of probability to determine the number
of events in a sample space and the number of successful outcomes for an experiment.
Probability theory commonly uses these counts to assess the likelihood of a particular
event. In computer science, elementary counting methods provide useful tools and tech-
niques for dealing with problems such as the enumeration of all possible states that must
be considered in proving that a program is correct. More generally, counting methods are
used at several stages in the development of a correct and efficient program. For example,
a first decision about which algorithm to use in a particular application is often based on
knowing how the various alternative algorithms compare with respect to running time or
storage use. A step in the process of determining the running time or the storage use of a
program often includes one or more counting arguments.
In this chapter, we discuss four major topics. First, we introduce the two fundamental
counting principles: the Multiplication Principle and the Addition Principle. Second, we
introduce permutations and combinations, which deal with the ways of selecting subsets ofa set in which the order of selection of the elements may-or may not-be important. With
these preliminaries, we introduce the final two major topics: The first involves counting the
number of selections possible from collections with repeated elements; the second involves
combinatorial identities, such as the binomial theorem. In addition, Pascal's triangle is
presented. The first example of this chapter involves determining the complexity of an
algorithm to solve a well-known problem in computer science.rnTraveling Salesperson's Problem
The Traveling Salesperson's Problem (TSP) is deceptively easy to state but deceptively
difficult to solve. A salesperson's territory includes n cities that must be visited on a regular
421