Tan S.T. Finite Mathematics for the Managerial, Life, and Social Sciences

Подождите немного. Документ загружается.

332 6 SETS AND COUNTING

We now illustrate the application of the generalized multiplication principle to

several diverse situations.

EXAMPLE 3

A coin is tossed 3 times, and the sequence of heads and tails is

recorded.

a. Use the generalized multiplication principle to determine the number of possible

outcomes of this activity.

b. Exhibit all the sequences by means of a tree diagram.

Solution

a. The coin may land in two ways. Therefore, in three tosses the number of out-

comes (sequences) is given by 2



2, or 8.

b. Let H and T denote the outcomes “a head” and “a tail,” respectively. Then the

required sequences may be obtained as shown in Figure 14, giving the sequence

as HHH, HHT, HTH, HTT, THH, THT, TTH, and TTT.

APPLIED EXAMPLE 4

Combination Locks A combination lock is

unlocked by dialing a sequence of numbers: first to the left, then to the

right, and to the left again. If there are ten digits on the dial, determine the num-

ber of possible combinations.

Solution

There are ten choices for the first number, followed by ten for the sec-

ond and ten for the third, so by the generalized multiplication principle there are



10, or 1000, possible combinations.

APPLIED EXAMPLE 5

Investment Options An investor has decided

to purchase shares in the stock of three companies: one engaged in aero-

space activities, one involved in energy development, and one involved in elec-

tronics. After some research, the account executive of a brokerage firm has rec-

ommended that the investor consider stock from five aerospace companies, three

First

toss

Combined

outcomes

Second

toss

Third

toss

(H, H, H)

(H, H, T)

(H, T, H)

(H, T, T)

(T, H, H)

(T, H, T)

(T, T

, H)

(

)

Generalized Multiplication Principle

Suppose a task T

can be performed in N

ways, a task T

can be performed in

ways, . . . , and, finally, a task T

can be performed in N

ways. Then, the

number of ways of performing the tasks T

, T

, . . . , T

in succession is given

by the product



FIGURE 14

Tree diagram displaying possible out-

comes of three consecutive coin tosses

87533_06_ch6_p313-352 1/30/08 10:01 AM Page 332

1. Explain the multiplication principle and illustrate it with a

diagram.

2. Given the following tree diagram for an activity, what are

the possible outcomes?

6.3 THE MULTIPLICATION PRINCIPLE 333

energy development companies, and four electronics companies. In how many

ways can the investor select the group of three companies from the executive’s

list?

Solution

The investor has five choices for selecting an aerospace company,

three choices for selecting an energy development company, and four choices for

selecting an electronics company. Therefore, by the generalized multiplication

principle, there are 5



4, or 60, ways in which she can select a group of three

companies, one from each industry group.

APPLIED EXAMPLE 6

Travel Options Tom is planning to leave for

New York City from Washington, D.C., on Monday morning and has

decided that he will either fly or take the train. There are five flights and two

trains departing for New York City from Washington that morning. When he

returns on Sunday afternoon, Tom plans to either fly or hitch a ride with a friend.

There are two flights departing from New York City to Washington that after-

noon. In how many ways can Tom complete this round trip?

Solution

There are seven ways Tom can go from Washington, D.C., to New

York City (five by plane and two by train). On the return trip, Tom can travel in

three ways (two by plane and one by car). Therefore, by the multiplication princi-

ple, Tom can complete the round trip in 7



3, or 21, ways.

1. Encore Travel offers a “Theater Week in London” package

originating from New York City. There is a choice of eight

flights departing from New York City each week, a choice

of five hotel accommodations, and a choice of one compli-

mentary ticket to one of eight shows. How many such

travel packages can one choose from?

2. The Café Napolean offers a dinner special on Wednesdays

consisting of a choice of two entrées (beef bourguignon

and chicken basquaise); one dinner salad; one French roll;

a choice of three vegetables; a choice of a carafe of bur-

gundy, rosé, or chablis wine; a choice of coffee or tea; and

a choice of six french pastries for dessert. How many com-

binations of dinner specials are there?

Solutions to Self-Check Exercises 6.3 can be found on

page 335.

6.3 Self-Check Exercises

6.3 Concept Questions

6.3 Exercises

1. R

ENTAL

ATES

Lynbrook West, an apartment complex fi-

nanced by the State Housing Finance Agency, consists of

one-, two-, three-, and four-bedroom units. The rental rate

for each type of unit—low, moderate, or market—is deter-

mined by the income of the tenant. How many different

rates are there?

87533_06_ch6_p313-352 1/30/08 10:01 AM Page 333

2. C

OMMUTER

ASSES

Five different types of monthly com-

muter passes are offered by a city’s local transit authority

for each of three different groups of passengers: youths,

adults, and senior citizens. How many different kinds of

passes must be printed each month?

3. B

LACKJACK

In the game of blackjack, a 2-card hand con-

sisting of an ace and either a face card or a 10 is called a

“blackjack.” If a standard 52-card deck is used, determine

how many blackjack hands can be dealt. (A “face card” is

a jack, queen, or king.)

4. C

OIN

OSSES

A coin is tossed 4 times and the sequence of

heads and tails is recorded.

a. Use the generalized multiplication principle to deter-

mine the number of outcomes of this activity.

b. Exhibit all the sequences by means of a tree diagram.

5. W

ARDROBE

ELECTION

A female executive selecting her

wardrobe purchased two blazers, four blouses, and three

skirts in coordinating colors. How many ensembles con-

sisting of a blazer, a blouse, and a skirt can she create from

this collection?

6. C

OMMUTER

PTIONS

Four commuter trains and three

express buses depart from city A to city B in the morning,

and three commuter trains and three express buses operate

on the return trip in the evening. In how many ways can a

commuter from city A to city B complete a daily round trip

via bus and/or train?

7. P

SYCHOLOGY

XPERIMENTS

A psychologist has constructed

the following maze for use in an experiment. The maze is

constructed so that a rat must pass through a series of one-

way doors. How many different paths are there from start

to finish?

8. U

NION

ARGAINING

SSUES

In a survey conducted by a

union, members were asked to rate the importance of the

following issues: (1) job security, (2) increased fringe ben-

efits, and (3) improved working conditions. Five different

responses were allowed for each issue. Among completed

surveys, how many different responses to this survey were

possible?

9. H

EALTH

-C

ARE

LAN

PTIONS

A new state employee is

offered a choice of ten basic health plans, three dental

Start

Finish

Maze

plans, and two vision care plans. How many different

health-care plans are there to choose from if one plan is

selected from each category?

10. C

ODE

ORDS

How many three-letter code words can be

constructed from the first ten letters of the Greek alphabet

if no repetitions are allowed?

11. S

OCIAL

ECURITY

UMBERS

A Social Security number has

nine digits. How many Social Security numbers are pos-

sible?

12. S

ERIAL

UMBERS

Computers manufactured by a certain

company have a serial number consisting of a letter of the

alphabet followed by a four-digit number. If all the serial

numbers of this type have been used, how many sets have

already been manufactured?

13. C

OMPUTER

ATING

A computer dating service uses the

results of its compatibility survey for arranging dates. The

survey consists of 50 questions, each having five possible

answers. How many different responses are possible if

every question is answered?

14. A

UTOMOBILE

OLORS

The 2007 BMW 335i Coupe is

offered with a choice of 14 exterior colors (11 metallic and

3 standard), 5 interior colors, and 4 trims. How many com-

binations involving color and trim are available for the

model?

Source: BMW

15. A

UTOMOBILE

OLORS

The 2007 Toyota Camry comes with 5

grades of models, 2 sizes of engines, 4 choices of transmis-

sions, 5 exterior colors, and 2 interior colors. How many

choices of the Camry are available for a prospective buyer?

Source: Toyota

16. T

ELEVISION

-V

IEWING

OLLS

An opinion poll is to be con-

ducted among cable TV viewers. Six multiple-choice ques-

tions, each with four possible answers, will be asked. In

how many different ways can a viewer complete the poll if

exactly one response is given to each question?

17. ATM C

ARDS

To gain access to his account, a customer

using an automatic teller machine (ATM) must enter a

four-digit code. If repetition of the same four digits is not

allowed (for example, 5555), how many possible combina-

tions are there?

18. P

OLITICAL

OLLS

An opinion poll was conducted by the

Morris Polling Group. Respondents were classified accord-

ing to their sex (M or F), political affiliation (D, I, R), and

the region of the country in which they reside (NW, W, C,

S, E, NE).

a. Use the generalized multiplication principle to deter-

mine the number of possible classifications.

b. Construct a tree diagram to exhibit all possible classifi-

cations of females.

19. L

ICENSE

LATE

UMBERS

Over the years, the state of Cali-

fornia has used different combinations of letters of the

alphabet and digits on its automobile license plates.

334

6 SETS AND COUNTING

87533_06_ch6_p313-352 1/30/08 10:01 AM Page 334

a. At one time, license plates were issued that consisted of

three letters followed by three digits. How many differ-

ent license plates can be issued under this arrangement?

b. Later on, license plates were issued that consisted of

three digits followed by three letters. How many differ-

ent license plates can be issued under this arrangement?

20. L

ICENSE

LATE

UMBERS

In recent years, the state of Cali-

fornia issued license plates using a combination of one let-

ter of the alphabet followed by three digits, followed by

another three letters of the alphabet. How many different

license plates can be issued using this configuration?

21. E

XAMS

An exam consists of ten true-or-false questions.

Assuming that every question is answered, in how many

different ways can a student complete the exam? In how

many ways can the exam be completed if a student can

leave some questions unanswered because, say, a penalty is

assessed for each incorrect answer?

22. W

ARRANTY

UMBERS

A warranty identification number for

a certain product consists of a letter of the alphabet fol-

lowed by a five-digit number. How many possible identifi-

cation numbers are there if the first digit of the five-digit

number must be nonzero?

23. L

OTTERIES

In a state lottery, there are 15 finalists eligible

for the Big Money Draw. In how many ways can the first,

second, and third prizes be awarded if no ticket holder can

win more than one prize?

24. T

ELEPHONE

UMBERS

a. How many seven-digit telephone numbers are possible

if the first digit must be nonzero?

b. How many direct-dialing numbers for calls within the

United States and Canada are possible if each number

consists of a 1 plus a three-digit area code (the first digit

of which must be nonzero) and a number of the type

described in part (a)?

25. S

LOT

ACHINES

A “lucky dollar” is one of the nine sym-

bols printed on each reel of a slot machine with three reels.

A player receives one of various payouts whenever one or

more “lucky dollars” appear in the window of the machine.

Find the number of winning combinations for which the

machine gives a payoff.

Hint: (a) Compute the number of ways in which the nine symbols

on the first, second, and third wheels can appear in the window

slot and (b) compute the number of ways in which the eight sym-

bols other than the “lucky dollar” can appear in the window slot.

The difference (a  b) is the number of ways in which the “lucky

dollar” can appear in the window slot. Why?

26. S

TAFFING

Student Painters, which specializes in painting

the exterior of residential buildings, has five people avail-

able to be organized into two-person and three-person

teams.

a. In how many ways can a two-person team be formed?

b. In how many ways can a three-person team be formed?

c. In how many ways can the company organize the avail-

able people into either two-person teams or three-

person teams?

In Exercises 27 and 28, determine whether the statement

is true or false. If it is true, explain why it is true. If it is

false, give an example to show why it is false.

27. There are 32 three-digit odd numbers that can be formed

from the digits 1, 2, 3, and 4.

28. If there are six toppings available, then the number of dif-

ferent pizzas that can be made is 2

, or 32, pizzas.

6.4 PERMUTATIONS AND COMBINATIONS 335

1. A tourist has a choice of eight flights, five hotel accommo-

dations, and eight tickets. By the generalized multiplication

principle, there are 8



8, or 320, travel packages.

2. There is a choice of two entrées, one dinner salad, one

French roll, three vegetables, three wines, two nonalcoholic

beverages, and six pastries. Therefore, by the generalized

multiplication principle, there are 2



or 216, combinations of dinner specials.

Permutations

In this section, we apply the generalized multiplication principle to the solution of two

types of counting problems. Both types involve determining the number of ways the

elements of a set can be arranged, and both play an important role in the solution of

problems in probability.

We begin by considering the permutations of a set. Specifically, given a set of dis-

tinct objects, a permutation of the set is an arrangement of these objects in a definite

6.3 Solutions to Self-Check Exercises

6.4 Permutations and Combinations

87533_06_ch6_p313-352 1/30/08 10:01 AM Page 335

order. To see why the order in which objects are arranged is important in certain prac-

tical situations, suppose the winning number for the first prize in a raffle is 9237. Then

the number 2973, although it contains the same digits as the winning number, cannot

be the first-prize winner (Figure 15). Here, the four objects—the digits 9, 2, 3, and 7—

are arranged in a different order; one arrangement is associated with the winning num-

ber for the first prize, and the other is not.

EXAMPLE 1

Let A  {a, b, c}.

a. Find the number of permutations of A.

b. List all the permutations of A with the aid of a tree diagram.

Solution

a. Each permutation of A consists of a sequence of the three letters a, b, c. There-

fore, we may think of such a sequence as being constructed by filling in each of

the three blanks

__ __ __

with one of the three letters. Now, there are three ways in which we can fill the

first blank—we can choose a, b, or c. Having selected a letter for the first blank,

there are two letters left for the second blank. Finally, there is but one way left to

fill the third blank. Schematically, we have

Invoking the generalized multiplication principle, we conclude that there are



1, or 6, permutations of the set A.

b. The tree diagram associated with this problem appears in Figure 16, and the six

permutations of A are abc, acb, bac, bca, cab, and cba.

Note

Notice that, when the possible outcomes are listed in the tree diagram in

Example 1, order is taken into account. Thus, (a, b, c) and (a, c, b) are two different

arrangements.

Combined

outcomes

(a, b, c)

(a, c, b)

(b, a, c)

(b, c, a)

(c, a, b)

(c, b, a

)

FIGURE 15

The same digits appear on each ticket,

but the order of the digits is different.

FIGURE 16

Permutations of three objects

336 6 SETS AND COUNTING

Winnin

g ticket

Nonwinnin

ticket

OMNI CLUB

RAFFLE

OMNI CLUB

RAFFLE

9237

2973

87533_06_ch6_p313-352 1/30/08 10:01 AM Page 336

n-Factorial

For any natural number n,

0!  1

n!  n1n  121n  2 2

EXAMPLE 2

Find the number of ways a baseball team consisting of nine people

can arrange themselves in a line for a group picture.

Solution

We want to determine the number of permutations of the nine members

of the baseball team. Each permutation in this situation consists of an arrangement

of the nine team members in a line. The nine positions can be represented by nine

blanks. Thus,

Position 123456789

There are nine ways to choose from among the nine players to fill the first position.

When that position is filled, eight players are left, which gives us eight ways to fill

the second position. Proceeding in a similar manner, we find that there are seven

ways to fill the third position, and so on. Schematically, we have

Number of ways to

987654321

fill each position

Invoking the generalized multiplication principle, we conclude that there are

987654321, or 362,880, ways the baseball team can be arranged for

the picture.

Whenever we are asked to determine the number of ways the objects of a set can

be arranged in a line, order is important. For example, if we take a picture of two

baseball players, A and B, then the two players can line up for the picture in two

ways, AB or BA, and the two pictures will be different.

Pursuing the same line of argument used in solving the problems in the last two

examples, we can derive an expression for the number of ways of permuting a set A

of n distinct objects taken n at a time. In fact, each permutation may be viewed as be-

ing obtained by filling each of n blanks with one and only one element from the set.

There are n ways of filling the first blank, followed by (n  1) ways of filling the sec-

ond blank, and so on. Thus, by the generalized multiplication principle, there are

n(n  1)(n  2) 321

ways of permuting the elements of the set A.

Before stating this result formally, let’s introduce a notation that will enable us to

write in a compact form many of the expressions that follow. We use the symbol n!

(read “n-factorial”) to denote the product of the first n positive integers.

For example,

10!  10

1  3,628,800

5!  5

1  120

4!  4

1  24

3!  3

1  6

2!  2

1  2

1!  1

###

########

6.4 PERMUTATIONS AND COMBINATIONS 337

87533_06_ch6_p313-352 1/30/08 10:01 AM Page 337

Using this notation, we can express the number of permutations of n distinct objects

taken n at a time

, denoted by P(n, n), as

P(n, n)  n!

In many situations, we are interested in determining the number of ways of per-

muting n distinct objects taken r at a time, where r  n. To derive a formula for com-

puting the number of ways of permuting a set consisting of n distinct objects taken r

at a time, we observe that each such permutation may be viewed as being obtained by

filling each of r blanks with precisely one element from the set. Now there are n ways

of filling the first blank, followed by (n  1) ways of filling the second blank, and so

on. Finally, there are (n  r  1) ways of filling the rth blank. We can represent this

argument schematically:

Using the generalized multiplication principle, we conclude that the number of ways of

permuting n distinct objects taken r at a time, denoted by P(n, r), is given by



r factors

we have the following formula.

Note

When r  n, Equation (6) reduces to

Note that 0!  1.

In other words, the number of permutations of a set of n distinct objects, taken all

together, is n!.

EXAMPLE 3

Compute (a) P(4, 4) and (b) P(4, 2), and interpret your results.

Solution

a. Note that 0!  1.

P14, 42

14  42!



 24

P1n, n2



 n!

P1n, r2 n1n  121n  22

1n  r  12

n  1

n  2

n  r  1

Number of ways

Position

338 6 SETS AND COUNTING

Since



Here we are multiplying by 1.



1n  r2!



3n1n  121n  2 2

1n  r  12431n  r 21n  r  12

1n  r21n  r  1 2

 3n1n  121n  2 2

1n  r  124

1n  r21n  r  1 2

n1n  121n  2 2

1n  r  12

1st 2nd 3rd rth

Permutations of n Distinct Objects

The number of permutations of n distinct objects taken r at a time is

(6)P1n, r2

1n  r2!

87533_06_ch6_p313-352 1/30/08 10:01 AM Page 338

Permutations of n Objects, Not All Distinct

Given a set of n objects in which n

objects are alike and of one kind, n

objects

are alike and of another kind, . . . , and n

objects are alike and of yet another

kind, so that

 n

n

 n

then the number of permutations of these n objects taken n at a time is given by

(7)

! n

This gives the number of permutations of four objects taken four at a time.

This is the number of permutations of four objects taken two at a time.

EXAMPLE 4

Let A  {a, b, c, d}.

a. Use Equation (6) to compute the number of permutations of the set A taken two

at a time.

b. Display the permutations of part (a) with the aid of a tree diagram.

Solution

a. Here, n  4 and r  2, so the required number of permutations is given by

b. The tree diagram associated with the problem is shown in Figure 17, and the

permutations of A taken two at a time are

ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc

EXAMPLE 5

Find the number of ways a chairman, a vice-chairman, a secretary,

and a treasurer can be chosen from a committee of eight members.

Solution

The problem is equivalent to finding the number of permutations of

eight distinct objects taken four at a time. Therefore, there are

ways of choosing the four officials from the committee of eight members.

The permutations considered thus far have been those involving sets of distinct ob-

jects. In many situations we are interested in finding the number of permutations of a

set of objects in which not all of the objects are distinct.

To establish Equation (7), let’s denote the number of such permutations by x.

Now, if we think of the n

objects as being distinct, then they can be permuted in n

ways. Similarly, if we think of the n

objects as being distinct, then they can be per-

muted in n

! ways, and so on. Therefore, if we think of the n objects as being distinct,

then, by the generalized multiplication principle, there are x





! per-

P18, 42

18  42!



 8

5  1680

 12

P14, 2 2

14  22!



 4

P14, 22

14  22!



 4

3  12

6.4 PERMUTATIONS AND COMBINATIONS 339

Combined

outcomes

(a, b)

(a, c)

(a, d)

(b, a)

(b, c)

(b, d)

(c, a)

(c, b)

(c, d)

(d, a)

(d, b

)

(d, c)

FIGURE 17

Permutations of four objects taken two at

a time

87533_06_ch6_p313-352 1/30/08 10:01 AM Page 339

mutations of these objects. But, the number of permutations of a set of n distinct

objects taken n at a time is just equal to n!. Therefore, we have

x(n





!)  n!

from which we deduce that

EXAMPLE 6

Find the number of permutations that can be formed from all the

letters in the word ATLANTA.

Solution

There are seven objects (letters) involved, so n  7. However, three of

them are alike and of one kind (the three As), while two of them are alike and of

another kind (the two Ts); hence, in this case we have n

 3, n

 2, n

 1 (the

one L), and n

 1 (the one N). Therefore, using Formula (7), there are

permutations.

APPLIED EXAMPLE 7

Management Decisions Weaver and Kline, a

stock brokerage firm, has received nine inquiries regarding new accounts.

In how many ways can these inquiries be directed to any three of the firm’s

account executives if each account executive is to handle three inquiries?

Solution

If we think of the nine inquiries as being slots arranged in a row with

inquiry 1 on the left and inquiry 9 on the right, then the problem can be thought

of as one of filling each slot with a business card from an account executive.

Then nine business cards would be used, of which three are alike and of one kind,

three are alike and of another kind, and three are alike and of yet another kind.

Thus, using Equation (7) with n  9 and n

 n

 3, there are

ways of assigning the inquiries.

Combinations

Until now we have dealt with permutations of a set—that is, with arrangements of the

objects of the set in which the order of the elements is taken into consideration. In

many situations one is interested in determining the number of ways of selecting r

objects from a set of n objects without any regard to the order in which the objects are

selected. Such a subset is called a combination.

For example, if one is interested in knowing the number of 5-card poker hands

that can be dealt from a standard deck of 52 cards, then the order in which the poker

hand is dealt is unimportant (Figure 18). In this situation, we are interested in deter-

mining the number of combinations of 5 cards (objects) selected from a deck (set) of

52 cards (objects). (We will solve this problem in Example 10.)

K K A

is considered

the same

hand as

A A

A KK

3! 3! 3!



 1680

3! 2! 1! 1!



 420

x 

! n

340 6 SETS AND COUNTING

FIGURE 18

87533_06_ch6_p313-352 1/30/08 10:01 AM Page 340

To derive a formula for determining the number of combinations of n objects

taken r at a time, written

we observe that each of the C(n, r) combinations of r objects can be permuted in r!

ways (Figure 19).

Thus, by the multiplication principle, the product r! C(n, r) gives the number of

permutations of n objects taken r at a time; that is,

r! C(n, r)  P(n, r)

from which we find

or, using Equation (6),

EXAMPLE 8

Compute and interpret the results of (a) C(4, 4) and (b) C(4, 2).

Solution

a. Recall that 0!  1.

This gives 1 as the number of combinations of four distinct objects taken four at

a time.

This gives 6 as the number of combinations of four distinct objects taken two at

a time.

APPLIED EXAMPLE 9

Committee Selection A Senate investigation

subcommittee of four members is to be selected from a Senate committee

of ten members. Determine the number of ways this can be done.

Solution

The order in which the members of the subcommittee are selected is

unimportant, and so the number of ways of choosing the subcommittee is given

C14, 22

2! 14  22!



2! 2!



 6

C14, 42

4! 14  42!



4! 0!

 1

C1n, r2

r! 1n  r2!

C1n, r2

P1n, r2

r! permutations

r objects

. . .

C(n, r

) boxes

r objects r objects

C1n, r2

6.4 PERMUTATIONS AND COMBINATIONS 341

FIGURE 19

Combinations of n Objects

The number of combinations of n distinct objects taken r at a time is given by

(where r  n) (8)C1n, r2

r! 1n  r2!

87533_06_ch6_p313-352 1/30/08 10:01 AM Page 341