Difference between revisions of "Factorial"

(problems)
(Problems: bad template)
Line 33: Line 33:
 
==Problems==
 
==Problems==
 
===Introductory===
 
===Introductory===
*{[{intro}}}
+
*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 22:01, 14 January 2008

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 $n!=n \cdot (n-1) \cdots 2 \cdot 1 = \prod_{i=1}^n i$. Alternatively, a recursive definition for the factorial is $n!=n \cdot (n-1)!$.

Additional Information

By convention, $0!$ is given the value $1$.

The gamma function is a generalization of the factorial to values other than nonnegative integers.

Prime Factorization

Main article: Prime factorization

Since $n!$ is the product of all positive integers not exceeding $n$, it is clear that it is divisible by all primes $p\le n$, and not divisible by any prime $p>n$. But what is the power of a prime $p\le n$ in the prime factorization of $n!$? We can find it as the sum of powers of $p$ in all the factors $1,2,\dots, n$; but rather than counting the power of $p$ in each factor, we shall count the number of factors divisible by a given power of $p$. Among the numbers $1,2,\dots,n$, exactly $\left\lfloor\frac n{p^k}\right\rfloor$ are divisible by $p^k$ (here $\lfloor\cdot\rfloor$ is the floor function). The ones divisible by $p$ give one power of $p$. The ones divisible by $p^2$ give another power of $p$. Those divisible by $p^3$ give yet another power of $p$. Continuing in this manner gives

$\left\lfloor\frac n{p}\right\rfloor+ \left\lfloor\frac n{p^2}\right\rfloor+ \left\lfloor\frac n{p^3}\right\rfloor+\dots$

for the power of $p$ in the prime factorization of $n!$. The series is formally infinite, but the terms converge to $0$ rapidly, as it is the reciprocal of an exponential function. For example, the power of $7$ in $100!$ is just $\left\lfloor\frac {100}{7}\right\rfloor+ \left\lfloor\frac {100}{49}\right\rfloor=14+2=16$ ($7^3=343$ is already greater than $100$).

Uses

The factorial is used in the definitions of combinations and permutations, as $n!$ is the number of ways to order $n$ distinct objects.

Problems

Introductory

  • Find the units digit of the sum

\[\sum_{i=1}^{100}(i!)^{2}\]

$\mathrm{(A)}\,0\quad\mathrm{(B)}\,1\quad\mathrm{(C)}\,3\quad\mathrm{(D)}\,5\quad\mathrm{(E)}\,7\quad\mathrm{(F)}\,9$ (Source)

Intermediate

  • Let $P$ be the product of the first $100$ positive odd integers. Find the largest integer $k$ such that $P$ is divisible by $3^k .$

(Source)

Olympiad

  • Let $p_n (k)$ be the number of permutations of the set $\{ 1, \ldots , n \} , \; n \ge 1$, which have exactly $k$ fixed points. Prove that
    $\sum_{k=0}^{n} k \cdot p_n (k) = n!$.

(Source)

= See Also