Combinatorics • Topic 4

Factorials

Factorials ( $n!$ ) grow incredibly fast and appear everywhere in counting. In Olympiad math, we often look at their number-theoretic properties, such as trailing zeros and prime factorization.

Definition

Definition (Factorial)

For a non-negative integer

n

n! = {1 n \times (n - 1)! if n = 0 if n > 0

Legendre's Formula

A crucial tool for finding the prime factorization of

n!

. The exponent of a prime

p

in the prime factorization of

n!

is denoted

v_{p} (n!)

Theorem (Legendre's Formula)

v_{p} (n!) = k = 1 \sum \infty ⌊ \frac{n}{p ^{k}} ⌋ = ⌊ \frac{n}{p} ⌋ + ⌊ \frac{n}{p ^{2}} ⌋ + ⌊ \frac{n}{p ^{3}} ⌋ + \dots

The sum terminates when $p^{k} > n$ .

Example (Trailing Zeros)

How many zeros are at the end of

100!

Proof. A zero is produced by a factor of $10 = 2 \times 5$ . In $100!$ , factors of 2 are abundant. The limiting factor is 5. Using Legendre's Formula for $p = 5$ :

v_{5} (100!) = ⌊ \frac{100}{5} ⌋ + ⌊ \frac{100}{25} ⌋ + ⌊ \frac{100}{125} ⌋ = 20 + 4 + 0 = 24

There are 24 trailing zeros. ∎

Approximation

For very large

n

, we use Stirling's Approximation:

n! \approx 2 πn (\frac{n}{e})^{n}

Practice Problems

Exercise (Problem 1)

Find the largest power of 2 that divides

50!

Exercise (Problem 2)

Simplify the expression

\frac{( n + 2 )! - ( n + 1 )!}{n !}

Exercise (Problem 3)

Find the last non-zero digit of

20!