Faculty (Mathematics)

${\displaystyle n}$	${\displaystyle n!}$
0	1
1	1
2	2
3	6th
4th	24
5	120
6th	720
7th	5,040
8th	40,320
9	362.880
10	3,628,800
20th	2.432 ... 10 18
50	3.041 ... 10 64
100	9.332 ... 10 157

The faculty (sometimes, especially in Austria, also called factorial ) is a function in mathematics that assigns the product of all natural numbers (without zero) less than and equal to this number to a natural number . It is abbreviated by an exclamation mark ("!") After the argument . This notation was first used in 1808 by the Alsatian mathematician Christian Kramp (1760-1826), who also introduced the term faculté "ability" for it around 1798 .

definition

For all natural numbers is ${\displaystyle n}$

${\displaystyle n!=1\cdot 2\cdot 3\dotsm n=\prod _{k=1}^{n}k}$

defined as the product of the natural numbers from 1 to . Since the empty product is always 1, the following applies ${\displaystyle n}$

${\displaystyle 0!=1}$

The faculty can also be defined recursively :

${\displaystyle n!={\begin{cases}1,&n=0\\n\cdot (n-1)!,&n>0\end{cases}}}$

Faculties for negative or non-integer numbers are not defined. But there is an extension of the factorial to such arguments (see section Gamma function ).

Examples

Diagram of 0! to 4!

${\displaystyle {\begin{array}{rll}0!&=1&=1\\1!&=1&=1\\2!&=1\cdot 2&=2\\3!&=1\cdot 2\cdot 3&=6\\4!&=1\cdot 2\cdot 3\cdot 4&=24\\5!&=1\cdot 2\cdot 3\cdot 4\cdot 5&=120\\&\;\vdots \end{array}}}$

The values ​​of the faculties form the sequence A000142 in OEIS .

Explicit factorial values ​​from 0 to 20

0!	1
1!	1
2!	2
3!	6th
4!	24
5!	120
6!	720
7!	5,040
8th!	40,320
9!	362.880
10!	3,628,800
11!	39,916,800
12!	479.001.600
13!	6.227.020.800
14!	87.178.291.200
15!	1,307,674,368,000
16!	20,922,789,888,000
17!	355,687,428,096,000
18!	6,402,373,705,728,000
19!	121,645,100,408,832,000
20!	2,432,902,008,176,640,000

Applications

Permutations

In counting combinatorics , faculties play an important role because the number of possibilities is to arrange distinguishable objects in a row. If there is an -element set, so is the number of bijective mappings (the number of permutations ). This also applies in particular to the case where there is exactly one possibility to map the empty set onto itself. ${\displaystyle n!}$ ${\displaystyle n}$ ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle X\to X}$ ${\displaystyle n=0}$

For example, in a car race with six drivers, there are different options for the sequence when crossing the finish line when all the drivers have reached the finish. All six drivers are eligible for first place. Once the first driver has arrived, only five drivers can compete for second place. For the occupancy of the second place, it is decisive which of the six drivers does not have to be taken into account (since he is already placed in first place). For this reason, it must be counted separately for each possible occupancy of place 1 how many occupancy possibilities exist for place 2. There are therefore options for occupying places 1 and 2 with six drivers . If the second place is also taken, only four drivers are considered for the third place, which results in occupancy options for the first three places and six drivers , etc. So in the end there are ${\displaystyle 6!}$ ${\displaystyle 6\cdot 5}$ ${\displaystyle 6\cdot 5\cdot 4}$

${\displaystyle 6!=6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=720}$

different ranking lists for the finish.

Binomial coefficients

A term that has a similar central position in counting combinatorics as the faculty is the binomial coefficient

${\displaystyle {n \choose k}={\frac {n!}{k!\,(n-k)!}}}$.

It indicates the number of possibilities to select a -element subset from a -element set. The reverse is true ${\displaystyle k}$ ${\displaystyle n}$

${\displaystyle n!=\sum _{i=0}^{n-1}(-1)^{i}{\binom {n}{n-i}}(n-i)^{n}}$.

Here is the most popular example, using the 6 out of 49 number lottery

${\displaystyle {49 \choose 6}={\frac {49!}{6!\,(49-6)!}}=13\,983\,816}$

Options.

Taylor series

A prominent place where faculties occur are the Taylor series of many functions such as the sine function and the exponential function .

Euler's number

The Euler number can be of as the sum of reciprocals define the faculties: ${\displaystyle \mathrm {e} }$

${\displaystyle \mathrm {e} =\sum _{k=0}^{\infty }{\frac {1}{k!}}={\frac {1}{0!}}+{\frac {1}{1!}}+{\frac {1}{2!}}+{\frac {1}{3!}}+{\frac {1}{4!}}+\dotsb }$

Numerical calculation and approximation

The faculty and the Stirling formula

Recursive and iterative computation

The numerical value for can be calculated recursively or iteratively , provided it is not too large. ${\displaystyle n!}$ ${\displaystyle n}$

The largest factorial that can be calculated by most commercially available pocket calculators is because it is outside the range of numbers usually available. The largest factorial that can be represented as a floating point number in the double precision format of the IEEE 754 standard is . ${\displaystyle 69!\approx 1{,}7\cdot 10^{98},}$ ${\displaystyle 70!\approx 1{,}2\cdot 10^{100}}$ ${\displaystyle 170!\approx 7{,}3\cdot 10^{306}}$

Python program

With libraries for very large integers (no limitation to 32, 64 or e.g. 512 bits), an Intel Pentium 4, for example, needs to be used to calculate 10,000! just a few seconds. The number has 35660 digits in decimal notation , with the last 2499 digits consisting only of the digit zero .

# Syntax: Python 3.7
n = int(input('Fakultät von n = '))
f = 1
for i in range(1, n + 1):
    f *= i
print(f'{n}! = {f}')

Recursive solution

def fak(n: int) -> int:
    return 1 if n <= 1 else n * fak(n - 1)

Java program

public static int factorial(int n) {
    assert n >= 0;

    int val = 1;
    for(int i = 2; i <= n; ++i) {
        val *= i;
    }
    return val;
}

Recursive solution

public static int factorial(int n) {
	if(n <= 1)
		return 1;
	// else
		return factorial(n - 1) * n;
	// end if
}

Approximation with the Stirling formula

When is large, you can get a good approximation for using the Stirling formula : ${\displaystyle n}$ ${\displaystyle n!}$

${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{\mathrm {e} }}\right)^{n}}$

It means that the quotient of the left and right side converges for against . ${\displaystyle \sim }$ ${\displaystyle n\to \infty }$ ${\displaystyle 1}$

Faculty-like functions

There are a number of other sequences and functions that look similar to the faculty in their definition or properties:

Gamma function

The gamma function

The gamma function generalizes the faculty around its domain of definition from natural to complex numbers : ${\displaystyle \Gamma (z)}$

${\displaystyle z!=\Gamma (z+1),\qquad z\in \mathbb {C} }$

${\displaystyle \Gamma (z)=\int \limits _{0}^{\infty }t^{z-1}\mathrm {e} ^{-t}\mathrm {d} t}$

Factorial

The rising and falling factorials and represent a combinatorial generalization because . ${\displaystyle (n)_{k}}$ ${\displaystyle (n)^{k}}$ ${\displaystyle (n)_{n}=(1)^{n}=n!}$

Primorial (Primary Faculty)

The prime faculty of a number is the product of the prime numbers less than or equal to the number:

${\displaystyle n_{\#}=\prod _{p\leq n,\;p{\text{ prim}}}p}$

Sub-faculty

The sub-faculty that occurs primarily in combinatorial studies

${\displaystyle !n=n!\cdot \sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$

denotes the number of all fixed point-free permutations of elements. ${\displaystyle n}$

Double faculty

definition

The less frequently used double faculty or double faculty is less than or equal to the product of all even numbers . For odd it is the product of all odd numbers less than or equal to . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

It is defined as:

${\displaystyle n!!={\begin{cases}n\cdot (n-2)\cdot (n-4)\dotsm 2&{\text{für }}n{\text{ gerade und }}n>0,\\n\cdot (n-2)\cdot (n-4)\dotsm 1&{\text{für }}n{\text{ ungerade und }}n>0,\\1&{\text{für }}n\in \{-1,0\}\end{cases}}}$

Often, instead of the double faculty, expressions with the ordinary faculty are used. It applies

${\displaystyle (2k)!!=2^{k}k!}$     and     ${\displaystyle (2k-1)!!={\frac {(2k)!}{2^{k}k!}}}$

If non-integer function values ​​are allowed, then there is exactly one extension to negative odd numbers, so that applies to all odd whole numbers . The formula for odd is obtained . ${\displaystyle n!!=n\cdot (n-2)!!}$ ${\displaystyle n}$ ${\displaystyle n!!={\tfrac {1}{n+2}}\cdot {\tfrac {1}{n+4}}\dotsm {\tfrac {1}{1}}}$ ${\displaystyle n<0}$

The values ​​of the double faculties form the sequence A006882 in OEIS .

Examples

• ${\displaystyle 6!!=6\cdot 4\cdot 2=48}$
• ${\displaystyle 7!!=7\cdot 5\cdot 3\cdot 1=105}$

Application examples

• The number of -digit combinations of non-element pairs formed from elements is given by the recursion with a recursion start (2 elements!). Resolution of the recursion results . Should z. B. Teams meet in pairs through a raffle, then the probability that two certain play against each other is given by . ${\displaystyle P_{2n}}$ ${\displaystyle n}$ ${\displaystyle 2n}$ ${\displaystyle P_{2n}=(2n-1)P_{2n-2}}$ ${\displaystyle P_{2}=1}$ ${\displaystyle P_{2n}=(2n-1)!!}$ ${\displaystyle 2n}$ ${\displaystyle {\frac {P_{2n-2}}{P_{2n}}}={\frac {1}{2n-1}}}$
• The number of elements of the hyperoctahedral group is . ${\displaystyle B_{n}}$ ${\displaystyle (2n-1)!!}$
• The number of fixed-point-free involutor permutations of elements is . ${\displaystyle 2n}$ ${\displaystyle (2n)!!}$
• The -th moment of the standard normal distribution is . ${\displaystyle 2n}$ ${\displaystyle (2n-1)!!}$
• The dual faculty also occurs in integral tables and formulas for special functions .
• For natural applies . ${\displaystyle n}$ ${\displaystyle (2n-1)!!={\frac {2^{n}}{\sqrt {\pi }}}\Gamma \left(n+{\frac {1}{2}}\right)}$

Multifaculty

Analogous to the double factorial, a triple ( ), quadruple ( ),…, -fold factorial ( ) is recursively defined as ${\displaystyle n!!!}$ ${\displaystyle n!!!!}$ ${\displaystyle k}$ ${\displaystyle n!^{(k)}}$

${\displaystyle n!^{(k)}:={\begin{cases}1&{\text{falls }}n=0\\n&{\text{falls }}0<n\leq k\\n(n-k)!^{(k)}&{\text{falls }}n>k\end{cases}}}$

Super faculty

The term super faculty is used for (at least) two different functions; one is defined as the product of the first faculties: ${\displaystyle \operatorname {sf} (n)}$

${\displaystyle \operatorname {sf} (n)=\prod _{i=1}^{n}i!=1!\cdot 2!\cdot 3!\cdot 4!\dotsm n!=G(n+2)}$

with the Barnesian function ${\displaystyle G(n)}$ , the other as a multiple power of a factorial

${\displaystyle n\$=\underbrace {n!^{{n!}^{{\cdot }^{{\cdot }^{{\cdot }^{n!}}}}}} _{n!}.}$

Hyperfaculty

The hyperfaculty for natural is defined as follows: ${\displaystyle H_{n}}$ ${\displaystyle n}$

${\displaystyle H(n)=\prod _{i=1}^{n}i^{i}=1^{1}\cdot 2^{2}\cdot 3^{3}\cdot 4^{4}\dotsm n^{n}}$

It can be generalized to complex numbers using the K function .

Related functions

• Smarandache function

Prime exponent

If you are not looking for the full number , but only the exponent of one of its prime factors, this can be determined directly and efficiently. ${\displaystyle n!}$

${\displaystyle v_{p}(n!)={\begin{cases}0&{\text{falls }}n<p\\\lfloor n/p\rfloor +v_{p}(\lfloor n/p\rfloor !)&{\text{sonst}}\end{cases}}}$

Here stands for the exponent of in the prime factorization of . ${\displaystyle v_{p}(k)}$ ${\displaystyle p}$ ${\displaystyle k}$

In the example above, the number of zeros at the end of 10,000! To determine the exponent of 5, the exponent of 2 is definitely greater.

${\displaystyle {\begin{aligned}v_{5}(10{.}000!)&=2{.}000+v_{5}(2{.}000!)=2{.}000+400+v_{5}(400!)\\&=2{.}400+80+v_{5}(80!)=2{.}480+16+v_{5}(16!)\\&=2{.}496+3+v_{5}(3!)=2{.}499\end{aligned}}}$

Web links

Wiktionary: Faculty  - explanations of meanings, word origins, synonyms, translations

Wikibooks: Math for Non-Freaks: Faculty  - Study and Teaching Materials

• Peter Luschny: The Homepage of Factorial Algorithms . efficient algorithms and further information
• Eric W. Weisstein : Factorial . In: MathWorld (English).

Individual evidence

1. ↑ Eric W. Weisstein : Double Factorial . In: MathWorld (English).
2. ↑ Eric W. Weisstein : Multifactorial . In: MathWorld (English).
3. ↑ ^{a b} Eric W. Weisstein : Superfactorial . In: MathWorld (English).
4. ↑ Eric W. Weisstein : Hyperfactorial . In: MathWorld (English).