Factorial

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)!$ .

Examples

$0! = 1$
$1! = 1$
$2! = 2$
$3! = 6$
$4! = 24$
$5! = 120$
$6! = 720$
$7! = 5040$
$8! = 40320$
$9! = 362880$
$10! = 3628800$
$11! = 39916800$
$12! = 479001600$
$13! = 6227020800$
$14! = 87178291200$
$15! = 1307674368000$
$16! = 20922789888000$
$17! = 355687428096000$
$18! = 6402373705728000$
$19! = 121645100408832000$
$20! = 2432902008176640000$
$21! = 51090942171709440000$
$22! = 1124000727777607680000$
$23! = 25852016738884976640000$
$24! = 620448401733239439360000$
$25! = 15511210043330985984000000$
$26! = 403291461126605635584000000$
$27! = 10888869450418352160768000000$
$28! = 304888344611713860501504000000$
$29! = 8841761993739701954543616000000$
$30! = 265252859812191058636308480000000$
$31! = 8222838654177922817725562880000000$
$32! = 263130836933693530167218012160000000$
$33! = 8683317618811886495518194401280000000$
$34! = 295232799039604140847618609643520000000$
$35! = 10333147966386144929666651337523200000000$
$36! = 371993326789901217467999448150835200000000$
$37! = 13763753091226345046315979581580902400000000$
$38! = 523022617466601111760007224100074291200000000$
$39! = 20397882081197443358640281739902897356800000000$
$40! = 815915283247897734345611269596115894272000000000$
$41! = 33452526613163807108170062053440751665152000000000$
$42! = 1405006117752879898543142606244511569936384000000000$
$43! = 60415263063373835637355132068513997507264512000000000$
$44! = 2658271574788448768043625811014615890319638528000000000$
$45! = 119622220865480194561963161495657715064383733760000000000$
$46! = 5502622159812088949850305428800254892961651752960000000000$
$47! = 258623241511168180642964355153611979969197632389120000000000$

(By now, factorials have gotten as big as 60 digits long!)

$48! = 12413915592536072670862289047373375038521486354677760000000000$
$49! = 608281864034267560872252163321295376887552831379210240000000000$
$50! = 30414093201713378043612608166064768844377641568960512000000000000$

( $50!$ is 65 digits long and has 12 terminal zeroes already!)

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)

Page

Toolbox

Search