Difference between revisions of "Factorial"
(added more explanation to where the prime factorization sum comes from) |
m (proofreading) |
||
Line 3: | Line 3: | ||
=== Definition === | === Definition === | ||
− | The factorial is defined for positive integers as <math>n!=n \cdot (n-1) \cdots 2 \cdot 1</math> Alternatively, a [[recursion|recursive definition]] for the factorial is: <math>n!=n \cdot (n-1)!</math>. | + | The factorial is defined for positive integers as <math>n!=n \cdot (n-1) \cdots 2 \cdot 1</math>. Alternatively, a [[recursion|recursive definition]] for the factorial is: <math>n!=n \cdot (n-1)!</math>. |
=== Additional Information === | === Additional Information === | ||
Line 14: | Line 14: | ||
Since <math>n!</math> is the product of all positive integers not exceeding <math>n</math>, it is clear that it is divisible by all | Since <math>n!</math> is the product of all positive integers not exceeding <math>n</math>, it is clear that it is divisible by all | ||
− | 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]]). 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 | + | 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 11:52, 3 July 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.