Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Factorial"

(→‎Uses)
(added more explanation to where the prime factorization sum comes from)
Line 16: Line 16:
 
primes <math>p\le n</math> and not divisible by any prime <math>p>n</math>. But what is the power of a prime <math>p\le n</math>
 
primes <math>p\le n</math> and not divisible by any prime <math>p>n</math>. But what is the power of a prime <math>p\le n</math>
 
in the prime factorization of <math>n!</math>? We can find it as the sum of powers of <math>p</math> in all the factors <math>1,2,\dots, n</math>
 
in the prime factorization of <math>n!</math>? We can find it as the sum of powers of <math>p</math> in all the factors <math>1,2,\dots, n</math>
−
but rather than counting the power of <math>p</math> in each factor, we shall count the number of factors divisible by a given power of <math>p</math>. Among the numbers <math>1,2,\dots,n</math> exactly <math>\left\lfloor\frac n{p^k}\right\rfloor</math> are divisible by <math>p^k</math> (here <math>\lfloor\cdot\rfloor</math> is the [[floor function]]). Now we will use the [[Lebesgue counting principle]] that says that the sum of several non-negative integers <math>a_1,\dots, a_n</math> (the powers of <math>p</math> in numbers <math>1,2,\dots,n</math> in our case) can be found as <math>\sum_{k\ge 1}\#\{j: a_j\ge k\}</math>. This immediately gives the formula
+
but rather than counting the power of <math>p</math> in each factor, we shall count the number of factors divisible by a given power of <math>p</math>. Among the numbers <math>1,2,\dots,n</math> exactly <math>\left\lfloor\frac n{p^k}\right\rfloor</math> are divisible by <math>p^k</math> (here <math>\lfloor\cdot\rfloor</math> is the [[floor function]]). The ones divisible by <math>p</math> give one power of <math>p</math>.  The ones divisible by <math>p^2</math> give another power of <math>p</math>.  Those divisible by <math>p^3</math> give yet another power of <math>p</math>. Continuing in this manner gives
  
 
<math>\left\lfloor\frac n{p}\right\rfloor+
 
<math>\left\lfloor\frac n{p}\right\rfloor+

Revision as of 08:45, 3 July 2006

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

Definition

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$).

Uses

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

Examples

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Factorial&oldid=5842"