Counting · Definition

Factorial

discrete mathematicscounting

Before you start you need to know

It measures the number of ways to arrange \(n\) distinct objects, which is why it appears in almost every counting formula.

Definition

The factorial of an integer \(n\ge 0\), written \(n!\), is the product of the positive integers less than or equal to \(n\); that of zero is one by convention.

\[n!=n(n-1)\cdots 2\cdot 1,\quad 0!=1\]

The reason for the factorial is the multiplication principle: to arrange \(n\) distinct objects there are \(n\) options for the first place, \(n-1\) for the second, and so on until one is left. Six people in a row can be ordered in \(6!=720\) ways. This gives the most used property, \(n!=n\,(n-1)!\), which lets us simplify quotients such as \(\dfrac{8!}{6!}=8\cdot 7=56\).

The convention \(0!=1\) is not arbitrary: it keeps the relation \(n!=n\,(n-1)!\) valid for \(n=1\) and matches the fact that there is a single way to arrange zero objects, the empty list. It also makes later formulas, such as binomial coefficients, work without special cases at the ends.

The factorial grows very fast: \(10!=3628800\) and \(20!\) already exceeds \(2\times 10^{18}\). So when computing quotients of factorials, cancel the common factors instead of evaluating each factorial. To arrange objects under restrictions, such as two people who must stand together, treat the block as one more object and multiply by its internal orders.

Typical mistakes: thinking that \((a+b)!=a!+b!\) or that \(\dfrac{a!}{b!}=\dfrac{a}{b}\), neither of which is true (for instance \(\dfrac{6!}{4!}=30\), not \(\tfrac{3}{2}\)). In this course the factorial is applied only to non-negative integers.

Think about it

Why are there \(n!\) ways to arrange \(n\) distinct objects?

By the multiplication principle: \(n\) options for the first place, \(n-1\) for the second, etc., and the product of those options is \(n!\).

Is \(3!+2!\) equal to \(5!\)?

No: \(3!+2!=8\), while \(5!=120\). The factorial does not distribute over addition.

Exercises 10

  1. Compute \(5!\).
  2. In how many ways can 6 different people line up in a row?
  3. Compute \(\dfrac{6!}{4!}\).
  4. Why is \(0!\) defined as \(1\)?
  5. For \(n\ge 0\), which equals \((n+1)!\)?
  6. Compute \(\dfrac{8!}{6!\,2!}\).
  7. Simplify \(\dfrac{n!}{(n-2)!}\) for \(n\ge 2\).
  8. Words of 4 letters are formed from A, B, C, D (no repetition). How many start with A?
  9. Five people (3 men and 2 women) line up with the two women next to each other. In how many ways?
  10. How many trailing zeros does \(20!\) have? (Each trailing zero comes from a factor 10 = 2 · 5.)

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §6.3
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §9.2
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §1.2