This site is supported by donations to The OEIS Foundation.
Factorial
The factorial of a nonnegative integer is defined as the product of all positive integers up to , and is notated as . For example, 7! = 1 × 2 × 3 × 4 × 5 × 6 × 7 = 5040. The factorial of 0 is defined as the empty product, 1. Factorials comes after parenthesized expressions but before exponentiation in the order of operator precedence.
A000142 The factorial numbers .
- {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, ...}
is the smallest number with that prime signature. E.g., 720 = 2^{ 4} × 3^{ 2} × 5.
Conjecturally, 1, 6, and 120 are the only numbers which are both triangular and factorial.
Contents
- 1 Applications of factorials
- 2 Formulae
- 3 Recurrences
- 4 Generating function
- 5 Exponential generating function
- 6 Asymptotic behavior
- 7 Approximations to
- 8 Sum of reciprocals of
- 9 Prime factors of
- 10 Base 10 representation of
- 11 Pochhammer symbol
- 12 Falling factorial
- 13 Rising factorial
- 14 Sequences
- 15 See also
- 16 Notes
- 17 External links
Applications of factorials
Factorials have applications in many branches of mathematics.
In regards to matrices:
- For , is the number of n X n (0,1) matrices with each row and column containing exactly one entry equal to 1.
- a(n) is the permanent of the n X n matrix M with M(i, j) = 1.
- a(n) is also the determinant of an square matrix, An, whose coefficients are the reciprocals of beta function: a{i, j} = 1/beta(i, j), det(An) = n!
In regards to graphs:
- n! is also the number of optimal broadcast schemes in the complete graph , equivalent to the number of binomial trees embedded in .^{[1]}
- Let denote the n-star graph. The structure consists of structures. This sequence gives the number of edges between the vertices of any two specified structures in , with ).
- Chromatic invariant of the sun graph .
In regards to chains:
- The number of chains of maximal length in the power set of {1, 2, ..., n} ordered by the subset relation.
- a(n) is also the number of order-decreasing full transformations (of an n-chain).
- a(n - 1) is also the number of nilpotent order-decreasing full transformations (of an n-chain).
In regards to permutations:
- The number of circular permutations of n letters for n >= 0 is 1, 1, 1, 2, 6, 24, 120, 720, 5040, 40320, ...
- Consider the n! permutations of the integer sequence [n] = 1, 2, ..., n. The i-th permutation consists of ncycle(i) permutation cycles. Then, if the sum Sum_{i = 1}^{n!} 2^ncycle(i) runs from 1 to n!, we have . E.g., for n = 3 we have ncycle(1) = 3, ncycle(2) = 2, ncycle(3) = 1, ncycle(4) = 2, ncycle(5) = 1, ncycle(6) = 2 and 2^3 + 2^2 + 2^1 + 2^2 + 2^1 + 2^2 = 8 + 4 + 2 + 4 + 2 + 4 = 24 = (n+1)!.
- Number of permutations of elements 1, 2, ..., n + 1 with a fixed element belonging to a cycle of length r does not depend on r and equals a(n).
- a(n) is the number of fixed points in all permutations of 1, ..., n: in all n! permutations, 1 is first exactly (n - 1)! times, 2 is second exactly (n - 1)! times, etc., giving (n - 1)!n = n!.
In regards to partitions:
- a(n) is the number of partition tableaux of size n. See Steingrimsson/Williams link for the definition.
- a(n) is the number of set partitions of {1, 2, ..., 2n - 1, 2n} into blocks of size 2 (perfect matchings) in which each block consists of one even and one odd integer. For example, a(3) = 6 counts 12-34-56, 12-36-45, 14-23-56, 14-25-36, 16-23-45, 16-25-34.
Number of distinct subsets of T(n-1) elements with 1 element A, 2 elements B,..., n - 1 elements X (e.g., at n = 5, we consider the distinct subsets of ABBCCCDDDD and there are 5! = 120).
Given n objects of distinct sizes (e.g., areas, volumes) such that each object is sufficiently large to simultaneously contain all previous objects, then n! is the total number of essentially different arrangements using all n objects. Arbitrary levels of nesting of objects are permitted within arrangements. (This application of the sequence was inspired by considering leftover moving boxes.) If the restriction exists that each object is able or permitted to contain at most one smaller (but possibly nested) object at a time, the resulting sequence begins 1,2,5,15,52 (Bell Numbers?). Sets of nested wooden boxes or traditional nested Russian dolls come to mind here.2004
n! is the n-th finite difference of consecutive n-th powers. E.g. for n = 3, [0, 1, 8, 27, 64, ...] -> [1, 7, 19, 37, ...] -> [6, 12, 18, ...] -> [6, 6, ...]
Write numbers 1 to n on a circle. Then a(n) = sum of the products of all n - 2 adjacent numbers. E.g., a(5) = 1*2*3 + 2*3*4 + 3*4*5 + 4*5*1 +5*1*2 = 120.
Consider the multiset M = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...] = [1, 2, 2, ..., n x 'n'] and form the set U (where U is a set in the strict sense) of all subsets N (where N may be a multiset again) of M. Then the number of elements |U| of U is equal to (n+1)!. E.g. for M = [1, 2, 2] we get U = [[], [2], [2, 2], [1], [1, 2], [1, 2, 2]] and |U| = 3! = 6.
Increasing colored 1-2 trees with choice of two colors for the rightmost branch of nonleaves.
Number of necklaces with n labeled beads of 1 color.
Formulae
where and are respectively the rising factorial and the falling factorial.
where is the ^{ th} triangular number, is the double factorial and where for we get the empty product 1.
The following definite integral (Euler's integral form) for the factorial
leads to the generalization for
which is called the gamma function.
For a nonnegative integer, we thus have
a result of the somewhat unfortunate notation due to Legendre.^{[2]}
Recurrences
Note that the subfactorial has a similar recurrence
So, for
Generating function
Exponential generating function
The exponential generating function of is
Asymptotic behavior
Approximations to
Factorial |
Stirling's approximation (nearest integer) |
Gosper's approximation (nearest integer) | |
---|---|---|---|
0 | 1 | 0 –1 |
1 0 |
1 | 1 | 1 0 |
1 0 |
2 | 2 | 2 0 |
2 0 |
3 | 6 | 6 0 |
6 0 |
4 | 24 | 24 0 |
24 0 |
5 | 120 | 118 –2 |
120 0 |
6 | 720 | 710 –10 |
720 0 |
7 | 5040 | 4980 –60 |
5039 –1 |
8 | 40320 | 39902 –418 |
40316 –4 |
9 | 362880 | 359537 –3343 |
362851 –29 |
10 | 3628800 | 3598696 –30104 |
3628561 –239 |
11 | 39916800 | 39615625 –301175 |
39914615 –2185 |
12 | 479001600 | 475687486 –3314114 |
478979481 –22119 |
13 | 6227020800 | 6187239475 –39781325 |
6226774954 –245846 |
14 | 87178291200 | 86661001741 –517289459 |
87175314872 –2976328 |
15 | 1307674368000 | 1300430722199 –7243645801 |
1307635379670 –38988330 |
16 | 20922789888000 | 20814114415223 ? |
20922240412500 ? |
17 | 355687428096000 | 353948328666101 ? |
355679137660826 ? |
18 | 6402373705728000 | 6372804626194309 ? |
6402240370021199 ? |
19 | 121645100408832000 | 121112786592293963 ? |
121642823201649058 ? |
20 | 2432902008176640000 | 2422786846761133394 ? |
2432860847996122437 ? |
21 | 51090942171709440000 | ? ? |
51090157192742729183 ? |
22 | 1124000727777607680000 | ? ? |
1123984974735953018069 ? |
23 | 25852016738884976640000 | ? ? |
25851684898376695192336 ? |
24 | 620448401733239439360000 | ? ? |
620441080509682809701382 ? |
25 | 15511210043330985984000000 | ? ? |
15511041215936944579902093 ? |
26 | 403291461126605635584000000 | ? ? |
403287399526697316252516250 ? |
27 | 10888869450418352160768000000 | ? ? |
10888767684658777169852805388 ? |
28 | 304888344611713860501504000000 | ? ? |
304885693246011383041733210739 ? |
29 | 8841761993739701954543616000000 | ? ? |
8841690269587826737517642605696 ? |
30 | 265252859812191058636308480000000 | ? ? |
265250847945328962838481886897160 ? |
Stirling's approximation to
Stirling's approximation to is
A005395 Leading term of Stirling's approximation to n!, sqrt(2*Pi)*n^(n+(1/2))/e^n, rounded up.
- {0, 1, 2, 6, 24, 119, 711, 4981, 39903, 359537, 3598696, 39615626, 475687488, 6187239487, 86661001990, 1300430725000, 20814114480000, 353948329800000, 6372804643000000, 121112787000000000, ...}
A005394 Leading term of Stirling's approximation to n!, sqrt(2*Pi)*n^(n+(1/2))/e^n, n ≥ 0, rounded to nearest integer.
- {0, 1, 2, 6, 24, 118, 710, 4980, 39902, 359537, 3598696, 39615625, 475687486, 6187239475, 86661001741, 1300430722199, 20814114415223, 353948328666101, 6372804626194309, 121112786592293963, 2422786846761133394, ...}
A005393 Leading term of Stirling's approximation to n!, sqrt(2*Pi)*n^(n+(1/2))/e^n, rounded down.
- {0, 0, 1, 5, 23, 118, 710, 4980, 39902, 359536, 3598695, 39615625, 475687487, 6187239487, 86661001990, 1300430725000, 20814114480000, 353948329800000, 6372804643000000, 121112787000000000, ...}
Gosper's approximation to
R. W. Gosper's approximation to is
A090583 Gosper's approximation to n!, sqrt((2*n+1/3)*pi)*n^n/e^n, n ≥ 0, rounded to nearest integer.
- {1, 1, 2, 6, 24, 120, 720, 5039, 40316, 362851, 3628561, 39914615, 478979481, 6226774954, 87175314872, 1307635379670, 20922240412500, 355679137660826, 6402240370021199, 121642823201649058, 2432860847996122437, ...}
There are other approximations, see the work of Luschny Other Approx
Sum of reciprocals of
where e is the base of the natural logarithm.
These are obtained from the Maclaurin expansion of evaluated at and
Prime factors of
The number of prime factors (with multiplicity) of is given by the summatory Omega function
The number of distinct prime factors of is given by the prime counting function
where is the radical of , i.e. the squarefree kernel .
The sum of prime factors (with multiplicity) (integer log) of is
The sum of distinct prime factors of is the sum of prime factors of the primorial of
where is the prime counting function and is the -th prime.
The product of distinct prime factors (radical or squarefree kernel) of is the primorial of
where is the prime counting function and is the -th prime.
Base 10 representation of
Number of trailing zeros of
The number of trailing zeros (in base 10) in (highest power of 5 dividing and highest power of 10 dividing ) is given by
where the exponent of prime in the prime factorization of is given by Legendre's formula
Pochhammer symbol
Depending on the context the Pochhammer symbol , introduced by Leo August Pochhammer, may represent either the rising factorial or the falling factorial as defined below.
Falling factorial
The falling factorial (represented with ) of the real number , being a nonnegative integer is defined as
where for we get the empty product, giving 1.
Rising factorial
The rising factorial (represented with ) of the real number , being a nonnegative integer is defined as
where for we get the empty product, giving 1.
Sequences
The number of trailing zeros (in base 10) in (highest power of 5 dividing and highest power of 10 dividing ) (see A027868) are
- {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, ...}
Omitting trailing zeros (in base 10) from factorial numbers, i.e. . (see A004154) gives
- {1, 1, 2, 6, 24, 12, 72, 504, 4032, 36288, 36288, 399168, 4790016, 62270208, 871782912, 1307674368, 20922789888, 355687428096, 6402373705728, 121645100408832, 243290200817664, ...}
See also
- Gamma function and generalizations of the factorial
- Double factorial, triple factorial, quadruple factorial, quintuple factorial, sextuple factorial, ..., multifactorial
- Left factorial
- Subfactorial
- Superfactorial
- Swinging factorial
- Primorial, compositorial
- Wilson's theorem
Operator precedence |
---|
Parenthesization — Factorial — Exponentiation — Multiplication and division — Addition and subtraction |
Notes
External links
- Peter Luschny, "Fast-Factorial-Functions," 2000-2011.
- Peter Luschny, "Approximation Formulas for the Factorial Function." Web. Accessed June 3, 2011. Available http://www.luschny.de/math/factorial/approx/SimpleCases.html.