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

90 TECHNIQUES OF COUNTING [CHAP. 5

Binomial Coefficients

The symbol

(

n

r

)

, read “nCr”or“nChooser,” whererandnare positive integers withr≤n, is defined as

follows:
(
n
r

)

=

n(n− 1 )···(n−r+ 1 )

r(r− 1 )... 3 · 2 · 1

or equivalently

(

n

r

)

=

n!

r!(n−r)!

Note thatn−(n−r)=r. This yields the following important relation.

Lemma 5.1:

(

n

n−r

)

=

(

n

r

)

or equivalently,

(

n

a

)

=

(

n

b

)

wherea+b=n.

Motivated by that fact that we defined 0!=1, we define:

(

n

0

)

=

n!

0 !n!

=1 and

(

0

0

)

=

0!

0! 0!

= 1

EXAMPLE 5.3

(a)

(

8

2

)

=

8 · 7

2 · 1

=28;

(

9

4

)

=

9 · 8 · 7 · 6

4 · 3 · 2 · 1

=126;

(

12

5

)

=

12 · 11 · 10 · 9 · 8

5 · 4 · 3 · 2 · 1

=792.

Note that

(

n

r

)

has exactlyrfactors in both the numerator and the denominator.

(b) Suppose we want to compute

(

10

7

)

. There will be 7 factors in both the numerator and the denominator.
However, 10− 7 =3. Thus, we use Lemma 5.1 to compute:
(
10
7

)

=

(

10

3

)

=

10 · 9 · 8

3 · 2 · 1

= 120

Binomial Coefficients and Pascal’s Triangle

The numbers

(

n

r

)

are calledbinomial coefficients, since they appear as the coefficients in the expansion of

(a+b)n. Specifically:

Theorem (Binomial Theorem) 5.2: (a+b)n=

∑n

k= 0

(

n

r

)

an−kbk

The coefficients of the successive powers ofa+bcan be arranged in a triangular array of numbers, called
Pascal’striangle, aspicturedinFig.5-1. ThenumbersinPascal’strianglehavethefollowinginterestingproperties:

(i) The first and last number in each row is 1.

(ii) Every other number can be obtained by adding the two numbers appearing above it. For example:

10 = 4 + 6 , 15 = 5 + 10 , 20 = 10 + 10.

Since these numbers are binomial coefficients, we state the above property formally.