This site is supported by donations to The OEIS Foundation.

Factorial

From OeisWiki
(Redirected from Number of permutations)
Jump to: navigation, search

This is an unrefereed and unapproved page. We recommend that you start by reading the official OEIS entry for the factorial numbers, https://oeis.org/A000142 (which has links to many other resources). - N. J. A. Sloane 08:59, 17 July 2020 (EDT)


The factorial of a nonnegative integer
n
is defined as the product of all positive integers up to
n
, and is notated as
n!
. 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
n!, n   ≥   0
.
{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
    n > 0, n!
    is the number of
    n × n
    (0, 1)-matrices with each row and column containing exactly one entry equal to 1.
  • n!
    is the permanent of the
    n × n
    matrix
    M
    with
    M  (i, j) = 1
    .
  • n!
    is also the determinant of an
    n × n
    square matrix
    An
    whose coefficients are the reciprocals of beta function:
    a{i, j} = 1 / β (i, j), det (An ) = n!

In regards to graphs:

  • n!
    is also the number of optimal broadcast schemes in the complete graph
    Kn
    , equivalent to the number of binomial trees embedded in
    Kn
    .[2]
  • Let
    Sn
    denote the
    n
    -star graph. The
    Sn
    structure consists of
    n
    Sn  − 1
    structures. (This sequence gives the number of edges between the vertices of any two specified
    Sn  + 1
    structures in
    Sn  + 2
    , with
    n > 0
    ).
  • Chromatic invariant of the sun graph
    Sn  − 2
    .

In regards to chains:

  • The number of chains of maximal length in the power set of
    {1, 2, ..., n}
    ordered by the subset relation.
  • n!
    is also the number of order-decreasing full transformations (of an
    n
    -chain).
  • (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
    distinct letters is
    n!, n   ≥   0
    .
  • Consider the
    n!
    permutations of the integer sequence
    [n] = 1, 2, ..., n
    . The
    i
    -th permutation consists of
    n-cycle (i )
    permutation cycles. Then, we have
    n!

    i  = 1
    2n-cycle (i ) = (n + 1)!
    . E.g., for
    n = 3
    , we have
    3-cycle (1) = 3, 3-cycle (2) = 2, 3-cycle (3) = 1, 3-cycle (4) = 2, 3-cycle (5) = 1, 3-cycle (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
    n!
    .
  • 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:

  • n!
    is the number of partition tableaux of size
    n
    . (See Steingrimsson/Williams link for the definition.)
  • n!
    is the number of set partitions of
    {1, 2, ..., 2 n  −  1, 2 n}
    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)
    T (n  −  1)
    elements with 1 element A, 2 elements B, ...,
    n  −  1
    elements
    X
    . E.g., at
    n = 5
    , 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
    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.
  • 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
    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 (bag)
    M =
    [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...] =
    [1: 1, 2: 2, ..., n: n]
    and form the set
    U
    (where
    U
    is a set in the strict sense) of all submultisets (subbags)
    N
    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

n! :=
n
k  = 1
  
k  =  1(n)  =  n(n)  ,
where
x (n)
and
x(n)
are respectively the rising factorial and the falling factorial.
(2 n)!  =  2n
n
k  = 1
  
t 2 k  − 1  =  2n
n
k  = 1
  
k (2 k  − 1)  =  2n n!
n
k  = 1
  
(2k  − 1)  =  2n n!  (2 n − 1)!!, n ≥ 0,
(2 n + 1)!  =  (2 n + 1) (2 n)!  =  (2 n + 1) 2n
n
k  = 1
  
t 2 k  − 1  =  (2 n + 1) 2n
n
k  = 1
  
k (2 k  − 1)  =  2n n!
n + 1
k  = 1
  
(2 k  − 1)  =  2n n!  (2 n + 1)!!, n ≥ 0,
where
tn
is the
n
th triangular number,
n!!
is the double factorial and where for 0! we get the empty product 1.

The following definite integral (Euler’s integral form) for the factorialSee proof: [3]

n!  = 
0
t  n e  − t dt
leads to the generalization, for complex
z
not a negative integer, of Gauss’s Pi function
Π (z)  :=
0
tz e  − t dt
or to the generalization, for complex
z
neither 0 nor negative integer,
Γ (z)  :=
0
tz − 1 e  − t dt  =  Π (z − 1),

which is called the Gamma function.[4]

For
z = n
a positive integer, we thus have
Γ (n)  =  (n − 1) !

a result of the somewhat unfortunate notation due to Legendre.[5]

Recurrences

     

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
n   ≥   2,
n!
(n − 1)! + (n − 2)!
 =  n − 1  = 
!n
!(n − 1) + !(n − 2)
 .

Generating function

G{n!}(x)  = 
n  = 0
  
n!  xn  =  ?

Exponential generating function

The exponential generating function of
n!
is
E{n!}(x)  = 
n  = 0
  
n!
xn
n!
 = 
n  = 0
  
xn  = 
1
1 − x
 .

Triangles

     
n!  = 
n
k  = 0
  
(−1)n  + k (
n
k
) k  n.
n
       
n

k  = 0
T  (n, k )

0   + 0^0  
1
1   − 0^1 + 1 * 1^1  
1
2   + 0^2 − 2 * 1^2 + 1 * 2^2  
2
3   − 0^3 + 3 * 1^3 − 3 * 2^3 + 1 * 3^3  
6
4   + 0^4 − 4 * 1^4 + 6 * 2^4 − 4 * 3^4 + 1 * 4^4  
24
5 − 0^5 + 5 * 1^5 − 10 * 2^5 + 10 * 3^5 − 5 * 4^5 + 1 * 5^5  
120
6   + 0^6 − 6 * 1^6 + 15 * 2^6 − 20 * 3^6 + 15 * 4^6 − 6 * 5^6 + 1 * 6^6  
720
7   − 0^7 + 7 * 1^7 − 21 * 2^7 + 35 * 3^7 − 35 * 4^7 + 21 * 5^7 − 7 * 6^7 + 1 * 7^7  
5040
8   + 0^8 − 8 * 1^8 + 28 * 2^8 − 56 * 3^8 + 70 * 4^8 − 56 * 5^8 + 28 * 6^8 − 8 * 7^8 + 1 * 8^8  
40320
9   − 0^9 + 9 * 1^9 − 36 * 2^9 + 84 * 3^9 − 126 * 4^9 + 126 * 5^9 − 84 * 6^9 + 36 * 7^9 − 9 * 8^9 + 1 * 9^9  
362880
10 + 0^10 − 10 * 1^10 + 45 * 2^10 − 120 * 3^10 + 210 * 4^10 − 252 * 5^10 + 210 * 6^10 − 120 * 7^10 + 45 * 8^10 − 10 * 9^10 + 1 * 10^10  
3628800
11   − 0^11 + 11 * 1^11 − 55 * 2^11 + 165 * 3^11 − 330 * 4^11 + 462 * 5^11 − 462 * 6^11 + 330 * 7^11 − 165 * 8^11 + 55 * 9^11 − 11 * 10^11 + 1 * 11^11  
39916800
12   + 0^12 − 12 * 1^12 + 66 * 2^12 − 220 * 3^12 + 495 * 4^12 − 792 * 5^12 + 924 * 6^12 − 792 * 7^12 + 495 * 8^12 − 220 * 9^12 + 66 * 10^12 − 12 * 11^12 + 1 * 12^12  
479001600

k = 0

1
2
3
4
5
6
7
8
9
10
11
12  

n
       
n

k  = 0
T  (n, k )

0   1  
1
1   0 1  
1
2   0 −2 4  
2
3   0 3 −24 27  
6
4   0 −4 96 −324 256  
24
5 0 5 −320 2430 −5120 3125  
120
6   0 −6 960 −14580 61440 −93750 46656  
720
7   0 7 −2688 76545 −573440 1640625 −1959552 823543  
5040
8   0 −8 7168 −367416 4587520 −21875000 47029248 −46118408 16777216  
40320
9   0 9 −18432 1653372 −33030144 246093750 −846526464 1452729852 −1207959552 387420489  
362880
10 0 −10 46080 −7085880 220200960 −2460937500 12697896960 −33897029880 48318382080 −34867844010 10000000000  
3628800

k = 0

1
2
3
4
5
6
7
8
9
10  
A258773 Triangle read by rows,
T  (n, k) = ( − 1)n  − k (  nk  ) k  n
, for
n   ≥   0
and
0   ≤   k   ≤   n
.
{1, 0, 1, 0, −2, 4, 0, 3, −24, 27, 0, − 4, 96, −324, 256, 0, 5, −320, 2430, −5120, 3125, 0, − 6, 960, −14580, 61440, − 93750, 46656, 0, 7, −2688, 76545, −573440, 1640625, −1959552, 823543, 0, −8, 7168, −367416, 4587520, −21875000, 47029248, − 46118408, 16777216, ...}
A000312
a (n) = nn, n   ≥   0
; number of labeled mappings from
n
points to themselves (endofunctions). (Rightmost diagonal of above triangle.)
{1, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489, 10000000000, 285311670611, 8916100448256, 302875106592253, 11112006825558016, 437893890380859375, ...}

Factorial triangle

Factorial triangle
(Triangle of unsigned Stirling numbers of the first kind)
n
       
n

k  = 1
T  (n, k )

1   1  
1
2   1 1  
2
3   1 3 2  
6
4   1 6 11 6  
24
5   1 10 35 50 24  
120
6 1 15 85 225 274 120  
720
7   1 21 175 735 1624 1764 720  
5040
8   1 28 322 1960 6769 13132 13068 5040  
40320
9   1 36 546 4536 22449 67284 118124 109584 40320  
362880
10   1 45 870 9450 63273 269325 723680 1172700 1026576 362880  
3628800

k = 1

2
3
4
5
6
7
8
9
10  
A094638 Triangle read by rows:
T  (n, k) =
| s (n, n  +1 − k) |
, where
s(n, k)
are the [signed] Stirling numbers of the first kind A008276 (
1   ≤   k   ≤   n
; in other words, the unsigned Stirling numbers of the first kind in reverse order).
{1, 1, 1, 1, 3, 2, 1, 6, 11, 6, 1, 10, 35, 50, 24, 1, 15, 85, 225, 274, 120, 1, 21, 175, 735, 1624, 1764, 720, 1, 28, 322, 1960, 6769, 13132, 13068, 5040, 1, 36, 546, 4536, 22449, 67284, 118124, 109584, 40320, 1, 45, 870, 9450, 63273, 269325, 723680, 1172700, 1026576, 362880, ...}

Asymptotic behavior

n! ∼  
2  2π n
 
n
e
n.

Approximations to n!

Approximations to
n!

(
[·]
is the nearest integer function)

n
n!
Stirling’s approximation
(nearest integer)

2  2π n
 
n
e
n


2  2π n
 
n
e
n
   − n!
Gosper’s approximation
(nearest integer)

  
2  (2n +
1
3
 )  π 
 
n
e
n


  
2  (2n +
1
3
 )  π 
 
n
e
n
   − n!
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
n!
is
n! ≈  
2  2π n
 
n
e
n,  n ≥ 0.
A005395 Leading term of Stirling’s approximation to
n!
,
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
n!
,
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
n!
,
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
n!
is
n! ≈  
2  (2n +
1
3
 )  π 
 
n
e
n,  n ≥ 0.
A090583 Gosper’s approximation to
n!
,
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!

n   = 0
  
1
n!
 =  e,
and
n   = 0
  
(−1)n
n!
 = 
1
e
  ,
where
e
is the base of the natural logarithm. These are obtained from the Maclaurin expansion of
e  x
evaluated at
x = 1
and
x =  − 1
n   = 0
  
xn
n!
 =  e  x.

Prime factors of n!

The number of prime factors (with multiplicity) of
n!
is given by the summatory Omega function
Ω (n!)  = 
n
i  = 1
  
Ω (i) .
The number of distinct prime factors of
n!
is given by the prime counting function
π (n)
ω (n!)  =  ω (rad (n!))  =  ω (n #)  =  π (n),
where
rad (n!)
is the radical of
n!
, i.e. the squarefree kernel
sqf (n!)
. The sum of prime factors (with multiplicity) (integer log) of
n!
is
sopfr (n!)  =  ?
The sum of distinct prime factors of
n!
is the sum of prime factors of the primorial of
n
sopf (n!)  =  sopf (n #)  = 
π (n)
i  = 1
  
pi ,
where
π (n)
is the prime counting function and
pi
is the
i
-th prime. The product of distinct prime factors (radical or squarefree kernel) of
n!
is the primorial of
n
rad (n!)  =  sqf (n!)  =  n #  = 
π (n)
i  = 1
  
pi ,
where
π (n)
is the prime counting function and
pi
is the
i
-th prime.

Divisors of n!

Divisors of
n!
are (...) (Elaborate: Divisors of n!.)[6]

Base 10 representation of n!

Number of trailing zeros of n!

The number of trailing zeros (in base 10) in
n!
(highest power of 5 dividing
n!
and highest power of 10 dividing
n!
) is given by
NTZ (n!)  =  α (n, 5),
where the exponent of prime
p
in the prime factorization of
n!
is given by Legendre’s formula
α (n, p)  = 
⌊  logp(n ) ⌋
k  = 1
  
n
  p  k
.

Pochhammer symbol

Depending on the context the Pochhammer symbol
(x)n
, 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
x(n)
) of the real number
x
,
n
being a nonnegative integer is defined as
x(n) :=
n − 1
i  = 0
  
(xi ), n ≥ 0,
where for
n = 0
we get the empty product, giving 1.

Rising factorial

The rising factorial (represented with
x(n)
) of the real number
x
,
n
being a nonnegative integer is defined as
x (n) :=
n − 1
i  = 0
  
(x + i ), n ≥ 0,
where for
n = 0
we get the empty product, giving 1.

Sequences

A027868 Number of trailing zeros (in base 10) in
n!
(highest power of 5 dividing
n!
and highest power of 10 dividing
n!
).
{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.
n!
10α  (n, 5)
, n   ≥   0
.
{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. Review contents (§ Applications of factorials).
  2. (see Calin D. Morosan, Information Processing Letters, 100 (2006), 188–193).
  3. See: Proof of Euler’s Integral Formula—CrystalMath.
    Theorem (Euler’s integral form for
    n!
    ).
     (Euler)

         
    n!  = 
    0
    t  n e  − t dt.


    Proof.
    d  n
    dxn
    x  − 1  =  (−1)n n! x  − (n  + 1),
    0
    e  − xt dt  =  x  − 1,
    d  n
    dxn
    0
    e  − xt dt  =  (−1)n
    0
    t  n e  − xt dt,

    therefore

    (−1)n
    0
    t  n e  − xt dt  =  (−1)n n! x  − (n  + 1),
    finally, letting
    x = 1
    , we have
    0
    t  n e  − t dt  =  n!.
     
    Note that if we let
    x =
    1
    k  
    , k ∈ ℕ+
    , we have
    0
    t  n e  − t / k dt  =  n! k  n  + 1,

    which yields

    1
    k  
    0
    t  n e  − t / k dt  = 
    n
    i  = 1
      
    k  i,
    where is the k-multifactorial of
    k  n
    .
  4. Peter Luschny, Is the Gamma function mis-defined? Or: Hadamard versus Euler - Who found the better Gamma function?
  5. One would have preferred the Gamma function to be defined as
    Γ(z) =
    0
    t  z e  − t dt
    so as to get
    Γ(n) = n!
    but for historical reasons we instead have
    Γ(z) =
    0
    t  z − 1 e  − t dt
    which begets
    Γ(n) = (n  −  1)!
    .
  6. Needs elaboration (Divisors of n!).

External links