Factorial
Definition and Basic Properties
The factorial of a non-negative integer \( n \), denoted by \( n! \), is the product of all positive integers less than or equal to \( n \). Formally, it is defined as:
\[ n! = n \times (n-1) \times (n-2) \times \cdots \times 1 \]
For example, \( 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \). The factorial of 0 is defined to be 1, i.e., \( 0! = 1 \).
Historical Background
The concept of factorials dates back to ancient Indian mathematics, where it was used in combinatorial problems. The notation \( n! \) was introduced by the French mathematician Christian Kramp in 1808. Factorials play a crucial role in various fields of mathematics, including combinatorics, algebra, and mathematical analysis.
Applications in Combinatorics
Factorials are extensively used in combinatorics, particularly in the calculation of permutations and combinations. The number of ways to arrange \( n \) distinct objects is given by \( n! \). For example, the number of permutations of 3 objects (A, B, C) is \( 3! = 6 \).
In combinations, the number of ways to choose \( k \) objects from \( n \) distinct objects is given by the binomial coefficient:
\[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \]
Stirling's Approximation
For large values of \( n \), the factorial function grows very rapidly. Stirling's approximation provides an asymptotic formula for \( n! \):
\[ n! \approx \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \]
This approximation is useful in fields such as statistics and probability theory where exact computation of large factorials is impractical.
Factorials in Algebra
Factorials appear in various algebraic contexts, such as in the expansion of polynomials and in the coefficients of Taylor series expansions. For example, the Taylor series of the exponential function \( e^x \) is given by:
\[ e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!} \]
Gamma Function
The factorial function can be extended to non-integer values using the Gamma function, which is defined for complex numbers with a positive real part. The Gamma function \( \Gamma(n) \) is related to the factorial by:
\[ \Gamma(n+1) = n! \]
For non-integer \( z \), the Gamma function is given by the integral:
\[ \Gamma(z) = \int_0^\infty t^{z-1} e^{-t} \, dt \]
Computational Methods
Efficient computation of factorials is essential in computer science and numerical analysis. Recursive algorithms, iterative methods, and advanced techniques such as prime factorization and the use of lookup tables are employed to compute large factorials.
Factorials in Number Theory
In number theory, factorials are used in the study of prime numbers and in the formulation of various theorems. For example, Wilson's Theorem states that a natural number \( p > 1 \) is a prime if and only if:
\[ (p-1)! \equiv -1 \ (\text{mod} \ p) \]
Factorial Growth and Asymptotics
The factorial function grows faster than exponential functions but slower than double exponential functions. This rapid growth is characterized by the fact that \( n! \) exceeds any polynomial function for sufficiently large \( n \).