Difference between revisions of "Factorial"
m (→Definition) |
(→Introductory) |
||
(34 intermediate revisions by 17 users not shown) | |||
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. | ||
− | == | + | == Factorials Video == |
+ | [https://youtu.be/axFmwEI9ddk Factorials] | ||
− | + | == 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>. |
− | + | == Examples == | |
+ | * <math>0! = 1</math> (remember! this is 1, not 0! (the '!' was an exclamation mark, not a factorial sign)) | ||
+ | * <math>1! = 1</math> | ||
+ | * <math>2! = 2</math> | ||
+ | * <math>3! = 6</math> | ||
+ | * <math>4! = 24</math> | ||
+ | * <math>5! = 120</math> | ||
+ | * <math>6! = 720</math> | ||
+ | * <math>7! = 5040</math> | ||
+ | * <math>8! = 40320</math> | ||
+ | * <math>9! = 362880</math> | ||
+ | * <math>10! = 3628800</math> | ||
+ | * <math>11! = 39916800</math> | ||
+ | * <math>12! = 479001600</math> | ||
+ | * <math>13! = 6227020800</math> | ||
+ | * <math>14! = 87178291200</math> | ||
+ | * <math>15! = 1307674368000</math> | ||
+ | * <math>16! = 20922789888000</math> | ||
+ | * <math>17! = 355687428096000</math> | ||
+ | * <math>18! = 6402373705728000</math> | ||
+ | * <math>19! = 121645100408832000</math> | ||
+ | * <math>20! = 2432902008176640000</math> | ||
+ | * <math>21! = 51090942171709440000</math> | ||
+ | * <math>22! = 1124000727777607680000</math> | ||
+ | * <math>23! = 25852016738884976640000</math> | ||
+ | * <math>24! = 620448401733239439360000</math> | ||
+ | * <math>25! = 15511210043330985984000000</math> | ||
+ | * <math>26! = 403291461126605635584000000</math> | ||
+ | * <math>27! = 10888869450418352160768000000</math> | ||
+ | * <math>28! = 304888344611713860501504000000</math> | ||
+ | * <math>29! = 8841761993739701954543616000000</math> | ||
+ | * <math>30! = 265252859812191058636308480000000</math> | ||
+ | * <math>31! = 8222838654177922817725562880000000</math> | ||
+ | * <math>32! = 263130836933693530167218012160000000</math> | ||
+ | * <math>33! = 8683317618811886495518194401280000000</math> | ||
+ | * <math>34! = 295232799039604140847618609643520000000</math> | ||
+ | * <math>35! = 10333147966386144929666651337523200000000</math> | ||
+ | * <math>36! = 371993326789901217467999448150835200000000</math> | ||
+ | * <math>37! = 13763753091226345046315979581580902400000000</math> | ||
+ | * <math>38! = 523022617466601111760007224100074291200000000</math> | ||
+ | * <math>39! = 20397882081197443358640281739902897356800000000</math> | ||
+ | * <math>40! = 815915283247897734345611269596115894272000000000</math> | ||
+ | * <math>41! = 33452526613163807108170062053440751665152000000000</math> | ||
+ | * <math>42! = 1405006117752879898543142606244511569936384000000000</math> | ||
+ | * <math>43! = 60415263063373835637355132068513997507264512000000000</math> | ||
+ | * <math>44! = 2658271574788448768043625811014615890319638528000000000</math> | ||
+ | * <math>45! = 119622220865480194561963161495657715064383733760000000000</math> | ||
+ | * <math>46! = 5502622159812088949850305428800254892961651752960000000000</math> | ||
+ | * <math>47! = 258623241511168180642964355153611979969197632389120000000000</math> | ||
+ | * <math>48! = 12413915592536072670862289047373375038521486354677760000000000</math> | ||
+ | * <math>49! = 608281864034267560872252163321295376887552831379210240000000000</math> | ||
+ | * <math>50! = 30414093201713378043612608166064768844377641568960512000000000000</math> | ||
+ | * <math>51! = 1551118753287382280224243016469303211063259720016986112000000000000</math> | ||
+ | * <math>52! = 80658175170943878571660636856403766975289505440883277824000000000000</math> | ||
+ | * <math>53! = 4274883284060025564298013753389399649690343788366813724672000000000000</math> | ||
+ | * <math>54! = 230843697339241380472092742683027581083278564571807941132288000000000000</math> | ||
+ | * <math>55! = 12696403353658275925965100847566516959580321051449436762275840000000000000</math> | ||
+ | * <math>56! = 710998587804863451854045647463724949736497978881168458687447040000000000000</math> | ||
+ | * <math>57! = 40526919504877216755680601905432322134980384796226602145184481280000000000000</math> | ||
+ | * <math>58! = 2350561331282878571829474910515074683828862318181142924420699914240000000000000</math> | ||
+ | * <math>59! = 138683118545689835737939019720389406345902876772687432540821294940160000000000000</math> | ||
+ | * <math>60! = 8320987112741390144276341183223364380754172606361245952449277696409600000000000000</math> (Note: this number is 82 digits long with 14 terminal zeroes!) | ||
+ | * <math>100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000</math> | ||
+ | * <math>1000! = 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000</math> (Note: This number is 2568 digits long and has as much as 249 terminal zeroes!) | ||
+ | * <math>10000!</math> is 38660 digits long and has 2499 terminal zeroes! | ||
+ | * <math>100000!</math> is 456574 digits long and has 24999 terminal zeroes! | ||
+ | * <math>200000!</math> is 973751 digits long and has 49998 terminal zeroes! | ||
− | + | == Additional Information == | |
− | === Uses | + | By [[mathematical convention|convention]] and rules of an empty product, <math>0!</math> is given the value <math>1</math>. |
+ | |||
+ | 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 | ||
+ | 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> | ||
+ | in the prime factorization of <math>n!</math>? We can find it as the sum of powers of <math>p</math> in all the factors <math>1,2,\dots, n</math>; | ||
+ | but rather than counting the power of <math>p</math> in each factor, we shall count the number of factors divisible by a given power of <math>p</math>. Among the numbers <math>1,2,\dots,n</math>, exactly <math>\left\lfloor\frac n{p^k}\right\rfloor</math> are divisible by <math>p^k</math> (here <math>\lfloor\cdot\rfloor</math> is the [[floor function]]). The ones divisible by <math>p</math> give one power of <math>p</math>. The ones divisible by <math>p^2</math> give another power of <math>p</math>. Those divisible by <math>p^3</math> give yet another power of <math>p</math>. Continuing in this manner gives | ||
+ | |||
+ | <math>\left\lfloor\frac n{p}\right\rfloor+ | ||
+ | \left\lfloor\frac n{p^2}\right\rfloor+ | ||
+ | \left\lfloor\frac n{p^3}\right\rfloor+\dots</math> | ||
+ | |||
+ | for the power of <math>p</math> in the prime factorization of <math>n!</math>. The series is formally infinite, but the terms converge to <math>0</math> rapidly, as it is the reciprocal of an [[exponential function]]. For example, the power of <math>7</math> in <math>100!</math> is just | ||
+ | <math>\left\lfloor\frac {100}{7}\right\rfloor+ | ||
+ | \left\lfloor\frac {100}{49}\right\rfloor=14+2=16</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=== | ||
+ | *Find the unitsdigit 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]]) | ||
− | === See | + | ===Intermediate=== |
+ | *<math>\frac{((3!)!)!}{3!}=k*n!</math>, where <math>k</math> and <math>n</math> are positive integers and <math>n</math> is as large as possible. Find the value of <math>k+n</math>. | ||
+ | ([[2003 AIME I Problems/Problem 1|Source]]) | ||
+ | *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 Also == | ||
*[[Combinatorics]] | *[[Combinatorics]] | ||
+ | |||
+ | [[Category:Combinatorics]] | ||
+ | |||
+ | * A cool link to calculate factorials: http://www.nitrxgen.net/factorialcalc.php | ||
+ | On that link, you can calculate factorials from <math>0!</math> to as much as <math>100000!</math> |
Latest revision as of 15:40, 17 March 2024
The factorial is an important function in combinatorics and analysis, used to determine the number of ways to arrange objects.
Contents
[hide]Factorials Video
Definition
The factorial is defined for positive integers as . Alternatively, a recursive definition for the factorial is .
Examples
- (remember! this is 1, not 0! (the '!' was an exclamation mark, not a factorial sign))
- (Note: this number is 82 digits long with 14 terminal zeroes!)
- (Note: This number is 2568 digits long and has as much as 249 terminal zeroes!)
- is 38660 digits long and has 2499 terminal zeroes!
- is 456574 digits long and has 24999 terminal zeroes!
- is 973751 digits long and has 49998 terminal zeroes!
Additional Information
By convention and rules of an empty product, 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 unitsdigit of the sum
(Source)
Intermediate
- , where and are positive integers and is as large as possible. Find the value of .
(Source)
- 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)
See Also
- A cool link to calculate factorials: http://www.nitrxgen.net/factorialcalc.php
On that link, you can calculate factorials from to as much as