Page 415 - Discrete Mathematics and Its Applications

394 6 / Counting

set of students who majored both in computer science and in business. By the subtraction rule
the number of students who majored either in computer science or in business (or both) equals

|A 1 ∪ A 2 |=|A 1 |+|A 2 |−|A 1 ∩ A 2 |= 220 + 147 − 51 = 316.

We conclude that 350 − 316 = 34 of the applicants majored neither in computer science nor in
business. ▲

The subtraction rule, or the principle of inclusion–exclusion, can be generalized to find the
number of ways to do one of n different tasks or, equivalently, to find the number of elements
in the union of n sets, whenever n is a positive integer. We will study the inclusion–exclusion
principle and some of its many applications in Chapter 8.

The Division Rule

We have introduced the product, sum, and subtraction rules for counting. You may wonder
whether there is also a division rule for counting. In fact, there is such a rule, which can be
useful when solving certain types of enumeration problems.

THE DIVISION RULE There are n/d ways to do a task if it can be done using a procedure
that can be carried out in n ways, and for every way w, exactly d of the n ways correspond
to way w.

We can restate the division rule in terms of sets: “If the finite set A is the union of n pairwise
disjoint subsets each with d elements, then n =|A|/d.”
We can also formulate the division rule in terms of functions: “If f is a function from A
to B where A and B are finite sets, and that for every value y ∈ B there are exactly d values
x ∈ A such that f(x) = y (in which case, we say that f is d-to-one), then |B|=|A|/d.”
We illustrate the use of the division rule for counting with an example.

EXAMPLE 20 How many different ways are there to seat four people around a circular table, where two
seatings are considered the same when each person has the same left neighbor and the same
right neighbor?

Solution: We arbitrarily select a seat at the table and label it seat 1. We number the rest of the
seats in numerical order, proceeding clockwise around the table. Note that are four ways to
select the person for seat 1, three ways to select the person for seat 2, two ways to select the
person for seat 3, and one way to select the person for seat 4. Thus, there are 4!= 24 ways to
order the given four people for these seats. However, each of the four choices for seat 1 leads
to the same arrangement, as we distinguish two arrangements only when one of the people has
a different immediate left or immediate right neighbor. Because there are four ways to choose
1st bit 1 0 the person for seat 1, by the division rule there are 24/4 = 6 different seating arrangements of
four people around the circular table. ▲
2nd bit 0 1 0
3rd bit 1 0 0 1 0 Tree Diagrams

4th bit
0 1 0 1 0 0 1 0 Counting problems can be solved using tree diagrams. A tree consists of a root, a number
1010 001 1 1000 0101 0100 0010 0001 0000 of branches leaving the root, and possible additional branches leaving the endpoints of other
branches. (We will study trees in detail in Chapter 11.) To use trees in counting, we use a branch
FIGURE 2 Bit to represent each possible choice. We represent the possible outcomes by the leaves, which are
Strings of Length the endpoints of branches not having other branches starting at them.
Four without Note that when a tree diagram is used to solve a counting problem, the number of choices
Consecutive 1s. of which branch to follow to reach a leaf can vary (see Example 21, for example).