Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Factorial"
(→‎Introductory)
 
(35 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.
  
−
=== Definition ===
+
== Factorials Video ==
 +
[https://youtu.be/axFmwEI9ddk Factorials]
  
−
The factorial is defined for positive integers as <math>n!=n \cdot (n-1) \cdots 2 \cdot 1</math>  Alternatively, a recursive definition for the factorial is: <math>n!=n \cdot (n-1)!</math>.
+
== Definition ==
  
−
=== Additional Information ===
+
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>.
  
−
By convention, <math>0!</math> is given the value <math>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!
  
−
The [[gamma function]] is a generalization of the factorial to values other than nonnegative integers.
+
== 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.
  
−
=== Examples ===
+
==Problems==
 +
===Introductory===
 +
*Find the unitsdigit of the sum
 +
 
 +
<cmath>\sum_{i=1}^{100}(i!)^{2}</cmath>
  
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=508851#p508851 AIME 2003I/1]
+
<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 also ===
+
===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.

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 unitsdigit 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 $100000!$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Factorial&oldid=217046"