Mathematics for Computer Science

14.5. Products 427

Exponentiating then gives

nn

en^1

 nŠ 

nnC^1

en^1

: (14.28)

This means thatnŠis within a factor ofnofnn=en^1.

14.5.1 Stirling’s Formula

nŠis probably the most commonly used product in discrete mathematics, and so
mathematicians have put in the effort to find much better closed-form bounds on its
value. The most useful bounds are given in Theorem 14.5.1.

Theorem 14.5.1(Stirling’s Formula).For alln 1 ,

nŠD

p

2n

n

e

n

e.n/

where

1

12nC 1

.n/

1

12n

:

Theorem 14.5.1 can be proved by induction onn, but the details are a bit painful
(even for us) and so we will not go through them here.
There are several important things to notice about Stirling’s Formula. First,.n/
is always positive. This means that

nŠ >

p

2n

n

e

n

(14.29)

for alln 2 NC.
Second,.n/tends to zero asngets large. This means that

nŠ

p

2n

n

e

n

(14.30)

which is rather surprising. After all, who would expect bothandeto show up in
a closed-form expression that is asymptotically equal tonŠ?
Third,.n/is small even for small values ofn. This means that Stirling’s For-
mula provides good approximations fornŠfor most all values ofn. For example, if
we use p
2n

n

e

n

as the approximation fornŠ, as many people do, we are guaranteed to be within a
factor of
e.n/e

1

12n