Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 5] TECHNIQUES OF COUNTING 101

TREE DIAGRAMS

5.25. TeamsAandBplay in a tournament. The first team to win three games wins the tournament. Find the

numbernof possible ways the tournament can occur.

Construct the appropriate tree diagram in Fig. 5-3(a). The tournament can occur in 20 ways:

AAA,AABA,AABBA,AABBB,ABAA,ABABA,ABABB,ABBAA,ABBAB,ABBB,

BBB,BBAB,BBAAB,BBAAA,BABB,BABAB,BABAA,BAABB,BAABA,BAAA

Fig. 5-3

5.26. Construct the tree diagram that gives the permutations of {a,b,c}.

The tree diagram appears in Fig. 5-3(b). There are six permutations, and they are listed on the bottom of the diagram.

MISCELLANEOUS PROBLEMS

5.27. There are 12 students in a class. Find the numbernof ways that the 12 students can take 3 tests if

4 students are to take each test.

There areC( 12 , 4 )=495 ways to choose 4 of the 12 students to take the first test. Following this, there are

C( 8 , 4 )=70 ways to choose 4 of the remaining 8 students to take the second test. The remaining students take the

third test. Thus:

n= 70 ( 495 )=34 650

5.28. Prove Theorem (Binomial Theorem) 5.2:(a+b)n=

∑n

r= 0

(

n

r

)

an−rbr.

The theorem is true forn=1, since

∑^1

r= 0

(

1

r

)

a^1 −rbr=

(

1

0

)

a^1 b^0 +

(

1

1

)

a^0 b^1 =a+b=(a+b)^1

We assume the theorem is true for(a+b)nand prove it is true for(a+b)n+1.

(a+b)n+^1 =(a+b) (a+b)n

=(a+b)[an+(n 1 )an−^1 b+···+(nr− 1 )an−r+^1 br−^1 +(nr)an−rbr+···(n 1 )abn−^1 +bn]