This site is supported by donations to The OEIS Foundation.

Factorial

From OeisWiki
Jump to: navigation, search

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.

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

Approximations to (With as the nearest integer function.)
Factorial

A000142

Stirling's approximation

(nearest integer)
A005394


Gosper's approximation

(nearest integer)
A090583


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

Operator precedence

Formula Operator Precedence Demo.png

Parenthesization — FactorialExponentiationMultiplication and divisionAddition and subtraction


Notes

  1. (see Calin D. Morosan, Information Processing Letters, 100 (2006), 188-193).
  2. One would have preferred the gamma function to be defined as so as to get but for historical reasons we instead have which begets .

External links