Factorial

From Wikipedia for FEVERv2
Jump to navigation Jump to search

Factorial_table_general_0

Selected members of the factorial sequence (sequence in the OEIS); values specified in scientific notation are rounded to the displayed precisionFactorial_table_caption_0
nFactorial_header_cell_0_0_0 n!Factorial_header_cell_0_0_1
0Factorial_cell_0_1_0 1Factorial_cell_0_1_1
1Factorial_cell_0_2_0 1Factorial_cell_0_2_1
2Factorial_cell_0_3_0 2Factorial_cell_0_3_1
3Factorial_cell_0_4_0 6Factorial_cell_0_4_1
4Factorial_cell_0_5_0 24Factorial_cell_0_5_1
5Factorial_cell_0_6_0 120Factorial_cell_0_6_1
6Factorial_cell_0_7_0 720Factorial_cell_0_7_1
7Factorial_cell_0_8_0 5040Factorial_cell_0_8_1
8Factorial_cell_0_9_0 40320Factorial_cell_0_9_1
9Factorial_cell_0_10_0 362880Factorial_cell_0_10_1
10Factorial_cell_0_11_0 3628800Factorial_cell_0_11_1
11Factorial_cell_0_12_0 39916800Factorial_cell_0_12_1
12Factorial_cell_0_13_0 479001600Factorial_cell_0_13_1
13Factorial_cell_0_14_0 6227020800Factorial_cell_0_14_1
14Factorial_cell_0_15_0 87178291200Factorial_cell_0_15_1
15Factorial_cell_0_16_0 1307674368000Factorial_cell_0_16_1
16Factorial_cell_0_17_0 20922789888000Factorial_cell_0_17_1
17Factorial_cell_0_18_0 355687428096000Factorial_cell_0_18_1
18Factorial_cell_0_19_0 6402373705728000Factorial_cell_0_19_1
19Factorial_cell_0_20_0 121645100408832000Factorial_cell_0_20_1
20Factorial_cell_0_21_0 2432902008176640000Factorial_cell_0_21_1
25Factorial_cell_0_22_0 1.551121004×10Factorial_cell_0_22_1
50Factorial_cell_0_23_0 3.041409320×10Factorial_cell_0_23_1
70Factorial_cell_0_24_0 1.197857167×10Factorial_cell_0_24_1
100Factorial_cell_0_25_0 9.332621544×10Factorial_cell_0_25_1
450Factorial_cell_0_26_0 1.733368733×10Factorial_cell_0_26_1
1000Factorial_cell_0_27_0 4.023872601×10Factorial_cell_0_27_1
3249Factorial_cell_0_28_0 6.412337688×10Factorial_cell_0_28_1
10000Factorial_cell_0_29_0 2.846259681×10Factorial_cell_0_29_1
25206Factorial_cell_0_30_0 1.205703438×10Factorial_cell_0_30_1
100000Factorial_cell_0_31_0 2.824229408×10Factorial_cell_0_31_1
205023Factorial_cell_0_32_0 2.503898932×10Factorial_cell_0_32_1
1000000Factorial_cell_0_33_0 8.263931688×10Factorial_cell_0_33_1
10Factorial_cell_0_34_0 10Factorial_cell_0_34_1

In mathematics, the factorial of a positive integer n, denoted by n!, is the product of all positive integers less than or equal to n: Factorial_sentence_0

For example, Factorial_sentence_1

The value of 0! Factorial_sentence_2

is 1, according to the convention for an empty product. Factorial_sentence_3

The factorial operation is encountered in many areas of mathematics, notably in combinatorics, algebra, and mathematical analysis. Factorial_sentence_4

Its most basic use counts the possible distinct sequences – the permutations – of n distinct objects: there are n!. Factorial_sentence_5

The factorial function can also be extended to non-integer arguments while retaining its most important properties by defining x! Factorial_sentence_6

= Γ(x + 1), where Γ is the gamma function; this is undefined when x is a negative integer. Factorial_sentence_7

History Factorial_section_0

Factorials were used to count permutations at least as early as the 12th century, by Indian scholars. Factorial_sentence_8

In 1677, Fabian Stedman described factorials as applied to change ringing, a musical art involving the ringing of many tuned bells. Factorial_sentence_9

After describing a recursive approach, Stedman gives a statement of a factorial (using the language of the original): Factorial_sentence_10

The notation n! Factorial_sentence_11

was introduced by the French mathematician Christian Kramp in 1808. Factorial_sentence_12

Definition Factorial_section_1

The factorial function is defined by the product Factorial_sentence_13

for integer n ≥ 1. Factorial_sentence_14

This may be written in pi product notation as Factorial_sentence_15

This leads to the recurrence relation Factorial_sentence_16

For example, Factorial_sentence_17

and so on. Factorial_sentence_18

Factorial of zero Factorial_section_2

The factorial of 0 is 1, or in symbols, 0! Factorial_sentence_19

= 1. Factorial_sentence_20

There are several motivations for this definition: Factorial_sentence_21

Factorial_unordered_list_0

  • For n = 0, the definition of 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 (see Empty product).Factorial_item_0_0
  • There is exactly one permutation of zero objects (with nothing to permute, the only rearrangement is to do nothing).Factorial_item_0_1
  • 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 coefficientFactorial_item_0_2

Factorial_unordered_list_1

  • It allows for the compact expression of many formulae, such as the exponential function, as a power series:Factorial_item_1_3

Factorial_unordered_list_2

  • It extends the recurrence relation to 0.Factorial_item_2_4

Applications Factorial_section_3

Although the factorial function has its roots in combinatorics, formulas involving factorials occur in many areas of mathematics. Factorial_sentence_22

Factorial_unordered_list_3

  • There are n! different ways of arranging n distinct objects into a sequence, the permutations of those objects.Factorial_item_3_5
  • 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 k-combinations (subsets of k elements) from a set with n elements. One can obtain such a combination by choosing a k-permutation: successively selecting and removing one element of the set, k times, for a total ofFactorial_item_3_6

Factorial_unordered_list_4

  • 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.Factorial_item_4_7
  • 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 nth derivative of x being equivalent to n!.Factorial_item_4_8
  • Factorials are also used extensively in probability theory and number theory (see below).Factorial_item_4_9
  • Factorials can be useful to facilitate expression manipulation. For instance the number of k-permutations of n can be written asFactorial_item_4_10

Factorial_unordered_list_5

  • The factorial function can be shown, using the power rule, to beFactorial_item_5_11

Rate of growth and approximations for large n Factorial_section_4

Most approximations for n! Factorial_sentence_23

are based on approximating its natural logarithm Factorial_sentence_24

The graph of the function f(n) = ln n! Factorial_sentence_25

is shown in the figure on the right. Factorial_sentence_26

It looks approximately linear for all reasonable values of n, but this intuition is false. Factorial_sentence_27

We get one of the simplest approximations for ln n! Factorial_sentence_28

by bounding the sum with an integral from above and below as follows: Factorial_sentence_29

which gives us the estimate Factorial_sentence_30

Hence ln n! Factorial_sentence_31

∼ n ln n (see Big O notation). Factorial_sentence_32

This result plays a key role in the analysis of the computational complexity of sorting algorithms (see comparison sort). Factorial_sentence_33

From the bounds on ln n! Factorial_sentence_34

deduced above we get that Factorial_sentence_35

It is sometimes practical to use weaker but simpler estimates. Factorial_sentence_36

Using the above formula it is easily shown that for all n we have (n/3) < n!, and for all n ≥ 6 we have n! Factorial_sentence_37

< (n/2). Factorial_sentence_38

For large n we get a better estimate for the number n! Factorial_sentence_39

using Stirling's approximation: Factorial_sentence_40

This in fact comes from an asymptotic series for the logarithm, and n factorial lies between this and the next approximation: Factorial_sentence_41

Another approximation for ln n! Factorial_sentence_42

is given by Srinivasa Ramanujan () Factorial_sentence_43

Both this and Stirling's approximation give a relative error on the order of 1/n, but Ramanujan's is about four times more accurate. Factorial_sentence_44

However, if we use two correction terms in a Stirling-type approximation, as with Ramanujan's approximation, the relative error will be of order 1/n: Factorial_sentence_45

Computation Factorial_section_5

If efficiency is not a concern, computing factorials is trivial from an algorithmic point of view: successively multiplying a variable initialized to 1 by the integers up to n (if any) will compute n!, provided the result fits in the variable. Factorial_sentence_46

In functional languages, the recursive definition is often implemented directly to illustrate recursive functions. Factorial_sentence_47

The main practical difficulty in computing factorials is the size of the result. Factorial_sentence_48

To assure that the exact result will fit for all legal values of even the smallest commonly used integral type (8-bit signed integers) would require more than 700 bits, so no reasonable specification of a factorial function using fixed-size types can avoid questions of overflow. Factorial_sentence_49

The values 12! Factorial_sentence_50

and 20! Factorial_sentence_51

are the largest factorials that can be stored in, respectively, the 32-bit and 64-bit integers commonly used in personal computers, however many languages support variable length integer types capable of calculating very large values. Factorial_sentence_52

Floating-point representation of an approximated result allows going a bit further, but this also remains quite limited by possible overflow. Factorial_sentence_53

Most calculators use scientific notation with 2-digit decimal exponents, and the largest factorial that fits is then 69!, because 69! Factorial_sentence_54

< 10 < 70!. Factorial_sentence_55

Other implementations (such as computer software such as spreadsheet programs) can often handle larger values. Factorial_sentence_56

Most software applications will compute small factorials by direct multiplication or table lookup. Factorial_sentence_57

Larger factorial values can be approximated using Stirling's formula. Factorial_sentence_58

Wolfram Alpha can calculate exact results for the ceiling function and floor function applied to the binary, natural and common logarithm of n! Factorial_sentence_59

for values of n up to 249999, and up to 20000000! Factorial_sentence_60

for the integers. Factorial_sentence_61

If the exact values of large factorials are needed, they can be computed using arbitrary-precision arithmetic. Factorial_sentence_62

Instead of doing the sequential multiplications ((1 × 2) × 3) × 4..., a program can partition the sequence into two parts, whose products are roughly the same size, and multiply them using a divide-and-conquer method. Factorial_sentence_63

This is often more efficient. Factorial_sentence_64

The asymptotically best efficiency is obtained by computing n! Factorial_sentence_65

from its prime factorization. Factorial_sentence_66

As documented by Peter Borwein, prime factorization allows n! Factorial_sentence_67

to be computed in time O(n(log n log log n)), provided that a fast multiplication algorithm is used (for example, the Schönhage–Strassen algorithm). Factorial_sentence_68

Peter Luschny presents source code and benchmarks for several efficient factorial algorithms, with or without the use of a prime sieve. Factorial_sentence_69

Number theory Factorial_section_6

Factorials have many applications in number theory. Factorial_sentence_70

In particular, n! Factorial_sentence_71

is necessarily divisible by all prime numbers up to and including n. As a consequence, n > 5 is a composite number if and only if Factorial_sentence_72

A stronger result is Wilson's theorem, which states that Factorial_sentence_73

if and only if p is prime. Factorial_sentence_74

Legendre's formula gives the multiplicity of the prime p occurring in the prime factorization of n! Factorial_sentence_75

as Factorial_sentence_76

or, equivalently, Factorial_sentence_77

where sp(n) denotes the sum of the standard base-p digits of n. Factorial_sentence_78

Adding 1 to a factorial n! Factorial_sentence_79

yields a number that is only divisible by primes that are larger than n. This fact can be used to prove Euclid's theorem that the number of primes is infinite. Factorial_sentence_80

Primes of the form n! Factorial_sentence_81

± 1 are called factorial primes. Factorial_sentence_82

Series of reciprocals Factorial_section_7

The reciprocals of factorials produce a convergent series whose sum is the exponential base e: Factorial_sentence_83

Although the sum of this series is an irrational number, it is possible to multiply the factorials by positive integers to produce a convergent series with a rational sum: Factorial_sentence_84

Factorial of non-integer values Factorial_section_8

The gamma and pi functions Factorial_section_9

Main article: Gamma function Factorial_sentence_85

Besides nonnegative integers, the factorial can also be defined for non-integer values, but this requires more advanced tools from mathematical analysis. Factorial_sentence_86

One function that fills in the values of the factorial (but with a shift of 1 in the argument), that is often used, is called the gamma function, denoted Γ(z). Factorial_sentence_87

It is defined for all complex numbers z except for the non-positive integers, and given when the real part of z is positive by Factorial_sentence_88

Its relation to the factorial is that n! Factorial_sentence_89

= Γ(n + 1) for every nonnegative integer n. Factorial_sentence_90

Euler's original formula for the gamma function was Factorial_sentence_91

Carl Friedrich Gauss used the notation Π(z) to denote the same function, but with argument shifted by 1, so that it agrees with the factorial for nonnegative integers. Factorial_sentence_92

This pi function is defined by Factorial_sentence_93

The pi function and gamma function are related by the formula Π(z) = Γ(z + 1). Factorial_sentence_94

Likewise, Π(n) = n! Factorial_sentence_95

for any nonnegative integer n. Factorial_sentence_96

In addition to this, the pi function satisfies the same recurrence as factorials do, but at every complex value z where it is defined Factorial_sentence_97

This is no longer a recurrence relation but a functional equation. Factorial_sentence_98

In terms of the gamma function, it is Factorial_sentence_99

The values of these functions at half-integer values is therefore determined by a single one of them: Factorial_sentence_100

from which it follows that for n ∈ N, Factorial_sentence_101

For example, Factorial_sentence_102

It also follows that for n ∈ N, Factorial_sentence_103

For example, Factorial_sentence_104

The pi function is certainly not the only way to extend factorials to a function defined at almost all complex values, and not even the only one that is analytic wherever it is defined. Factorial_sentence_105

Nonetheless it is usually considered the most natural way to extend the values of the factorials to a complex function. Factorial_sentence_106

For instance, the Bohr–Mollerup theorem states that the gamma function is the only function that takes the value 1 at 1, satisfies the functional equation Γ(n + 1) = nΓ(n), is meromorphic on the complex numbers, and is log-convex on the positive real axis. Factorial_sentence_107

A similar statement holds for the pi function as well, using the Π(n) = nΠ(n − 1) functional equation. Factorial_sentence_108

However, there exist complex functions that are probably simpler in the sense of analytic function theory and which interpolate the factorial values. Factorial_sentence_109

For example, Hadamard's 'gamma' function () which, unlike the gamma function, is an entire function. Factorial_sentence_110

Euler also developed a convergent product approximation for the non-integer factorials, which can be seen to be equivalent to the formula for the gamma function above: Factorial_sentence_111

However, this formula does not provide a practical means of computing the pi function or the gamma function, as its rate of convergence is slow. Factorial_sentence_112

Applications of the gamma function Factorial_section_10

The volume of an n-dimensional hypersphere of radius R is Factorial_sentence_113

Factorial in the complex plane Factorial_section_11

Representation through the gamma function allows evaluation of factorial of complex argument. Factorial_sentence_114

Equilines of amplitude and phase of factorial are shown in figure. Factorial_sentence_115

Let Factorial_sentence_116

Several levels of constant modulus (amplitude) ρ and constant phase φ are shown. Factorial_sentence_117

The grid covers the range −3 ≤ x ≤ 3, −2 ≤ y ≤ 2, with unit steps. Factorial_sentence_118

The scratched line shows the level φ = ±π. Factorial_sentence_119

Thin lines show intermediate levels of constant modulus and constant phase. Factorial_sentence_120

At the poles at every negative integer, phase and amplitude are not defined. Factorial_sentence_121

Equilines are dense in vicinity of singularities along negative integer values of the argument. Factorial_sentence_122

For |z| < 1, the Taylor expansions can be used: Factorial_sentence_123

The first coefficients of this expansion are Factorial_sentence_124

Factorial_table_general_1

nFactorial_header_cell_1_0_0 gnFactorial_header_cell_1_0_1 ApproximationFactorial_header_cell_1_0_2
0Factorial_cell_1_1_0 1Factorial_cell_1_1_1 1Factorial_cell_1_1_2
1Factorial_cell_1_2_0 −γFactorial_cell_1_2_1 −0.5772156649Factorial_cell_1_2_2
2Factorial_cell_1_3_0 π/12 + γ/2Factorial_cell_1_3_1 0.9890559955Factorial_cell_1_3_2
3Factorial_cell_1_4_0 −ζ(3)/3 − π/12 − γ/6Factorial_cell_1_4_1 −0.9074790760Factorial_cell_1_4_2

where γ is the Euler–Mascheroni constant and ζ is the Riemann zeta function. Factorial_sentence_125

Computer algebra systems such as SageMath can generate many terms of this expansion. Factorial_sentence_126

Approximations of the factorial Factorial_section_12

For the large values of the argument, the factorial can be approximated through the integral of the digamma function, using the continued fraction representation. Factorial_sentence_127

This approach is due to T. Factorial_sentence_128 J. Stieltjes (1894). Factorial_sentence_129

Writing z! Factorial_sentence_130

= e where P(z) is Factorial_sentence_131

Stieltjes gave a continued fraction for p(z): Factorial_sentence_132

The first few coefficients an are Factorial_sentence_133

Factorial_description_list_6

  • n an 0 1/12 1 1/30 2 53/210 3 195/371 4 22999/22737 5 29944523/19733142 6 109535241009/48264275462Factorial_item_6_12

There is a misconception that ln z! Factorial_sentence_134

= P(z) or ln Γ(z + 1) = P(z) for any complex z ≠ 0. Factorial_sentence_135

Indeed, the relation through the logarithm is valid only for a specific range of values of z in the vicinity of the real axis, where −π < Im(Γ(z + 1)) < π. Factorial_sentence_136

The larger the real part of the argument, the smaller the imaginary part should be. Factorial_sentence_137

However, the inverse relation, z! Factorial_sentence_138

= e, is valid for the whole complex plane apart from z = 0. Factorial_sentence_139

The convergence is poor in the vicinity of the negative part of the real axis; it is difficult to have good convergence of any approximation in the vicinity of the singularities. Factorial_sentence_140

When |Im z| > 2 or Re z > 2, the six coefficients above are sufficient for the evaluation of the factorial with complex double precision. Factorial_sentence_141

For higher precision more coefficients can be computed by a rational QD scheme (Rutishauser's QD algorithm). Factorial_sentence_142

Non-extendability to negative integers Factorial_section_13

The relation n! Factorial_sentence_143

= n × (n − 1)! Factorial_sentence_144

allows one to compute the factorial for an integer given the factorial for a smaller integer. Factorial_sentence_145

The relation can be inverted so that one can compute the factorial for an integer given the factorial for a larger integer: Factorial_sentence_146

However, this recursion does not permit us to compute the factorial of a negative integer; use of the formula to compute (−1)! Factorial_sentence_147

would require a division of a nonzero value by zero, and thus blocks us from computing a factorial value for every negative integer. Factorial_sentence_148

Similarly, the gamma function is not defined for zero or negative integers, though it is defined for all other complex numbers. Factorial_sentence_149

Factorial-like products and functions Factorial_section_14

There are several other integer sequences similar to the factorial that are used in mathematics: Factorial_sentence_150

Double factorial Factorial_section_15

Main article: Double factorial Factorial_sentence_151

The product of all the odd integers up to some odd positive integer n is called the double factorial of n, and denoted by n!!. Factorial_sentence_152

That is, Factorial_sentence_153

For example, 9!! Factorial_sentence_154

= 1 × 3 × 5 × 7 × 9 = 945. Factorial_sentence_155

The sequence of double factorials for n = 1, 3, 5, 7,... starts as Factorial_sentence_156

Factorial_description_list_7

  • 1, 3, 15, 105, 945, 10395, 135135,... (sequence in the OEIS)Factorial_item_7_13

Double factorial notation may be used to simplify the expression of certain trigonometric integrals, to provide an expression for the values of the gamma function at half-integer arguments and the volume of hyperspheres, and to solve many counting problems in combinatorics including counting binary trees with labeled leaves and perfect matchings in complete graphs. Factorial_sentence_157

Multifactorials Factorial_section_16

A common related notation is to use multiple exclamation points to denote a multifactorial, the product of integers in steps of two (n!! Factorial_sentence_158

), three (n!!! Factorial_sentence_159

), or more (see generalizations of the double factorial). Factorial_sentence_160

The double factorial is the most commonly used variant, but one can similarly define the triple factorial (n!!!) Factorial_sentence_161

and so on. Factorial_sentence_162

One can define the k-tuple factorial, denoted by n!, recursively for positive integers as Factorial_sentence_163

In addition, similarly to 0! Factorial_sentence_164

= 1!/1 = 1, one can define: Factorial_sentence_165

For sufficiently large n ≥ 1, the ordinary single factorial function is expanded through the multifactorial functions as follows: Factorial_sentence_166

In the same way that n! Factorial_sentence_167

is not defined for negative integers, and n!! Factorial_sentence_168

is not defined for negative even integers, n! Factorial_sentence_169

is not defined for negative integers divisible by k. Factorial_sentence_170

Primorial Factorial_section_17

Main article: Primorial Factorial_sentence_171

The primorial of a natural number n (sequence in the OEIS), denoted n#, is similar to the factorial, but with the product taken only over the prime numbers less than or equal to n. That is, Factorial_sentence_172

where p ranges over the prime numbers less than or equal to n. For example, the primorial of 11 is Factorial_sentence_173

Superfactorial Factorial_section_18

See also: Large numbers Factorial_sentence_174

"N$" redirects here. Factorial_sentence_175

For the currency, see Namibian dollar. Factorial_sentence_176

Neil Sloane and Simon Plouffe defined a superfactorial in The Encyclopedia of Integer Sequences (Academic Press, 1995) to be the product of the first n factorials. Factorial_sentence_177

So the superfactorial of 4 is Factorial_sentence_178

In general Factorial_sentence_179

Equivalently, the superfactorial is given by the formula Factorial_sentence_180

which is the determinant of a Vandermonde matrix. Factorial_sentence_181

Factorial_description_list_8

  • 1, 1, 2, 12, 288, 34560, 24883200, 125411328000,... (sequence in the OEIS)Factorial_item_8_14

By this definition, we can define the k-superfactorial of n (denoted sfk(n)) as: Factorial_sentence_182

The 2-superfactorials of n are Factorial_sentence_183

Factorial_description_list_9

  • 1, 1, 2, 24, 6912, 238878720, 5944066965504000, 745453331864786829312000000,... (sequence in the OEIS)Factorial_item_9_15

The 0-superfactorial of n is n. Factorial_sentence_184

Pickover’s superfactorial Factorial_section_19

In his 1995 book Keys to Infinity, Clifford Pickover defined a different function n$ that he called the superfactorial. Factorial_sentence_185

It is defined by Factorial_sentence_186

This sequence of superfactorials starts Factorial_sentence_187

(Here, as is usual for compound exponentiation, the grouping is understood to be from right to left: a = a.) Factorial_sentence_188

This operation may also be expressed as the tetration Factorial_sentence_189

or using Knuth's up-arrow notation as Factorial_sentence_190

Hyperfactorial Factorial_section_20

Occasionally the hyperfactorial of n is considered. Factorial_sentence_191

It is written as H(n) and defined by Factorial_sentence_192

For n = 1, 2, 3, 4,... the values of H(n) are 1, 4, 108, 27648,... (sequence in the OEIS). Factorial_sentence_193

The asymptotic growth rate is Factorial_sentence_194

where A = 1.2824... is the Glaisher–Kinkelin constant. Factorial_sentence_195

H(14) ≈ 1.8474×10 is already almost equal to a googol, and H(15) ≈ 8.0896×10 is almost of the same magnitude as the Shannon number, the theoretical number of possible chess games. Factorial_sentence_196

Compared to the Pickover definition of the superfactorial, the hyperfactorial grows relatively slowly. Factorial_sentence_197

The hyperfactorial function can be generalized to complex numbers in a similar way as the factorial function. Factorial_sentence_198

The resulting function is called the K-function. Factorial_sentence_199

See also Factorial_section_21

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Factorial.