Difference between revisions of "Factorial"
(problems) |
|||
Line 1: | Line 1: | ||
The '''factorial''' is an important function in [[combinatorics]] and [[analysis]], used to determine the number of ways to arrange objects. | 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 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>. | 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 == | |
By [[mathematical convention|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>. | ||
Line 11: | Line 11: | ||
The [[gamma function]] is a generalization of the factorial to values other than [[nonnegative integer]]s. | The [[gamma function]] is a generalization of the factorial to values other than [[nonnegative integer]]s. | ||
− | == | + | ==Prime Factorization== |
− | + | {{main|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 | 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> | ||
Line 27: | Line 27: | ||
(<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 == | |
The factorial is used in the definitions of [[combinations]] and [[permutations]], as <math>n!</math> is the number of ways to order <math>n</math> distinct objects. | The factorial is used in the definitions of [[combinations]] and [[permutations]], as <math>n!</math> is the number of ways to order <math>n</math> distinct objects. | ||
− | === | + | ==Problems== |
+ | ===Introductory=== | ||
+ | *{[{intro}}} | ||
+ | ([[2007 iTest Problems/Problem 6|Source]]) | ||
+ | ===Intermediate=== | ||
+ | *Let <math>P </math> be the product of the first <math>100</math> [[positive integer | positive]] [[odd integer]]s. Find the largest integer <math>k </math> such that <math>P </math> is divisible by <math>3^k .</math> | ||
+ | ([[2006 AIME II Problems/Problem 3|Source]]) | ||
+ | ===Olympiad=== | ||
+ | *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]]) | ||
− | |||
− | |||
− | === See | + | === See Also == |
*[[Combinatorics]] | *[[Combinatorics]] | ||
+ | |||
+ | [[Category:Combinatorics]] |
Revision as of 22:00, 14 January 2008
The factorial is an important function in combinatorics and analysis, used to determine the number of ways to arrange objects.
Contents
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
- {[{intro}}}
(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)