1. Foundations of Factorials in Discrete Mathematics
In discrete mathematics, combinatorics, and probability theory, the factorial of a non-negative integer \(n\), denoted by the exclamation mark symbol \(n!\) (introduced by French mathematician Christian Kramp in 1808), represents the product of all positive integers less than or equal to \(n\):
$$n! = \prod_{k=1}^n k = n \times (n - 1) \times (n - 2) \times \dots \times 3 \times 2 \times 1$$The factorial operation is defined recursively by the difference equation:
$$n! = n \times (n - 1)! \quad \text{for } n \ge 1$$with the fundamental initial boundary condition:
$$0! = 1$$1.1 Rigorous Mathematical Proofs that \(0! = 1\)
The identity \(0! = 1\) is often considered counterintuitive, but it is mathematically mandatory for three distinct reasons:
- Algebraic Consistency: Rearranging the recursive definition gives \((n - 1)! = \frac{n!}{n}\). Substituting \(n = 1\): $$0! = (1 - 1)! = \frac{1!}{1} = \frac{1}{1} = 1$$ If \(0!\) were defined as 0, evaluating \((n-1)!\) would induce catastrophic division by zero across all higher factorials.
- Combinatorial Permutations of the Empty Set: The quantity \(n!\) counts the number of distinct ways to arrange \(n\) items in an ordered queue. An empty set (\(\emptyset\)) containing zero elements has exactly one unique arrangement: the trivial empty arrangement. Thus, \(0! = 1\).
- The Empty Product Convention: In mathematical algebra, the empty product of zero factors is universally defined as the multiplicative identity element (1), just as an empty sum equals the additive identity element (0).
2. Permutations and Combinations in Enumerative Combinatorics
Factorials form the mathematical engine underlying all counting problems where subsets of size \(r\) are selected from a universe of size \(n\).
2.1 Permutations: Order-Dependent Arrangements
A permutation counts the number of ways to select and arrange \(r\) elements from a set of \(n\) distinct elements, where the sequence order matters (such as podium places in an Olympic sprint, horse race trifectas, or alphanumeric passwords):
$$P(n, r) = {}_n P_r = \frac{n!}{(n - r)!} = n \times (n - 1) \times \dots \times (n - r + 1)$$When all \(n\) elements are arranged (\(r = n\)), \(P(n, n) = \frac{n!}{0!} = \frac{n!}{1} = n!\).
2.2 Combinations: Unordered Subsets
A combination counts the number of ways to select \(r\) elements from \(n\) distinct elements, where the arrangement order does not matter (such as drawing 5 cards in poker, selecting lottery balls, or choosing a committee of delegates):
$$C(n, r) = \binom{n}{r} = \frac{P(n, r)}{r!} = \frac{n!}{r! (n - r)!}$$The binomial coefficients \(\binom{n}{r}\) form the rows of Pascal's Triangle and govern the algebraic expansion of polynomials via the Binomial Theorem:
$$(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{n - k} y^k$$3. Euler's Gamma Function: Extending Factorials to the Complex Plane
In standard arithmetic, factorials are restricted to integer inputs. In 1729, Leonhard Euler solved the problem of interpolating factorials across continuous real and complex numbers by introducing the Gamma Function \(\Gamma(z)\):
$$\Gamma(z) = \int_0^\infty t^{z - 1} e^{-t} \, dt \quad (\operatorname{Re}(z) > 0)$$Using integration by parts, Euler proved the fundamental functional recurrence relation:
$$\Gamma(z + 1) = z \cdot \Gamma(z)$$For any positive integer \(n\), iterating this relation reveals that the Gamma function shifts the factorial by exactly one:
$$\Gamma(n + 1) = n! \iff n! = \Gamma(n + 1)$$3.1 Half-Integer Factorials and \(\sqrt{\pi}\)
Evaluating Euler's integral at \(z = \frac{1}{2}\) transforms via Gaussian integration into:
$$\Gamma\left(\frac{1}{2} \right) = \int_0^\infty t^{-1/2} e^{-t} \, dt = \sqrt{\pi}$$Consequently, fractional factorials are exact multiples of \(\sqrt{\pi}\):
$$\left(\frac{1}{2} \right)! = \Gamma\left(\frac{3}{2} \right) = \frac{1}{2} \Gamma\left(\frac{1}{2} \right) = \frac{\sqrt{\pi}}{2} \approx 0.8862269$$ $$\left(\frac{3}{2} \right)! = \frac{3}{2} \left(\frac{1}{2} \right)! = \frac{3\sqrt{\pi}}{4} \approx 1.3293403$$4. Stirling's Asymptotic Approximation
As \(n\) increases, \(n!\) grows with astonishing speed, eclipsing exponential growth. In statistical physics and thermodynamics, Scottish mathematician James Stirling derived an asymptotic formula for large \(n\):
$$n! \sim \sqrt{2\pi n} \left(\frac{n}{e} \right)^n \quad \text{as } n \to \infty$$Taking the natural logarithm yields the form indispensable in statistical mechanics (Boltzmann's entropy equation \(S = k_B \ln \Omega\)):
$$\ln(n!) \approx n \ln(n) - n + \frac{1}{2}\ln(2\pi n) \approx n \ln(n) - n$$Stirling's approximation achieves high precision rapidly: for \(n = 10\), the approximation error is less than \(0.8\%\); for \(n = 100\), the error drops below \(0.08\%\).
5. Benchmark Comparative Reference Table
The table below catalogues factorials from \(0!\) through \(15!\), illustrating exact values, scientific representations, and Stirling approximations.
| \(n\) | Exact Factorial (\(n!\)) | Scientific Notation | Stirling Approximation | Relative Error |
|---|---|---|---|---|
| 0 | 1 | \(1.000 \times 10^0\) | N/A | 0.00% |
| 1 | 1 | \(1.000 \times 10^0\) | \(0.922\) | -7.79% |
| 2 | 2 | \(2.000 \times 10^0\) | \(1.919\) | -4.05% |
| 3 | 6 | \(6.000 \times 10^0\) | \(5.836\) | -2.73% |
| 4 | 24 | \(2.400 \times 10^1\) | \(23.506\) | -2.06% |
| 5 | 120 | \(1.200 \times 10^2\) | \(118.019\) | -1.65% |
| 6 | 720 | \(7.200 \times 10^2\) | \(710.078\) | -1.38% |
| 7 | 5,040 | \(5.040 \times 10^3\) | \(4,980.396\) | -1.18% |
| 8 | 40,320 | \(4.032 \times 10^4\) | \(39,902.395\) | -1.04% |
| 9 | 362,880 | \(3.629 \times 10^5\) | \(359,536.873\) | -0.92% |
| 10 | 3,628,800 | \(3.629 \times 10^6\) | \(3,598,695.619\) | -0.83% |
| 12 | 479,001,600 | \(4.790 \times 10^8\) | \(475,687,486.47\) | -0.69% |
| 15 | 1,307,674,368,000 | \(1.308 \times 10^{12}\) | \(1,300,430,722,199\) | -0.55% |
6. Worked Probability Case Study: The 52-Card Deck Permutations
Scenario: A casino statistician models the probability of card shuffling collisions. A standard deck of playing cards contains \(N = 52\text{ cards}\). The statistician must: (1) calculate the total permutations of arrangements in a shuffled deck (\(52!\)), (2) express the result in scientific notation using Stirling's approximation, and (3) calculate the likelihood that any two thoroughly shuffled decks in history have ever shared the identical card sequence.
Step 1: Formulate the Permutation Count
Because all 52 distinct cards are arranged in order, the total possible unique sequences is:
$$\Omega = 52!$$
Step 2: Evaluate using Stirling's Approximation
$$52! \sim \sqrt{2\pi(52)} \left(\frac{52}{e} \right)^{52} = \sqrt{104\pi} \times (19.13)^{52}$$
Taking common base-10 logarithms:
$$\log_{10}(52!) = \sum_{k=1}^{52} \log_{10}(k) \approx 67.906648$$
Converting to scientific notation:
$$\Omega = 10^{0.906648} \times 10^{67} \approx 8.0658 \times 10^{67}\text{ unique permutations}$$
Step 3: Cosmic Probability Analysis
Assume 7 billion humans have each shuffled a deck 1,000 times per year since the invention of cards 700 years ago:
$$\text{Total Human Shuffles} \approx 7 \times 10^9 \times 1,000 \times 700 \approx 4.9 \times 10^{15}\text{ shuffles}$$
The ratio of shuffles to total possibilities is:
$$\frac{4.9 \times 10^{15}}{8.0658 \times 10^{67}} \approx 6.07 \times 10^{-53}$$
Whenever a deck is thoroughly shuffled, that exact sequence of cards has almost certainly never existed before in the entire history of the universe.
7. Frequently Asked Questions (FAQ)
Why does computing 171! cause an overflow error in calculators?
Standard 64-bit floating-point registers conform to the IEEE 754 standard, which has a maximum finite exponent threshold of \(2^{1024} \approx 1.797693 \times 10^{308}\). Because \(170! \approx 7.257 \times 10^{306}\), it fits within the limit. However, \(171! \approx 1.241 \times 10^{309}\), which exceeds the maximum possible value representable by a 64-bit double precision float, causing computers to output Infinity.
What is a double factorial (n!!)?
A double factorial \(n!!\) (not to be confused with \((n!)!\)) is the product of integers having the same parity (odd or even) down to 1 or 2: if \(n\) is odd, \(n!! = n \times (n-2) \times (n-4) \times \dots \times 3 \times 1\) (e.g., \(7!! = 7 \times 5 \times 3 \times 1 = 105\)); if \(n\) is even, \(n!! = n \times (n-2) \times \dots \times 4 \times 2\) (e.g., \(6!! = 6 \times 4 \times 2 = 48\)). Double factorials appear in quantum mechanics integrals and Taylor series expansions of \((1+x)^{1/2}\).
Can a negative integer have a factorial?
In standard real and complex analysis, the factorial of a negative integer (\(-1!, -2!, -3!, \dots\)) is undefined and diverges to infinity. Under Euler's Gamma function, \(\Gamma(z)\) has simple poles (infinite vertical asymptotes) at all non-positive integers \(z \in \{0, -1, -2, -3, \dots\}\).
How does Legendre's formula count the trailing zeros of a factorial?
Trailing zeros in \(n!\) are produced by factors of 10, which come from pairs of prime factors 2 and 5. Because factors of 2 are always more plentiful than 5, the count of trailing zeros equals the multiplicity of 5 in \(n!\), given by Legendre's formula: \(Z(n) = \sum_{k=1}^\infty \lfloor\frac{n}{5^k}\rfloor = \lfloor\frac{n}{5}\rfloor + \lfloor\frac{n}{25}\rfloor + \lfloor\frac{n}{125}\rfloor + \dots\). For example, \(100!\) has \(\lfloor 100/5 \rfloor + \lfloor 100/25 \rfloor = 20 + 4 = 24\) trailing zeros.