Difference between revisions of "Factorial"
m (→Definition) |
(→Uses) |
||
| Line 11: | Line 11: | ||
The [[gamma function]] is a generalization of the factorial to values other than nonnegative integers. | The [[gamma function]] is a generalization of the factorial to values other than nonnegative integers. | ||
| + | ===[[Prime factorization]]=== | ||
| + | |||
| + | 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> | ||
| + | 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 | ||
| + | |||
| + | <math>\left\lfloor\frac n{p}\right\rfloor+ | ||
| + | \left\lfloor\frac n{p^2}\right\rfloor+ | ||
| + | \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 become <math>0</math> pretty fast. For example, the power of <math>7</math> in <math>100!</math> is just | ||
| + | <math>\left\lfloor\frac {100}{7}\right\rfloor+ | ||
| + | \left\lfloor\frac {100}{49}\right\rfloor=14+2=16</math> | ||
| + | (<math>7^3=343</math> is already greater than <math>100</math>). | ||
=== Uses === | === Uses === | ||
Revision as of 08:30, 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 
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). Now we will use the Lebesgue counting principle that says that the sum of several non-negative integers 
(the powers of in numbers in our case) can be found as 
. This immediately gives the formula
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.
