(Redirected from Number of permutations)
There are no approved revisions of this page, so it may
not have been
reviewed.
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 come 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, ...}
Factorial numbers are the smallest integers with a given prime signature. E.g., 720 = 2 4 × 3 2 × 5 1 is the smallest integer with prime signature {4, 2, 1}.
Conjecturally,
t1 = 1 = 1!, t3 = 6 = 3!, t15 = 120 = 5!, 
are the only numbers which are both
triangular and factorial.
Applications of factorials
Factorials have applications in many branches of mathematics. ^{(Review: § Applications of factorials)} ^{[1]}
In regards to matrices:
 For is the number of (0, 1)matrices with each row and column containing exactly one entry equal to 1.
 is the permanent of the matrix with .
 is also the determinant of an square matrix whose coefficients are the reciprocals of beta function:
a {i, j} = 1 / β (i, j), det (An ) = n! 
In regards to graphs:
 is also the number of optimal broadcast schemes in the complete graph , equivalent to the number of binomial trees embedded in .^{[2]}
 Let denote the 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 ordered by the subset relation.
 is also the number of orderdecreasing full transformations (of an chain).
 is also the number of nilpotent orderdecreasing full transformations (of an chain).
In regards to permutations:
 The number of circular permutations of distinct letters is .
 Consider the permutations of the integer sequence . The th permutation consists of ncycle(i) permutation cycles. Then, we have . E.g., for we have ncycle(1) = 3, ncycle(2) = 2, ncycle(3) = 1, ncycle(4) = 2, ncycle(5) = 1, ncycle(6) = 2 and .
 Number of permutations of elements with a fixed element belonging to a cycle of length does not depend on and equals .
 is the number of fixed points in all permutations of : in all permutations, 1 is first exactly times, 2 is second exactly times, etc., giving .
In regards to partitions:
 is the number of partition tableaux of size . (See Steingrimsson/Williams link for the definition.)
 is the number of set partitions of into blocks of size 2 (perfect matchings) in which each block consists of one even and one odd integer. For example, 3! = 6 counts
 { { {12}, {34}, {56} }, { {12}, {36}, {45} }, { {14}, {23}, {56} }, { {14}, {25}, {36} }, { {16}, {23}, {45} }, { {16}, {25}, {34} } }.
 Number of distinct submultisets (subbags) of a multiset (subbag) elements with 1 element A, 2 elements B, ..., elements (e.g., at , we consider the distinct submultisets (subbags) of [A, B, B, C, C, C, D, D, D, D] = [A: 1, B: 2, C: 3, D: 4] and there are 5! = 120).
 Given objects of distinct sizes (e.g., areas, volumes) such that each object is sufficiently large to simultaneously contain all previous objects, then is the total number of essentially different arrangements using all 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.
 is the th finite difference of consecutive th powers. E.g. for , [0, 1, 8, 27, 64, ...] ⤇ [1, 7, 19, 37, ...] ⤇ [6, 12, 18, ...] ⤇ [6, 6, ...].
 Write numbers 1 to on a circle. Then = sum of the products of all adjacent numbers. E.g., = 1 ⋅ 2 ⋅ 3 + 2 ⋅ 3 ⋅ 4 + 3 ⋅ 4 ⋅ 5 + 4 ⋅ 5 ⋅ 1 + 5 ⋅ 1 ⋅ 2 = 120.
 Consider the multiset (bag) = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...] = and form the set (where is a set in the strict sense) of all submultisets (subbags) of . Then the number of elements of is equal to . E.g. for = [1, 2, 2] we get = { [ ], [2], [2, 2], [1], [1, 2], [1, 2, 2] } and = 3! = 6.
 Increasing colored 12 trees with choice of two colors for the rightmost branch of nonleaves.
 Number of necklaces with labeled beads of 1 color.
Formulae
 $n!:=\prod _{k=1}^{n}k=1^{(n)}=n_{(n)},$
where
and
are respectively the
rising factorial and the
falling factorial.
 $(2n)!=2^{n}\prod _{k=1}^{n}t_{2k1}=2^{n}\prod _{k=1}^{n}k(2k1)=2^{n}~n!\prod _{k=1}^{n}(2k1)=2^{n}~n!~(2n1)!!,\quad n\geq 0,$
 $(2n+1)!=(2n+1)(2n)!=(2n+1)~2^{n}\prod _{k=1}^{n}t_{2k1}=(2n+1)~2^{n}\prod _{k=1}^{n}k(2k1)=2^{n}~n!\prod _{k=1}^{n+1}(2k1)=2^{n}~n!~(2n+1)!!,\quad n\geq 0,$
where
is the
th triangular number,
is the
double factorial and where for
0! we get the
empty product 1.
The following definite integral (Euler’s integral form) for the factorial
 $n!=\int _{0}^{\infty }x^{n}e^{x}dx$
leads to the generalization for
 $\Gamma (z)=\int _{0}^{\infty }t^{z1}e^{t}dt$
which is called the gamma function.
For
a
nonnegative integer, we thus have
 $\Gamma (n)=(n1)!$
a result of the somewhat unfortunate notation due to Legendre.^{[3]}
Recurrences
 $n!={\begin{cases}1&{\text{if }}n=0,\\n\cdot (n1)!&{\text{if }}n>0.\end{cases}}$

n! = (n − 1) ⋅ [(n − 1)! + (n − 2)!], n ≥ 2. 
Note that the subfactorial has a similar recurrence

!n = (n − 1) ⋅ [!(n − 1) + !(n − 2)], n ≥ 2. 
So, for

Generating function
 $G_{\{n!\}}(x)=\sum _{n=0}^{\infty }n!~x^{n}=?$
Exponential generating function
The
exponential generating function of
is
 $E_{\{n!\}}(x)=\sum _{n=0}^{\infty }n!~{\frac {x^{n}}{n!}}=\sum _{n=0}^{\infty }x^{n}={\frac {1}{1x}}.$
Asymptotic behavior

Approximations to n!
Approximations to
( is the nearest integer function)


Stirling’s approximation (nearest integer)

Gosper’s approximation (nearest integer)


A000142

A005394

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 n!
Stirling’s approximation to
is

A005395 Leading term of Stirling’s approximation to
,
2√ 2π n (n / e) n, n ≥ 0, 
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
,
2√ 2π n (n / 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
,
2√ 2π n (n / e) n, n ≥ 0, 
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 n!
R.W. Gosper’s approximation to
is

A090583 Gosper’s approximation to
,
2√ (2n + 1 / 3) π (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 Peter Luschny: Approximation Formulas for the Factorial Function n!
Sum of reciprocals of n!
 and
where
is the base of the natural logarithm.
These are obtained from the
Maclaurin expansion of
evaluated at
and

Prime factors of n!
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

ω (n!) = ω (rad (n!)) = ω (n #) = π (n), 
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

sopf (n!) = sopf (n #) = pi , 
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

rad (n!) = sqf (n!) = n # = pi , 
where
is the
prime counting function and
is the
th
prime.
Divisors of n!
Divisors of
are (...)
^{(Elaborate: Divisors of n!)} ^{[4]}
Base 10 representation of n!
Number of trailing zeros of n!
The number of
trailing zeros (in base
10) in
(highest power of
5 dividing
and highest power of
10 dividing
) is given by
 ${\rm {NTZ}}(n!)=\alpha (n,5)$
where the exponent of prime
in the
prime factorization of
is given by
Legendre’s formula
 $\alpha (n,p)=\sum _{k=1}^{\lfloor \log _{p}(n)\rfloor }{{\bigg \lfloor }{\frac {n}{p^{k}}}{\bigg \rfloor }}$
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
 $x_{(n)}:=\prod _{i=0}^{n1}(xi),\quad n\geq 0,$
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
 $x^{(n)}:=\prod _{i=0}^{n1}(x+i),\quad n\geq 0,$
where for
we get the
empty product, giving
1.
Sequences
A027868 Number of trailing zeros (in base
10) in
(highest power of
5 dividing
and highest power of
10 dividing
).

{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, ...}
A004154 Omitting trailing zeros (in base
10) from factorial numbers, i.e.
.

{1, 1, 2, 6, 24, 12, 72, 504, 4032, 36288, 36288, 399168, 4790016, 62270208, 871782912, 1307674368, 20922789888, 355687428096, 6402373705728, 121645100408832, 243290200817664, ...}
See also
Notes
 ↑ Review contents (§ Applications of factorials).
 ↑ (see Calin D. Morosan, Information Processing Letters, 100 (2006), 188–193).
 ↑ One would have preferred the gamma function to be defined as so as to get but for historical reasons we instead have which begets .
 ↑ Needs elaboration (Divisors of n!).
External links