Editing Factorial (section)

==Applications==
The earliest uses of the factorial function involve counting [[permutations]]: there are <math>n!</math> different ways of arranging <math>n</math> distinct objects into a sequence.<ref name="ConwayGuy1998">{{Cite book |title=The Book of Numbers |title-link=The Book of Numbers (math book) |last1=Conway |first1=John H. |last2=Guy |first2=Richard |year=1998 |publisher=Springer Science & Business Media |isbn=978-0-387-97993-9 |language=en |author-link=John Horton Conway |author-link2=Richard K. Guy |pages=55–56|contribution=Factorial numbers}}</ref> Factorials appear more broadly in many formulas in [[combinatorics]], to account for different orderings of objects. For instance the [[binomial coefficient]]s <math>\tbinom{n}{k}</math> count the {{nowrap|<math>k</math>-element}} [[combination]]s (subsets of {{nowrap|<math>k</math> elements)}} from a set with {{nowrap|<math>n</math> elements,}} and can be computed from factorials using the formula{{sfn|Graham|Knuth|Patashnik|1988|p=156}} <math display=block>\binom{n}{k}=\frac{n!}{k!(n-k)!}.</math> The [[Stirling numbers of the first kind]] sum to the factorials, and count the permutations {{nowrap|of <math>n</math>}} grouped into subsets with the same numbers of cycles.<ref>{{cite book | last = Riordan | first = John | author-link = John Riordan (mathematician) | mr = 0096594 | page = 76 | publisher = Chapman & Hall | series = Wiley Publications in Mathematical Statistics | title = An Introduction to Combinatorial Analysis | year = 1958}} [https://books.google.com/books?id=Sbb_AwAAQBAJ&pg=PA76 Reprinted], Princeton Legacy Library, Princeton University Press, 2014, {{isbn|9781400854332}}.</ref> Another combinatorial application is in counting [[derangement]]s, permutations that do not leave any element in its original position; the number of derangements of <math>n</math> items is the [[Rounding|nearest integer]] {{nowrap|to <math>n!/e</math>.{{sfn|Graham|Knuth|Patashnik|1988|p=195}}}}

In [[algebra]], the factorials arise through the [[binomial theorem]], which uses binomial coefficients to expand powers of sums.{{sfn|Graham|Knuth|Patashnik|1988|p=162}} They also occur in the coefficients used to relate certain families of polynomials to each other, for instance in [[Newton's identities]] for [[symmetric polynomial]]s.<ref>{{cite journal | last = Randić | first = Milan | doi = 10.1007/BF01205340 | issue = 1 | journal = Journal of Mathematical Chemistry | mr = 895533 | pages = 145–152 | title = On the evaluation of the characteristic polynomial via symmetric function theory | volume = 1 | year = 1987| s2cid = 121752631 }}</ref> Their use in counting permutations can also be restated algebraically: the factorials are the [[order of a group|orders]] of finite [[symmetric group]]s.<ref>{{cite book|title=Groups and Characters|first=Victor E.|last=Hill|publisher=Chapman & Hall|year=2000|mr=1739394|isbn=978-1-351-44381-4|page=70|contribution=8.1 Proposition: Symmetric group {{math|''S''<sub>''n''</sub>}}|contribution-url=https://books.google.com/books?id=yjL3DwAAQBAJ&pg=PA70}}</ref> In [[calculus]], factorials occur in [[Faà di Bruno's formula]] for chaining higher derivatives.<ref name=craik/> In [[mathematical analysis]], factorials frequently appear in the denominators of [[power series]], most notably in the series for the [[exponential function]],<ref name=exponential-series/> <math display=block>e^x=1+\frac{x}{1}+\frac{x^2}{2}+\frac{x^3}{6}+\cdots=\sum_{i=0}^{\infty}\frac{x^i}{i!},</math>
and in the coefficients of other [[Taylor series]] (in particular those of the [[trigonometric functions|trigonometric]] and [[hyperbolic functions]]), where they cancel factors of <math>n!</math> coming from the {{nowrap|<math>n</math>th derivative}} {{nowrap|of <math>x^n</math>.<ref>{{cite book|title=Complexity and Criticality|series=Advanced physics texts|volume=1|first1=Kim|last1=Christensen|first2=Nicholas R.|last2=Moloney|publisher=Imperial College Press|year=2005|isbn=978-1-86094-504-5|contribution=Appendix A: Taylor expansion|page=341|contribution-url=https://books.google.com/books?id=bAIM1_EoQu0C&pg=PA341}}</ref>}} This usage of factorials in power series connects back to [[analytic combinatorics]] through the [[exponential generating function]], which for a [[combinatorial class]] with <math>n_i</math> elements of {{nowrap|size <math>i</math>}} is defined as the power series<ref>{{cite book | last = Wilf | first = Herbert S. | author-link = Herbert Wilf | edition = 3rd | isbn = 978-1-56881-279-3 | mr = 2172781 | page = 22 | publisher = A K Peters | location = Wellesley, Massachusetts | title = generatingfunctionology | url = https://books.google.com/books?id=XOPMBQAAQBAJ&pg=PA22 | year = 2006}}</ref> <math display=block>\sum_{i=0}^{\infty} \frac{x^i n_i}{i!}.</math>

In [[number theory]], the most salient property of factorials is the [[divisibility]] of <math>n!</math> by all positive integers up {{nowrap|to <math>n</math>,}} described more precisely for prime factors by [[Legendre's formula]]. It follows that arbitrarily large [[prime number]]s can be found as the prime factors of the numbers
<math>n!\pm 1</math>, leading to a proof of [[Euclid's theorem]] that the number of primes is infinite.<ref>{{cite book | last = Ore | first = Øystein | author-link = Øystein Ore | location = New York | mr = 0026059 | page = 66 | publisher = McGraw-Hill | title = Number Theory and Its History  | year = 1948 }} [https://books.google.com/books?id=Sl_6BPp7S0AC&pg=PA66 Reprinted], Courier Dover Publications, 1988, {{isbn|9780486656205}}.</ref> When <math>n!\pm 1</math> is itself prime it is called a [[factorial prime]];<ref name=caldwell-gallot>{{cite journal | last1 = Caldwell | first1 = Chris K. | last2 = Gallot | first2 = Yves | doi = 10.1090/S0025-5718-01-01315-1 | issue = 237 | journal = [[Mathematics of Computation]] | mr = 1863013 | pages = 441–448 | title = On the primality of <math>n!\pm1</math> and <math>2\times3\times5\times\dots\times p\pm1</math> | volume = 71 | year = 2002| doi-access = free }}</ref> relatedly, [[Brocard's problem]], also posed by [[Srinivasa Ramanujan]], concerns the existence of [[square number]]s of the form {{nowrap|<math>n!+1</math>.<ref>{{cite book | last = Guy | first = Richard K. | author-link = Richard K. Guy | contribution = D25: Equations involving factorial <math>n</math> | doi = 10.1007/978-0-387-26677-0 | edition = 3rd | isbn = 0-387-20860-7 | mr = 2076335 | pages = 301–302 | publisher = Springer-Verlag | location = New York | series = Problem Books in Mathematics | title = Unsolved Problems in Number Theory | year = 2004| volume = 1 }}</ref>}} In contrast, the numbers <math>n!+2,n!+3,\dots n!+n</math> must all be composite, proving the existence of arbitrarily large [[prime gap]]s.<ref>{{cite book|title=Closing the Gap: The Quest to Understand Prime Numbers|first=Vicky|last=Neale|author-link=Vicky Neale|publisher=Oxford University Press|year=2017|isbn=978-0-19-878828-7|pages=146–147|url=https://books.google.com/books?id=T7Q1DwAAQBAJ&pg=PA146}}</ref> An elementary [[proof of Bertrand's postulate]] on the existence of a prime in any interval of the {{nowrap|form <math>[n,2n]</math>,}} one of the first results of [[Paul Erdős]], was based on the divisibility properties of factorials.<ref>{{cite journal | last = Erdős | first = Pál | author-link = Paul Erdős | journal = Acta Litt. Sci. Szeged | language = de | pages = 194–198 | title = Beweis eines Satzes von Tschebyschef | trans-title = Proof of a theorem of Chebyshev | url = https://users.renyi.hu/~p_erdos/1932-01.pdf | volume = 5 | year = 1932 | zbl = 0004.10103}}</ref><ref>{{cite book | last = Chvátal | first = Vašek | author-link = Václav Chvátal | contribution = 1.5: Erdős's proof of Bertrand's postulate | contribution-url = https://books.google.com/books?id=_gVDEAAAQBAJ&pg=PA7 | doi = 10.1017/9781108912181 | isbn = 978-1-108-83183-3 | mr = 4282416 | pages = 7–10 | publisher = Cambridge University Press | location = Cambridge, England | title = The Discrete Mathematical Charms of Paul Erdős: A Simple Introduction | year = 2021| s2cid = 242637862 }}</ref> The [[factorial number system]] is a [[mixed radix]] notation for numbers in which the place values of each digit are factorials.<ref>{{cite journal | last = Fraenkel | first = Aviezri S. | author-link = Aviezri Fraenkel | doi = 10.1080/00029890.1985.11971550 | issue = 2 | journal = [[The American Mathematical Monthly]] | jstor = 2322638 | mr = 777556 | pages = 105–114 | title = Systems of numeration | volume = 92 | year = 1985}}</ref>

Factorials are used extensively in [[probability theory]], for instance in the [[Poisson distribution]]<ref>{{cite book | last = Pitman | first = Jim | contribution = 3.5: The Poisson distribution | doi = 10.1007/978-1-4612-4374-8 | pages = 222–236 | publisher = Springer | location = New York | title = Probability | year = 1993| isbn = 978-0-387-94594-1 }}</ref> and in the probabilities of [[random permutation]]s.{{sfn|Pitman|1993|p=153}} In [[computer science]], beyond appearing in the analysis of [[brute-force search]]es over permutations,<ref>{{cite book|title=Algorithm Design|first1=Jon|last1=Kleinberg|author1-link=Jon Kleinberg|first2=Éva|last2=Tardos|author2-link=Éva Tardos|publisher=Addison-Wesley|year=2006|page=55}}</ref> factorials arise in the [[lower bound]] of <math>\log_2 n!=n\log_2n-O(n)</math> on the number of comparisons needed to [[comparison sort]] a set of <math>n</math> items,<ref name=knuth-sorting/> and in the analysis of chained [[hash table]]s, where the distribution of keys per cell can be accurately approximated by a Poisson distribution.<ref>{{cite book|title=Algorithms|edition=4th|publisher=Addison-Wesley|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin|last2=Wayne|year=2011|isbn=978-0-13-276256-4|page=466|url=https://books.google.com/books?id=idUdqdDXqnAC&pg=PA466}}</ref> Moreover, factorials naturally appear in formulae from [[quantum mechanics|quantum]] and [[statistical physics]], where one often considers all the possible permutations of a set of particles. In [[statistical mechanics]], calculations of [[entropy]] such as [[Boltzmann's entropy formula]] or the [[Sackur–Tetrode equation]] must correct the count of [[Microstate (statistical mechanics)|microstates]] by dividing by the factorials of the numbers of each type of [[identical particles|indistinguishable particle]] to avoid the [[Gibbs paradox]]. Quantum physics provides the underlying reason for why these corrections are necessary.<ref>{{cite book|first=Mehran |last=Kardar |author-link=Mehran Kardar |title=Statistical Physics of Particles |title-link=Statistical Physics of Particles |year=2007 |publisher=[[Cambridge University Press]] |isbn=978-0-521-87342-0 |oclc=860391091 |pages=107–110, 181–184}}</ref>