Page 406 - Discrete Mathematics and Its Applications

CH A P TER

6 Counting

6.1 The Basics of ombinatorics, the study of arrangements of objects, is an important part of discrete math-
Counting Cematics. This subject was studied as long ago as the seventeenth century, when combi-
natorial questions arose in the study of gambling games. Enumeration, the counting of objects
6.2 The Pigeonhole
Principle with certain properties, is an important part of combinatorics. We must count objects to solve
many different types of problems. For instance, counting is used to determine the complexity of
6.3 Permutations algorithms. Counting is also required to determine whether there are enough telephone numbers
and or Internet protocol addresses to meet demand. Recently, it has played a key role in mathematical
Combinations biology, especially in sequencing DNA. Furthermore, counting techniques are used extensively
when probabilities of events are computed.
6.4 Binomial
Coefficients The basic rules of counting, which we will study in Section 6.1, can solve a tremendous
and Identities variety of problems. For instance, we can use these rules to enumerate the different telephone
numbers possible in the United States, the allowable passwords on a computer system, and the
6.5 Generalized different orders in which the runners in a race can finish. Another important combinatorial tool
Permutations is the pigeonhole principle, which we will study in Section 6.2. This states that when objects are
and placed in boxes and there are more objects than boxes, then there is a box containing at least two
Combinations objects. For instance, we can use this principle to show that among a set of 15 or more students,

6.6 Generating at least 3 were born on the same day of the week.
Permutations We can phrase many counting problems in terms of ordered or unordered arrangements of
and the objects of a set with or without repetitions. These arrangements, called permutations and
Combinations combinations, are used in many counting problems. For instance, suppose the 100 top finishers
on a competitive exam taken by 2000 students are invited to a banquet.We can count the possible
sets of 100 students that will be invited, as well as the ways in which the top 10 prizes can be
awarded.
Another problem in combinatorics involves generating all the arrangements of a specified
kind. This is often important in computer simulations. We will devise algorithms to generate
arrangements of various types.

6.1 The Basics of Counting

Introduction

Suppose that a password on a computer system consists of six, seven, or eight characters. Each
of these characters must be a digit or a letter of the alphabet. Each password must contain at least
one digit. How many such passwords are there? The techniques needed to answer this question
and a wide variety of other counting problems will be introduced in this section.
Counting problems arise throughout mathematics and computer science. For example, we
must count the successful outcomes of experiments and all the possible outcomes of these
experiments to determine probabilities of discrete events. We need to count the number of
operations used by an algorithm to study its time complexity.
We will introduce the basic techniques of counting in this section. These methods serve as
the foundation for almost all counting techniques.

385