Difference between revisions of "Factorial"
(problems) |
(→Problems: bad template) |
||
Line 33: | Line 33: | ||
==Problems== | ==Problems== | ||
===Introductory=== | ===Introductory=== | ||
− | *{ | + | *Find the units digit of the sum |
+ | |||
+ | <cmath>\sum_{i=1}^{100}(i!)^{2}</cmath> | ||
+ | |||
+ | <math>\mathrm{(A)}\,0\quad\mathrm{(B)}\,1\quad\mathrm{(C)}\,3\quad\mathrm{(D)}\,5\quad\mathrm{(E)}\,7\quad\mathrm{(F)}\,9</math> | ||
([[2007 iTest Problems/Problem 6|Source]]) | ([[2007 iTest Problems/Problem 6|Source]]) | ||
===Intermediate=== | ===Intermediate=== | ||
Line 41: | Line 45: | ||
*Let <math>p_n (k) </math> be the number of permutations of the set <math>\{ 1, \ldots , n \} , \; n \ge 1 </math>, which have exactly <math>k </math> fixed points. Prove that <center><math>\sum_{k=0}^{n} k \cdot p_n (k) = n!</math>.</center> | *Let <math>p_n (k) </math> be the number of permutations of the set <math>\{ 1, \ldots , n \} , \; n \ge 1 </math>, which have exactly <math>k </math> fixed points. Prove that <center><math>\sum_{k=0}^{n} k \cdot p_n (k) = n!</math>.</center> | ||
([[1987 IMO Problems/Problem 1|Source]]) | ([[1987 IMO Problems/Problem 1|Source]]) | ||
− | |||
− | |||
=== See Also == | === See Also == |
Revision as of 21:01, 14 January 2008
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
- Main article: 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.
Problems
Introductory
- Find the units digit of the sum
(Source)
Intermediate
- Let be the product of the first positive odd integers. Find the largest integer such that is divisible by
(Source)
Olympiad
- Let be the number of permutations of the set , which have exactly fixed points. Prove that
.
(Source)