Difference between revisions of "Factorial"
m (→Examples: added problem) |
m |
||
Line 3: | Line 3: | ||
=== Definition === | === Definition === | ||
− | The factorial is defined for positive | + | The factorial is defined for [[positive integer]]s as <math>n!=n \cdot (n-1) \cdots 2 \cdot 1 = \prod_{i=1}^n i</math>. Alternatively, a [[recursion|recursive definition]] for the factorial is <math>n!=n \cdot (n-1)!</math>. |
=== Additional Information === | === Additional Information === | ||
− | By convention, <math>0!</math> is given the value <math>1</math>. | + | By [[mathematical convention|convention]], <math>0!</math> is given the value <math>1</math>. |
− | The [[gamma function]] is a generalization of the factorial to values other than nonnegative | + | The [[gamma function]] is a generalization of the factorial to values other than [[nonnegative integer]]s. |
===[[Prime factorization]]=== | ===[[Prime factorization]]=== |
Revision as of 10:49, 8 August 2006
The factorial is an important function in combinatorics and analysis, used to determine the number of ways to arrange objects.
Contents
[hide]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 become pretty fast. 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