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

96 TECHNIQUES OF COUNTING [CHAP. 5

Fig. 5-2

(b) Mark and Erik are to play a tennis tournament. The first person to win two games in a row or who wins a
total of three games wins the tournament. Find the number of ways the tournament can occur.

The tree diagram showing the possible outcomes of the tournament appears in Fig. 5-2(b). Here the tree is

constructed from top-down rather than from left-right. (That is, the “root” is on the top of the tree.) Note that

there are 10 endpoints, and the endpoints correspond to the following 10 ways the tournament can occur:

MM, MEMM, MEMEM, MEMEE, MEE, EMM, EMEMM, EMEME, EMEE, EE

The path from the beginning (top) of the tree to the endpoint describes who won which game in the tournament.

SolvedProblems

FACTORIAL NOTATION AND BINOMIAL COEFFICIENTS

5.1. Compute: (a) 4!, 5!; (b) 6!, 7!, 8!, 9!; (c) 50!.

(a)4!= 4 · 3 · 2 · 1 =24, 5!= 5 · 4 · 3 · 2 · 1 = 5 ( 24 )=120.

(b) Now use(n+ 1 )!=(n+ 1 )n!:

6 != 5 ( 5 !)= 6 ( 120 )= 720 , 8 != 8 ( 7 !)= 8 ( 5040 )=40 320,

7 != 7 ( 6 !)= 7 ( 720 )=5 040, 9 != 9 ( 8 !)= 9 (40 320)= 362880.

(c) Sincenis very large, we use Sterling’s approximation:n!=

√

2 πnnπe−n(wheree≈ 2 .718). Thus:

50 !≈N=

√

100 π 5050 e−^50

EvaluatingNusing a calculator, we getN= 3. 04 × 1064 (which has 65 digits).

5.2. Compute: (a)

13!

11!

;(b)

7!

10!

.

(a)

13!

11!

=

13 · 12 · 11 · 10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1

11 · 10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1

= 13 · 12 =156.

Alternatively, this could be solved as follows:

13!

11!

=

13 · 12 · 11!

11!

= 13 · 12 = 156.