Factorials!
by aoum, Mar 24, 2025, 10:50 PM
Factorials: Understanding the Mathematics of Permutations and Products
The factorial function is a fundamental concept in mathematics, particularly in combinatorics, algebra, and mathematical analysis. It is denoted by an exclamation mark (
) and represents the product of all positive integers from 1 up to a given number.
1. Definition of Factorials
The factorial of a non-negative integer
is defined as:
![\[
n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1,
\]](//latex.artofproblemsolving.com/8/0/5/805af30b05bc1810210b9b279b67551792eec9e2.png)
with the special case:
![\[
0! = 1,
\]](//latex.artofproblemsolving.com/3/8/5/3856e5581700a6feaa5368ed75b341f8004979ae.png)
by convention.
This definition is recursive and can also be written as:
![\[
n! = \begin{cases}
1 & \text{if } n = 0, \\
n \times (n-1)! & \text{if } n \geq 1.
\end{cases}
\]](//latex.artofproblemsolving.com/6/7/9/679f6a801d51fcdd067ebe40910ef19239829e04.png)
For example:
2. Properties of Factorials
Factorials exhibit many interesting and useful properties:
3. Applications of Factorials
Factorials are crucial in various areas of mathematics:
4. Stirling's Approximation
Since factorials grow rapidly, it is useful to have an approximation for large. Stirling’s approximation provides a way to estimate factorials:
![\[
n! \approx \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n,
\]](//latex.artofproblemsolving.com/e/f/3/ef39623f9c67940964011f16dad0def10eca5e18.png)
For large, the ratio of 
to this approximation approaches 1:
![\[
\lim_{n \to \infty} \frac{n!}{\sqrt{2 \pi n} \left( \frac{n}{e} \right)^n} = 1.
\]](//latex.artofproblemsolving.com/a/7/1/a71b520e2c6f28efec6c772abfb6c5a5ef633e78.png)
5. Factorials of Non-Integers: The Gamma Function
While the factorial function is defined only for non-negative integers, it can be extended to real and complex numbers through the Gamma function
:
![\[
\Gamma(z) = \int_0^\infty t^{z-1} e^{-t} \, dt,
\]](//latex.artofproblemsolving.com/8/0/0/8008c2f4a584768546523c8ecc6501d807516c4a.png)
which satisfies:
![\[
\Gamma(n) = (n-1)!, \quad n \text{ a positive integer}.
\]](//latex.artofproblemsolving.com/9/9/7/997b4a322cfb6371287e3760a6af158e21f70b08.png)
The Gamma function is a generalization of the factorial and allows us to evaluate "fractional factorials," such as:
![\[
\Gamma\left( \frac{1}{2} \right) = \sqrt{\pi}.
\]](//latex.artofproblemsolving.com/f/4/1/f413d13a5dd00d5b33df784afe4c4015496e1865.png)
6. Factorials in Combinatorial Identities
Factorials appear in many important combinatorial identities:
7. Special Values and Patterns in Factorials
8. Recursive Proof of the Factorial Formula
We can prove the basic factorial formula
using induction.
Base Case:
When
:
![\[
1! = 1,
\]](//latex.artofproblemsolving.com/7/f/e/7fe2d3cb5d006f5d187d2f0fd15276497df4d377.png)
which holds true.
Inductive Step:
Assume is true for some 
.
We need to show it holds for
:
![\[
(n+1)! = (n+1) \times n!,
\]](//latex.artofproblemsolving.com/a/6/b/a6b7de48c1731ddb850b8cc2a68b3d4c2cf54b78.png)
By the inductive hypothesis:
![\[
(n+1)! = (n+1) \times (n \times (n-1)!),
\]](//latex.artofproblemsolving.com/4/d/d/4dd5a249f121813d06905c5c71ee248fea1434c5.png)
which proves the formula by induction.
9. Conclusion
The factorial function is a cornerstone of mathematics, linking areas such as combinatorics, probability, and analysis. Its rapid growth, recursive structure, and connection to the Gamma function make it both fascinating and useful. Whether you are counting permutations or expanding binomials, factorials play a fundamental role in mathematical theory and applications.
10. References
The factorial function is a fundamental concept in mathematics, particularly in combinatorics, algebra, and mathematical analysis. It is denoted by an exclamation mark (
) and represents the product of all positive integers from 1 up to a given number.1. Definition of Factorials
The factorial of a non-negative integer
is defined as:![\[
n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1,
\]](http://latex.artofproblemsolving.com/8/0/5/805af30b05bc1810210b9b279b67551792eec9e2.png)
with the special case:
![\[
0! = 1,
\]](http://latex.artofproblemsolving.com/3/8/5/3856e5581700a6feaa5368ed75b341f8004979ae.png)
by convention.
This definition is recursive and can also be written as:
![\[
n! = \begin{cases}
1 & \text{if } n = 0, \\
n \times (n-1)! & \text{if } n \geq 1.
\end{cases}
\]](http://latex.artofproblemsolving.com/6/7/9/679f6a801d51fcdd067ebe40910ef19239829e04.png)
For example:
2. Properties of Factorials
Factorials exhibit many interesting and useful properties:
- Recursive Definition:
- Growth Rate: Factorials grow extremely rapidly. For large , is much larger than any polynomial or exponential function.
- Multiplicative Property: For any positive integers
and with 
:
![\[
n! = m! \times (m+1) \times (m+2) \times \dots \times n,
\]](//latex.artofproblemsolving.com/2/4/3/243963260193e1f6fc7bdd56dc3803010cc101e4.png)
- Division Property (Simplification): If :
![\[
\frac{n!}{m!} = n \times (n-1) \times \dots \times (m+1).
\]](//latex.artofproblemsolving.com/f/f/8/ff8712ddd0765937aecd250cafc56cd97b9f1a67.png)
and 
:![\[
n! = m! \times (m+1) \times (m+2) \times \dots \times n,
\]](http://latex.artofproblemsolving.com/2/4/3/243963260193e1f6fc7bdd56dc3803010cc101e4.png)
![\[
\frac{n!}{m!} = n \times (n-1) \times \dots \times (m+1).
\]](http://latex.artofproblemsolving.com/f/f/8/ff8712ddd0765937aecd250cafc56cd97b9f1a67.png)
3. Applications of Factorials
Factorials are crucial in various areas of mathematics:
- Combinatorics: Counting permutations and combinations relies on factorials.
- The number of ways to arrange objects (permutations) is:
![\[
P(n) = n!.
\]](//latex.artofproblemsolving.com/5/3/7/537448df9c36a9777da6e2a4ad86d0998800fb68.png)
- The number of ways to choose
objects from objects (combinations) is:
![\[
\binom{n}{r} = \frac{n!}{r!(n-r)!}.
\]](//latex.artofproblemsolving.com/9/5/e/95ec530a6a2deee086198f6b4294dc2d896e8d82.png)
- Binomial Theorem: Factorials appear in the expansion of powers of binomials:
![\[
(a + b)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} b^r = \sum_{r=0}^{n} \frac{n!}{r!(n-r)!} a^{n-r} b^r.
\]](//latex.artofproblemsolving.com/7/0/1/701f81ec3f4e200a7576acfc08ce6d1c9ab848fc.png)
- Probability Theory: Factorials determine the total outcomes and probabilities in discrete random processes.
- Algebra: Factorials are used to define polynomial coefficients, Taylor series, and generating functions.
- Number Theory: Factorials are linked to divisibility properties, prime factorizations, and Wilson's theorem.
![\[
P(n) = n!.
\]](http://latex.artofproblemsolving.com/5/3/7/537448df9c36a9777da6e2a4ad86d0998800fb68.png)
objects from ![\[
\binom{n}{r} = \frac{n!}{r!(n-r)!}.
\]](http://latex.artofproblemsolving.com/9/5/e/95ec530a6a2deee086198f6b4294dc2d896e8d82.png)
![\[
(a + b)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} b^r = \sum_{r=0}^{n} \frac{n!}{r!(n-r)!} a^{n-r} b^r.
\]](http://latex.artofproblemsolving.com/7/0/1/701f81ec3f4e200a7576acfc08ce6d1c9ab848fc.png)
4. Stirling's Approximation
Since factorials grow rapidly, it is useful to have an approximation for large
. Stirling’s approximation provides a way to estimate factorials:![\[
n! \approx \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n,
\]](http://latex.artofproblemsolving.com/e/f/3/ef39623f9c67940964011f16dad0def10eca5e18.png)
For large
, the ratio of 
to this approximation approaches 1:![\[
\lim_{n \to \infty} \frac{n!}{\sqrt{2 \pi n} \left( \frac{n}{e} \right)^n} = 1.
\]](http://latex.artofproblemsolving.com/a/7/1/a71b520e2c6f28efec6c772abfb6c5a5ef633e78.png)
5. Factorials of Non-Integers: The Gamma Function
While the factorial function is defined only for non-negative integers, it can be extended to real and complex numbers through the Gamma function
:![\[
\Gamma(z) = \int_0^\infty t^{z-1} e^{-t} \, dt,
\]](http://latex.artofproblemsolving.com/8/0/0/8008c2f4a584768546523c8ecc6501d807516c4a.png)
which satisfies:
![\[
\Gamma(n) = (n-1)!, \quad n \text{ a positive integer}.
\]](http://latex.artofproblemsolving.com/9/9/7/997b4a322cfb6371287e3760a6af158e21f70b08.png)
The Gamma function is a generalization of the factorial and allows us to evaluate "fractional factorials," such as:
![\[
\Gamma\left( \frac{1}{2} \right) = \sqrt{\pi}.
\]](http://latex.artofproblemsolving.com/f/4/1/f413d13a5dd00d5b33df784afe4c4015496e1865.png)
6. Factorials in Combinatorial Identities
Factorials appear in many important combinatorial identities:
- Pascal’s Identity:
![\[
\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1},
\]](//latex.artofproblemsolving.com/4/7/7/47701eb5446a34bde68ae5961597bde6f6c28faa.png)
- Vandermonde's Identity:
![\[
\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k}.
\]](//latex.artofproblemsolving.com/4/a/6/4a656630beec2e06f0c8fcd25a06b48b635219e6.png)
- Multinomial Coefficient: For non-negative integers
:
![\[
\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1! n_2! \dots n_k!},
\]](//latex.artofproblemsolving.com/c/6/3/c63389172c1fa38b0f85ceb8047fe9d15683c5b5.png)
giving the number of ways to partition items into 
groups.
![\[
\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1},
\]](http://latex.artofproblemsolving.com/4/7/7/47701eb5446a34bde68ae5961597bde6f6c28faa.png)
![\[
\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k}.
\]](http://latex.artofproblemsolving.com/4/a/6/4a656630beec2e06f0c8fcd25a06b48b635219e6.png)
:![\[
\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1! n_2! \dots n_k!},
\]](http://latex.artofproblemsolving.com/c/6/3/c63389172c1fa38b0f85ceb8047fe9d15683c5b5.png)
groups.7. Special Values and Patterns in Factorials
- Zero Factorial:
by convention, as it aligns with combinatorial definitions. - Double Factorials: Defined as:
![\[
n!! = n \times (n-2) \times (n-4) \times \dots,
\]](//latex.artofproblemsolving.com/0/5/4/0548ca23a09c61e84eeee0b913105775c56a2f52.png)
with:
![\[
n!! = 2^{\frac{n}{2}} \left( \frac{n}{2} \right)!, \text{ if } n \text{ is even}.
\]](//latex.artofproblemsolving.com/1/6/6/166c4ed9943989b54acca8b8725c4e58be35ccf0.png)
- Primorials: The product of the first prime numbers is denoted by:
![\[
p_n\# = 2 \times 3 \times 5 \times \dots \times p_n.
\]](//latex.artofproblemsolving.com/2/0/9/2098814cd7a296d938c08badbacf21173c73b123.png)
by convention, as it aligns with combinatorial definitions.![\[
n!! = n \times (n-2) \times (n-4) \times \dots,
\]](http://latex.artofproblemsolving.com/0/5/4/0548ca23a09c61e84eeee0b913105775c56a2f52.png)
![\[
n!! = 2^{\frac{n}{2}} \left( \frac{n}{2} \right)!, \text{ if } n \text{ is even}.
\]](http://latex.artofproblemsolving.com/1/6/6/166c4ed9943989b54acca8b8725c4e58be35ccf0.png)
![\[
p_n\# = 2 \times 3 \times 5 \times \dots \times p_n.
\]](http://latex.artofproblemsolving.com/2/0/9/2098814cd7a296d938c08badbacf21173c73b123.png)
8. Recursive Proof of the Factorial Formula
We can prove the basic factorial formula
using induction.Base Case:
When
:![\[
1! = 1,
\]](http://latex.artofproblemsolving.com/7/f/e/7fe2d3cb5d006f5d187d2f0fd15276497df4d377.png)
which holds true.
Inductive Step:
Assume
is true for some 
.We need to show it holds for
:![\[
(n+1)! = (n+1) \times n!,
\]](http://latex.artofproblemsolving.com/a/6/b/a6b7de48c1731ddb850b8cc2a68b3d4c2cf54b78.png)
By the inductive hypothesis:
![\[
(n+1)! = (n+1) \times (n \times (n-1)!),
\]](http://latex.artofproblemsolving.com/4/d/d/4dd5a249f121813d06905c5c71ee248fea1434c5.png)
which proves the formula by induction.
9. Conclusion
The factorial function is a cornerstone of mathematics, linking areas such as combinatorics, probability, and analysis. Its rapid growth, recursive structure, and connection to the Gamma function make it both fascinating and useful. Whether you are counting permutations or expanding binomials, factorials play a fundamental role in mathematical theory and applications.
10. References
- Wikipedia: Factorial
- Graham, R. L., Knuth, D. E., & Patashnik, O. Concrete Mathematics: A Foundation for Computer Science (1994).
- AoPS Wiki: Factorials
- Niven, I., Zuckerman, H., & Montgomery, H. An Introduction to the Theory of Numbers (2008).
March 2025