Difference between revisions of "Factorial"

Revision as of 23:22, 29 March 2011

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$
$48! = 12413915592536072670862289047373375038521486354677760000000000$
$49! = 608281864034267560872252163321295376887552831379210240000000000$
$50! = 30414093201713378043612608166064768844377641568960512000000000000$
$51! = 1551118753287382280224243016469303211063259720016986112000000000000$
$52! = 80658175170943878571660636856403766975289505440883277824000000000000$
$53! = 4274883284060025564298013753389399649690343788366813724672000000000000$
$54! = 230843697339241380472092742683027581083278564571807941132288000000000000$
$55! = 12696403353658275925965100847566516959580321051449436762275840000000000000$
$56! = 710998587804863451854045647463724949736497978881168458687447040000000000000$
$57! = 40526919504877216755680601905432322134980384796226602145184481280000000000000$
$58! = 2350561331282878571829474910515074683828862318181142924420699914240000000000000$
$59! = 138683118545689835737939019720389406345902876772687432540821294940160000000000000$
$60! = 8320987112741390144276341183223364380754172606361245952449277696409600000000000000$ (Note: this number is 82 digits long with 14 terminal zeroes!)
1000! = 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669

944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476 632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534 524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151 027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975 602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200 015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780 889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786 906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348 344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657 245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446 640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819 372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278 288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994 871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230 560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000

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