text: You are on page 1of 2
  
  # Combinatorics, the study of arrangements of objects, is an important part of dis
  
  crete mathematics. This subject was studied as long ago as the seventeenth century, when c
  ombinatorial questions arose in the study of gambling games. Enumeration, the counti
  ng of objects
  with certain properties, is an important part of combinatorics. We must count ob
  jects to solve
  many different types of problems. For instance, counting is used to determine th
  e complexity of
  algorithms. Counting is also required to determine whether there are enough tele
  phone numbers
  or Internet protocol addresses tomeet demand. Recently, it has played a key role
  inmathematical
  biology, especially in sequencing DNA. Furthermore, counting techniques are used
  extensively
  when probabilities of events are computed.
  The basic rules of counting, which we will study in Section 6.1, can solve a tre
  mendous
  variety of problems. For instance, we can use these rules to enumerate the diffe
  rent telephone
  numbers possible in the United States, the allowable passwords on a computer sys
  tem, and the
  different orders in which the runners in a race can ?nish. Another important com
  binatorial tool
  is the pigeonhole principle, which we will study in Section 6.2. This states tha
  t when objects are
  placed in boxes and there are more objects than boxes, then there is a box conta
  ining at least two objects. For instance, we can use this principle to show that
  among a set of 15 or more students,
  at least 3 were born on the same day of the week.
  We can phrase many counting problems in terms of ordered or unordered arrangemen
  ts of
  the objects of a set with or without repetitions. These arrangements, called per
  mutations and
  combinations, are used in many counting problems. For instance, suppose the 100
  top ?nishers
  on a competitive examtaken by 2000 students are invited to a banquet.We can coun
  t 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 s
  peci?ed
  kind. This is often important in computer simulations. We will devise algorithms
  to generate
  arrangements of various types.
  The Basics of Counting
  Introduction
  Suppose that a password on a computer system consists of six, seven, or eight ch
  aracters. Each
  of these charactersmust be a digit or a letter of the alphabet. Each passwordmus
  t contain at least
  one digit. How many such passwords are there? The techniques needed to answer th
  is 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 method
  s serve as
  the foundation for almost all counting techniques.
  Basic Counting Principles
  We ?rst present two basic counting principles, the product rule and the sumrule.
  Then we will
  show how they can be used to solve many different counting problems.
  The product rule applies when a procedure is made up of separate tasks.
  THE PRODUCT RULE Suppose that a procedure can be broken down into a sequence of
  two tasks. If there are n1 ways to do the ?rst task and for each of these ways o
  f doing the ?rst
  task, there are n2 ways to do the second task, then there are n1n2 ways to do th
  e procedure.
  Examples 1 10 show how the product rule is used.
  A new company with just two employees, Sanchez and Patel, rents a ?oor of a buil
  ding with
  12 of?ces. How many ways are there to assign different of?ces to these two emplo
  yees?
  Solution: The procedure of assigning of?ces to these two employees consists of a
  ssigning an
  of?ce to Sanchez, which can be done in 12 ways, then assigning an of?ce to Patel
  different from
  the of?ce assigned to Sanchez, which can be done in 11 ways. By the product rule
  , there are
  = ?