Arithmetic

Factorial

The Exclamation Mark That Changed Mathematics

Before 1808, mathematicians wrote factorial clumsily: "1·2·3·...·n" or "[n]" or "|n". **Christian Kramp**, an Alsatian mathematician, decided: enough. He introduced the notation **n!** - and the exclamation mark perfectly captured the essence: factorial is a mathematical SHOUT, a number that explodes beyond imagination.

I use the notation n! for the product 1·2·3...n, because it is convenient. - Christian Kramp, 1808

Factorial 52! (ways to shuffle a deck of cards) exceeds the number of atoms in the observable Universe. Every shuffle is almost certainly unique in all of human history. You have never held the same sequence of cards that anyone else has ever held. **Never**.

How many ways can a deck of 52 cards be arranged? 52! ≈ 8×10⁶⁷. That's more than the atoms in the observable Universe! Every shuffle is almost certainly unique in all of human history. Factorial is a simple operation with staggering results.

**Cryptography:** key spaces, permutation ciphers
**Combinatorics:** counting arrangements, probabilities
**Algorithms:** complexity of brute-force search

The Factorial

The **factorial** of n (written n!) is the product of all positive integers from 1 to n. It's a fundamental operation in combinatorics.

**Definition:** n! = 1 × 2 × 3 × ... × n **By convention:** 0! = 1 (empty product) **Recursion:** n! = n × (n-1)!

The exclamation mark notation for factorial was introduced by Christian Kramp in 1808. Before that it was written out clumsily.

What is 5!?

Factorial Growth

Factorial grows **incredibly fast** - faster than any exponential. Already 20! exceeds the number of atoms on Earth.

**Growth hierarchy:** log n < n < n² < 2ⁿ < n! < nⁿ Factorial is "super-exponential". Algorithms with O(n!) complexity are practically infeasible for n > 15 - 20.

The explosive growth makes brute-force enumeration of all permutations impossible even for small n. This is the foundation of the complexity of many algorithmic problems.

Which is larger: 10! or 2¹⁰?

Combinatorial Meaning

Factorial arises naturally when counting **permutations** - the number of ways to order n objects.

**Where else factorial appears:** • Taylor series: eˣ = Σ xⁿ/n! • Probability: n! in distribution formulas • Euler's number: e = Σ 1/n! • Gamma function: Γ(n+1) = n! (generalization to real numbers)

Factorial is the bridge between discrete and continuous mathematics.

How many ways can 4 people be seated at a round table (rotations considered the same)?

Stirling's Approximation

**Stirling's approximation** estimates factorial for large n. It lets you gauge n! without computing the full product.

**Refined formula:** n! = √(2πn) × (n/e)ⁿ × e^(θ/(12n)) where 0 < θ < 1. With this correction, the error is < 1/(12n) for any n.

Stirling's approximation is indispensable in statistics, thermodynamics, and information theory - wherever large factorials appear.

Factorial grows like the exponential 2ⁿ or nⁿ

Factorial grows faster than exponentials but slower than nⁿ

2ⁿ multiplies by the constant factor 2. n! multiplies by the growing factor n. So n! ≫ 2ⁿ. But nⁿ = n×n×...×n (n times), with every factor equal to n, whereas in n! the factors go from 1 to n. Hierarchy: 2ⁿ < n! < nⁿ.

Stirling's formula gives n! ≈ √(2πn) × (n/e)ⁿ. Which statement is true?

Key Ideas

n! = 1 × 2 × ... × n, 0! = 1
Grows faster than exponential: n! ≫ 2ⁿ
Combinatorics: permutations, combinations
Stirling: n! ≈ √(2πn)(n/e)ⁿ

Вопросы для размышления

Why is 0! = 1 a natural definition?
How would you estimate the order of magnitude of 1000! without a calculator?
Can factorial be defined for fractional numbers?