Difference between revisions of "Factorial"

(Examples)
m (Examples)
(12 intermediate revisions by 8 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 ==
 
== Definition ==
Line 6: Line 9:
  
 
== Examples ==
 
== Examples ==
* <math>0! = 1</math>
+
* <math>0! = 1</math> (remember! this is 1, not 0! (the '!' was an exclamation mark, not a factorial sign))
 
* <math>1! = 1</math>
 
* <math>1! = 1</math>
 
* <math>2! = 2</math>
 
* <math>2! = 2</math>
Line 67: Line 70:
 
* <math>59! = 138683118545689835737939019720389406345902876772687432540821294940160000000000000</math>
 
* <math>59! = 138683118545689835737939019720389406345902876772687432540821294940160000000000000</math>
 
* <math>60! = 8320987112741390144276341183223364380754172606361245952449277696409600000000000000</math> (Note: this number is 82 digits long with 14 terminal zeroes!)
 
* <math>60! = 8320987112741390144276341183223364380754172606361245952449277696409600000000000000</math> (Note: this number is 82 digits long with 14 terminal zeroes!)
* 1000! = 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669
+
* <math>100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000</math>
944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476
+
* <math>1000! = 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000</math> (Note: This number is 2568 digits long and has as much as 249 terminal zeroes!)
632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534
+
* <math>10000!</math> is 38660 digits long and has 2499 terminal zeroes!
524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151
+
* <math>100000!</math> is 456574 digits long and has 24999 terminal zeroes!
027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975
+
* <math>200000!</math> is 973751 digits long and has 49998 terminal zeroes!
602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200
 
015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780
 
889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786
 
906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348
 
344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657
 
245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446
 
640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819
 
372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278
 
288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994
 
871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230
 
560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000
 
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 
000000000000000000
 
  
 
== Additional Information ==
 
== Additional Information ==
  
By [[mathematical convention|convention]], <math>0!</math> is given the value <math>1</math>.
+
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.
 
The [[gamma function]] is a generalization of the factorial to values other than [[nonnegative integer]]s.
Line 121: Line 111:
 
([[2007 iTest Problems/Problem 6|Source]])
 
([[2007 iTest Problems/Problem 6|Source]])
 
===Intermediate===
 
===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>
 
*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]])
 
([[2006 AIME II Problems/Problem 3|Source]])
 +
 
===Olympiad===
 
===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>
 
*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>
Line 133: Line 126:
  
 
* A cool link to calculate factorials: http://www.nitrxgen.net/factorialcalc.php
 
* 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>200000!</math>

Revision as of 18:57, 12 July 2022

The factorial is an important function in combinatorics and analysis, used to determine the number of ways to arrange objects.

Factorials Video

Factorials

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$ (remember! this is 1, not 0! (the '!' was an exclamation mark, not a factorial sign))
  • $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!)
  • $100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000$
  • $1000! = 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000$ (Note: This number is 2568 digits long and has as much as 249 terminal zeroes!)
  • $10000!$ is 38660 digits long and has 2499 terminal zeroes!
  • $100000!$ is 456574 digits long and has 24999 terminal zeroes!
  • $200000!$ is 973751 digits long and has 49998 terminal zeroes!

Additional Information

By convention and rules of an empty product, $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

  • $\frac{((3!)!)!}{3!}=k*n!$, where $k$ and $n$ are positive integers and $n$ is as large as possible. Find the value of $k+n$.

(Source)

  • 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

On that link, you can calculate factorials from $0!$ to as much as $200000!$