This site is supported by donations to The OEIS Foundation.

Factorial

From OeisWiki
(Redirected from Rising factorial)
Jump to: navigation, search
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 ncycle(i) permutation cycles. Then, we have
    n!

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

where
x (n)
and
x(n)
are respectively the rising factorial and the falling factorial.
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 factorial

leads to the generalization for
ℜ(z) > 0

which is called the gamma function.

For
z = n
a nonnegative integer, we thus have

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

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

Exponential generating function

The exponential generating function of
n!
is

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!)[4]

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
where the exponent of prime
p
in the prime factorization of
n!
is given by Legendre’s formula

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
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
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. 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)!
    .
  4. Needs elaboration (Divisors of n!).

External links