Khanh at 18:24, 14 November 2021

2021-11-14T18:24:25Z

Khanh: Created page with "In mathematics, the '''factorial''' of a non-negative integer {{mvar|n}}, denoted by {{math|''n''!}}, is the product of all positive integers less than or equal to {{mvar|n}}:..."

2021-09-17T20:28:05Z

Created page with "In mathematics, the '''factorial''' of a non-negative integer {{mvar|n}}, denoted by {{math|''n''!}}, is the product of all positive integers less than or equal to {{mvar|n}}:..."

New page

In mathematics, the '''factorial''' of a non-negative integer {{mvar|n}}, denoted by {{math|''n''!}}, is the product of all positive integers less than or equal to {{mvar|n}}:
<math display=block>n! = n \cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot \cdots \cdot 3 \cdot 2 \cdot 1 \,. </math>
For example,
<math display=block>5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120 \,. </math>

The value of 0! is 1, according to the convention for an empty product.
The factorial operation is encountered in many areas of mathematics, notably in combinatorics, algebra, and mathematical analysis. Its most basic use counts the possible distinct sequences – the permutations – of {{mvar|n}} distinct objects: there are {{math|''n''!}}.

The factorial function can also be extended to non-integer arguments while retaining its most important properties by defining {{math|1=''x''! = Γ(''x'' + 1)}}, where {{math|Γ}} is the gamma function; this is undefined when {{mvar|x}} is a negative integer.

==Notation==
Factorial of {{mvar|n}} is denoted by {{math|''n''!}} or {{math|1=''n''}}. The notation {{math|''n''!}} was introduced by the French mathematician Christian Kramp in 1808.

==Definition==
The factorial function is defined by the product
<math display=block>n! = 1 \cdot 2 \cdot 3 \cdots (n-2) \cdot (n-1) \cdot n,</math>
for integer {{math|''n'' ≥ 1}}. This may be written in pi product notation as
<math display=block>n! = \prod_{i = 1}^n i.</math>

This leads to the recurrence relation
<math display=block> n! = n \cdot (n-1)! .</math>
For example,
<math display=block>\begin{align}
5! &= 5 \cdot 4! \\
6! &= 6 \cdot 5! \\
50! &= 50 \cdot 49!
\end{align}</math>
and so on.

===Factorial of zero===
The factorial of {{math|0}} is {{math|1}}, or in symbols, {{math|1=0! = 1}}.

There are several motivations for this definition:
* For {{math|1= ''n'' = 0}}, the definition of {{math|''n''!}} as a product involves the product of no numbers at all, and so is an example of the broader convention that the product of no factors is equal to the multiplicative identity.
* There is exactly one permutation of zero objects (with nothing to permute, the only rearrangement is to do nothing).
* It makes many identities in combinatorics valid for all applicable sizes. The number of ways to choose 0 elements from the empty set is given by the binomial coefficient: <math display=block>\binom{0}{0} = \frac{0!}{0!0!} = 1. </math> More generally, the number of ways to choose all {{mvar|n}} elements among a set of {{mvar|n}} is: <math display=block>\binom{n}{n} = \frac{n!}{n!0!} = 1. </math>
* It allows for the compact expression of many formulae, such as the exponential function, as a power series: <math display=block> e^x = \sum_{n = 0}^\infty \frac{x^n}{n!}.</math>
* It extends the recurrence relation to 0.
* It matches the gamma function <math>0! = \Gamma(0+1) = 1</math>.

==Applications==
Although the factorial function has its roots in combinatorics, formulas involving factorials occur in many areas of mathematics.
* There are {{math|''n''!}} different ways of arranging {{mvar|n}} distinct objects into a sequence, the permutations of those objects.
* Often factorials appear in the denominator of a formula to account for the fact that ordering is to be ignored. A classical example is counting {{mvar|k}}-combinations (subsets of {{mvar|k}} elements) from a set with {{mvar|n}} elements. One can obtain such a combination by choosing a {{mvar|k}}-permutation: successively selecting and removing one element of the set, {{mvar|k}} times, for a total of <math display=block>(n-0)(n-1)(n-2)\cdots\left(n-(k-1)\right) = \frac{n!}{(n-k)!} = n^{\underline k}</math> possibilities. This, however, produces the {{mvar|k}}-combinations in a particular order that one wishes to ignore; since each {{mvar|k}}-combination is obtained in {{math|''k''!}} different ways, the correct number of {{mvar|k}}-combinations is <math display=block>\frac{n(n-1)(n-2)\cdots(n-k+1)}{k(k-1)(k-2)\cdots 1} = \frac{n^{\underline k}}{k!}= \frac{n!}{(n-k)!k!} = \binom {n}{k}.</math> This number is known as the binomial coefficient, because it is also the coefficient of {{math|''x''''k''}} in {{math|(1 + ''x'')''n''}}. The term <math>n^{\underline k}</math> is often called a falling factorial (pronounced "''n'' to the falling ''k''").
* Factorials occur in algebra for various reasons, such as via the already mentioned coefficients of the binomial formula, or through averaging over permutations for symmetrization of certain operations.
* Factorials also turn up in calculus; for example, they occur in the denominators of the terms of Taylor's formula, where they are used as compensation terms due to the {{mvar|n}}th derivative of {{math|''x''''n''}} being equivalent to {{math|''n''!}}.
* Factorials are also used extensively in probability theory and number theory.
* Factorials can be useful to facilitate expression manipulation. For instance the number of {{mvar|k}}-permutations of {{mvar|n}} can be written as <math display=block>n^{\underline k}=\frac{n!}{(n-k)!}\,;</math> while this is inefficient as a means to compute that number, it may serve to prove a symmetry property of binomial coefficients: <math display=block>\binom nk=\frac{n^{\underline k}}{k!}=\frac{n!}{(n-k)!k!} = \frac{n^{\underline{n-k}}}{(n-k)!} = \binom n{n-k}\,.</math>
* The factorial function can be shown, using the power rule, to be <math display=block>n! = D^n\,x^n = \frac{d^n}{dx^n}\,x^n</math> where {{math|''D''''n'' ''x''''n''}} is Euler's notation for the {{mvar|n}}th derivative of {{math|''xn''}}.

==Rate of growth and approximations for large ''{{mvar|n}}''==
[[File:Log-factorial.svg|upright=1.35|thumb|right|Plot of the natural logarithm of the factorial]]
As {{mvar|n}} grows, the factorial {{math|''n''!}} increases faster than all polynomials and exponential functions (but slower than <math>n^n</math> and double exponential functions) in {{mvar|n}}.

Most approximations for ''n''! are based on approximating its natural logarithm
<math display=block>\ln n! = \sum_{x=1}^n \ln x \,.</math>

The graph of the function ''f''(''n'') = ln ''n''! is shown in the figure on the right. It looks approximately linear for all reasonable values of {{mvar|n}}, but this intuition is false. We get one of the simplest approximations for {{math|ln ''n''!}} by bounding the sum with an integral from above and below as follows:
<math display=block> \int_1^n \ln x \, dx \leq \sum_{x=1}^n \ln x \leq \int_0^n \ln (x+1) \, dx</math>
which gives us the estimate
<math display=block> n\ln\left(\frac{n}{e}\right)+1 \leq \ln n! \leq (n+1)\ln\left( \frac{n+1}{e} \right) + 1 \,.</math>

Hence {{math|ln ''n''! ∼ ''n'' ln ''n''}}. This result plays a key role in the analysis of the computational complexity of sorting algorithms. From the bounds on {{math|ln ''n''!}} deduced above we get that
<math display=block>\left(\frac ne\right)^n e \leq n! \leq \left(\frac{n+1}e\right)^{n+1} e \,.</math>

It is sometimes practical to use weaker but simpler estimates. Using the above formula it is easily shown that for all {{mvar|n}} we have (<math>\frac{n}{3}</math>)''n'' < ''n''!}}, and for all {{math|''n'' ≥ 6}} we have {{math|''n''! < (<math>\frac{n}{2}</math>)''n''.

[[File:Mplwp factorial gamma stirling.svg|thumb|right|upright=1.35|Comparison of Stirling's approximation with the factorial]]
For large {{mvar|n}} we get a better estimate for the number {{math|''n''!}} using Stirling's approximation:
<math display=block>n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\,.</math>

This in fact comes from an asymptotic series for the logarithm, and {{mvar|n}} factorial lies between this and the next approximation:
<math display=block>\sqrt{2\pi n}\left(\frac{n}{e}\right)^n<n!<\sqrt{2\pi n}\left(\frac{n}{e}\right)^ne^{1/(12n)} \,.</math>

Another approximation for {{math|ln ''n''!}} is given by Srinivasa Ramanujan (Ramanujan 1988)
<math display=block>\begin{align}
\ln n! &\approx n\ln n - n + \frac {\ln\Bigl(n\bigl(1+4n(1+2n)\bigr)\Bigr)}{6} + \frac {\ln\pi}{2} \\[6px]
\Longrightarrow \; n!&\approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1 +\frac 1{2n} +\frac 1{8n^2}\right)^{1/6} \,.
\end{align}</math>

Both this and Stirling's approximation give a relative error on the order of <math>\frac{1}{n^3}</math>, but Ramanujan's is about four times more accurate. However, if we use ''two'' correction terms in a Stirling-type approximation, as with Ramanujan's approximation, the relative error will be of order <math>\frac{1}{n^5}</math>:
<math display=block>n!\approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\exp\left({\frac 1{12n}-\frac 1{360n^3}}\right) \,.</math>

==References==
# Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1988), Concrete Mathematics, Reading, MA: Addison-Wesley, ISBN 0-201-14236-8
# Wilson, Robin; Watkins, John J.; Graham, Ronald (2013). Combinatorics: Ancient & Modern. Oxford University Press. p. 111. ISBN 978-0-19-965659-2.
# Biggs, Norman L. (May 1979). "The roots of combinatorics". Historia Mathematica. 6 (2): 109–136. doi:10.1016/0315-0860(79)90074-0. ISSN 0315-0860.
# Stedman, Fabian (1677), Campanalogia, London The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed.
# Aggarwal, M.L. (2021). "8. Permutations and Combinations". Understanding ISC Mathematics Class XI. I. Industrial Area, Trilokpur Road, Kala Amb-173030, Distt. Simour (H.P.): Arya Publications (Avichal Publishing Company). p. A-400. ISBN 978-81-7855-743-4.
# Higgins, Peter (2008), Number Story: From Counting to Cryptography, New York: Copernicus, ISBN 978-1-84800-000-1
# Cheng, Eugenia (2017-03-09). Beyond Infinity: An expedition to the outer limits of the mathematical universe. Profile Books. ISBN 9781782830818.
# Conway, John H.; Guy, Richard (1998-03-16). The Book of Numbers. Springer Science & Business Media. ISBN 9780387979939.
# Knuth, Donald E. (1997-07-04). The Art of Computer Programming: Volume 1: Fundamental Algorithms. Addison-Wesley Professional. ISBN 9780321635747.
# "18.01 Single Variable Calculus, Lecture 37: Taylor Series". MIT OpenCourseWare. Fall 2006. Archived from the original on 2018-04-26. Retrieved 2017-05-03.
# Kardar, Mehran (2007-06-25). "Chapter 2: Probability". Statistical Physics of Particles. Cambridge University Press. pp. 35–56. ISBN 9780521873420.
# "18.01 Single Variable Calculus, Lecture 4: Chain rule, higher derivatives". MIT OpenCourseWare. Fall 2006. Archived from the original on 2018-04-26. Retrieved 2017-05-03.
# Impens, Chris (2003), "Stirling's series made easy", American Mathematical Monthly, 110 (8): 730–735, doi:10.2307/3647856, hdl:1854/LU-284957, JSTOR 3647856, MR 2024001

@@ Line 82: / Line 82: @@
 <math display=block>n!\approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\exp\left({\frac 1{12n}-\frac 1{360n^3}}\right) \,.</math>
-==References==
+== Licensing ==
-# Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1988), Concrete Mathematics, Reading, MA: Addison-Wesley, ISBN 0-201-14236-8
+Content obtained and/or adapted from:
-# Wilson, Robin; Watkins, John J.; Graham, Ronald (2013). Combinatorics: Ancient & Modern. Oxford University Press. p. 111. ISBN 978-0-19-965659-2.
+* [https://en.wikipedia.org/wiki/Factorial Factorial, Wikipedia] under a CC BY-SA license

Factorials - Revision history

Khanh at 18:24, 14 November 2021

Khanh: Created page with "In mathematics, the '''factorial''' of a non-negative integer {{mvar|n}}, denoted by {{math|''n''!}}, is the product of all positive integers less than or equal to {{mvar|n}}:..."