Discrete Mathematics for Computer Science

426 CHAPTER 7 Counting and Combinatorics

independently of whether any other line segment is on or off, the Multiplication Principle

says that 27 = 128 characters can be represented by this grid. U

It is easy enough to represent the digits using seven segments, but the reader should

think about how many segments, and what pattern of segments, could be used to represent

the letters of the alphabet as well as the other characters on a keyboard.

Example 4. Show that the number of subsets of a finite set with n elements is 2'.

Solution. Let the elements of an n-element set be al, a2. ..... a,. Each subset of these

elements can be uniquely associated with an n-tuple of 0's and I's, with 1 in the ith position

indicating that the element ai is in the subset and 0 in the ith position indicating the element

ai is not in the subset. In this procedure, for I < i < n, the ith step has one of two possible

outcomes: Either the ith element of the set is an element of the subset and the entry is 1,

or the ith element of the set is not an element of the subset and the entry is 0. Therefore,

by the Multiplication Principle, there are 2n such n-tuples and, consequently, 2n possible

subsets of an n-element set. 0

The reader should compare this proof with the one in Theorem 2 in Section 1.7.4

That proof is far more complicated, because it does not use the Multiplication Principle.

(It also makes the induction very explicit. Indeed, if one wanted to prove the Multipli-

cation Principle from "first principles," then the proof might look rather like the one in

Section 1.7.4

72.2 Addition Principle

Another counting principle arises when choices are made from sets of mutually exclu-

sive options. For example, suppose that Fast Machine Repair, Inc., offers two categories

of service contracts. The first is a full-service contract that provides parts and services as

needed for a fixed annual fee. The second is a service-on-demand contract that charges

a small annual fee and then charges separately for services by the hour and for parts as

they are needed. To satisfy different kinds of customers, Fast Machine Repair offers three

levels of full-service contracts and two levels for service-on-demand service. These two

sets of choices are disjoint. How many different contracts should be available so that no

matter what option the customer may choose, the appropriate contract is ready for signing?

Since there are three choices for the full-service option and two-choices for the hourly

charge option, and because these two sets of choices are disjoint, the total number of

choices is

(# Service options) (# Full-service options) + (# Hourly charge options)

=5

Rather than representing these choices by a tree as was done with the Multiplication Prin-

ciple, the possible choices here are represented by a collection of disjoint sets. Each set

represents a collection of options in the same category. The options available in this prob-

lem are represented by the two disjoint sets pictured in Figure 7.4.