# Difference between revisions of "Factorial"

m |
|||

Line 22: | Line 22: | ||

\left\lfloor\frac n{p^3}\right\rfloor+\dots</math> | \left\lfloor\frac n{p^3}\right\rfloor+\dots</math> | ||

− | for the power of <math>p</math> in the prime factorization of <math>n!</math>. The series is formally infinite, but the terms | + | for the power of <math>p</math> in the prime factorization of <math>n!</math>. The series is formally infinite, but the terms converge to <math>0</math> rapidly, as it is the reciprocal of an [[exponential function]]. For example, the power of <math>7</math> in <math>100!</math> is just |

<math>\left\lfloor\frac {100}{7}\right\rfloor+ | <math>\left\lfloor\frac {100}{7}\right\rfloor+ | ||

\left\lfloor\frac {100}{49}\right\rfloor=14+2=16</math> | \left\lfloor\frac {100}{49}\right\rfloor=14+2=16</math> | ||

(<math>7^3=343</math> is already greater than <math>100</math>). | (<math>7^3=343</math> is already greater than <math>100</math>). | ||

+ | |||

=== Uses === | === Uses === | ||

## Revision as of 19:13, 4 November 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 . Alternatively, a recursive definition for the factorial is .

### Additional Information

By convention, is given the value .

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

### Prime factorization

Since is the product of all positive integers not exceeding , it is clear that it is divisible by all primes , and not divisible by any prime . But what is the power of a prime in the prime factorization of ? We can find it as the sum of powers of in all the factors ; but rather than counting the power of in each factor, we shall count the number of factors divisible by a given power of . Among the numbers , exactly are divisible by (here is the floor function). The ones divisible by give one power of . The ones divisible by give another power of . Those divisible by give yet another power of . Continuing in this manner gives

for the power of in the prime factorization of . The series is formally infinite, but the terms converge to rapidly, as it is the reciprocal of an exponential function. For example, the power of in is just ( is already greater than ).

### Uses

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

### Examples

- 2006 AIME II Problem 3 on finding prime powers in a factorial