CHAP. 5] TECHNIQUES OF COUNTING 89
EXAMPLE 5.1 Suppose a college has 3 different history courses, 4 different literature courses, and 2 different
sociology courses.
(a)Thenumbermofwaysastudentcanchooseoneofeachkindofcoursesis:
m= 3 ( 4 )( 2 )= 24(b) The numbernof ways a student can choose just one of the courses is:n= 3 + 4 + 2 = 9There is a set theoretical interpretation of the above two principles. Specifically, supposen(A)denotes the
number of elements in a setA. Then:
(1) Sum Rule Principle:SupposeAandBare disjoint sets. Thenn(A∪B)=n(A)+n(B)(2) Product Rule Principle:LetA×Bbe the Cartesian product of setsAandB. Thenn(A×B)=n(A)·n(B)5.3Mathematical Functions
We discuss two important mathematical functions frequently used in combinatorics.Factorial Function
The product of the positive integers from 1 toninclusive is denoted byn!, read “nfactorial.” Namely:n!= 1 · 2 · 3 ·...·(n− 2 )(n− 1 )n=n(n− 1 )(n− 2 )·...· 3 · 2 · 1Accordingly, 1 !=1 andn!=n(n−l)!. It is also convenient to define 0!=1.EXAMPLE 5.2
(a)3!= 3 · 2 · 1 =6,4!= 4 · 3 · 2 · 1 =24,5= 5 · 4 != 5 ( 24 )=120.
(b)
12 · 11 · 10
3 · 2 · 1=12 · 11 · 10 · 9!
3 · 2 · 1 · 9!=12!
3! 9!and, more generally,n(n− 1 )···(n−r+ 1 )
r(r− 1 )··· 3 · 2 · 1=n(n− 1 )···(n−r+ 1 )(n−r)!
r(r− 1 )··· 3 · 2 · 1 ·(n−r)!=n!
r!(n−r)!(c)Forlargen,oneusesStirling’sapproximation(wheree= 2. 7128 ...):
n!=√
2 πnnne−n