Difference between revisions of "Factorial"

m (proofreading)
m (Examples: added problem)
Line 31: Line 31:
=== Examples ===
=== Examples ===
* [[2006 AIME II Problems/Problem 3|2006 AIME II Problem 3]] on finding prime powers in a factorial
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=508851#p508851 AIME 2003I/1]
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=508851#p508851 AIME 2003I/1]

Revision as of 13:35, 24 July 2006

The factorial is an important function in combinatorics and analysis, used to determine the number of ways to arrange objects.


The factorial is defined for positive integers as $n!=n \cdot (n-1) \cdots 2 \cdot 1$. Alternatively, a recursive definition for the factorial is: $n!=n \cdot (n-1)!$.

Additional Information

By convention, $0!$ is given the value $1$.

The gamma function is a generalization of the factorial to values other than nonnegative integers.

Prime factorization

Since $n!$ is the product of all positive integers not exceeding $n$, it is clear that it is divisible by all primes $p\le n$, and not divisible by any prime $p>n$. But what is the power of a prime $p\le n$ in the prime factorization of $n!$? We can find it as the sum of powers of $p$ in all the factors $1,2,\dots, n$; but rather than counting the power of $p$ in each factor, we shall count the number of factors divisible by a given power of $p$. Among the numbers $1,2,\dots,n$, exactly $\left\lfloor\frac n{p^k}\right\rfloor$ are divisible by $p^k$ (here $\lfloor\cdot\rfloor$ is the floor function). The ones divisible by $p$ give one power of $p$. The ones divisible by $p^2$ give another power of $p$. Those divisible by $p^3$ give yet another power of $p$. Continuing in this manner gives

$\left\lfloor\frac n{p}\right\rfloor+ \left\lfloor\frac n{p^2}\right\rfloor+ \left\lfloor\frac n{p^3}\right\rfloor+\dots$

for the power of $p$ in the prime factorization of $n!$. The series is formally infinite, but the terms become $0$ pretty fast. For example, the power of $7$ in $100!$ is just $\left\lfloor\frac {100}{7}\right\rfloor+ \left\lfloor\frac {100}{49}\right\rfloor=14+2=16$ ($7^3=343$ is already greater than $100$).


The factorial is used in the definitions of combinations and permutations, as $n!$ is the number of ways to order $n$ distinct objects.


See also

Invalid username
Login to AoPS