Misplaced Pages

#881118

139-587: ( n k ) = n ( n − 1 ) ⋯ ( n − k + 1 ) k ( k − 1 ) ⋯ 1 , {\displaystyle {\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},} which can be written using factorials as n ! k ! ( n − k ) ! {\displaystyle \textstyle {\frac {n!}{k!(n-k)!}}} whenever k ≤ n {\displaystyle k\leq n} , and which

278-458: A 1 , … , a n } {\displaystyle A=\{a_{1},\ldots ,a_{n}\}} is a finite set , the multiset ( A , m ) is often represented as where upper indices equal to 1 are omitted. For example, the multiset { a , a , b } may be written { a 2 , b } {\displaystyle \{a^{2},b\}} or a 2 b . {\displaystyle a^{2}b.} If

417-598: A n  ×  n matrix in Jordan normal form that has a single eigenvalue. Its multiplicity is n , its multiplicity as a root of the minimal polynomial is the size of the largest Jordan block, and its geometric multiplicity is the number of Jordan blocks. A multiset may be formally defined as an ordered pair ( A , m ) where A is the underlying set of the multiset, formed from its distinct elements, and m : A → Z + {\displaystyle m\colon A\to \mathbb {Z} ^{+}}

556-717: A double exponential function . Its growth rate is similar to n n {\displaystyle n^{n}} , but slower by an exponential factor. One way of approaching this result is by taking the natural logarithm of the factorial, which turns its product formula into a sum, and then estimating the sum by an integral: ln ⁡ n ! = ∑ x = 1 n ln ⁡ x ≈ ∫ 1 n ln ⁡ x d x = n ln ⁡ n − n + 1. {\displaystyle \ln n!=\sum _{x=1}^{n}\ln x\approx \int _{1}^{n}\ln x\,dx=n\ln n-n+1.} Exponentiating

695-413: A function that respects sorts . He also introduced a multinumber  : a function f  ( x ) from a multiset to the natural numbers , giving the multiplicity of element x in the multiset. Monro argued that the concepts of multiset and multinumber are often mixed indiscriminately, though both are useful. One of the simplest and most natural examples is the multiset of prime factors of

834-436: A one-to-one correspondence between these functions and the multisets that have their elements in U . This extended multiplicity function is commonly called simply the multiplicity function , and suffices for defining multisets when the universe containing the elements has been fixed. This multiplicity function is a generalization of the indicator function of a subset , and shares some properties with it. The support of

973-422: A , a , b ] . The cardinality or "size" of a multiset is the sum of the multiplicities of all its elements. For example, in the multiset { a , a , b , b , b , c } the multiplicities of the members a , b , and c are respectively 2, 3, and 1, and therefore the cardinality of this multiset is 6. Nicolaas Govert de Bruijn coined the word multiset in the 1970s, according to Donald Knuth . However,

1112-408: A 1685 treatise by John Wallis , a study of their approximate values for large values of n {\displaystyle n} by Abraham de Moivre in 1721, a 1729 letter from James Stirling to de Moivre stating what became known as Stirling's approximation , and work at the same time by Daniel Bernoulli and Leonhard Euler formulating the continuous extension of the factorial function to

1251-507: A collection of n distinct variables X s labeled by the elements s of S , and expand the product over all elements of  S : ∏ s ∈ S ( 1 + X s ) ; {\displaystyle \prod _{s\in S}(1+X_{s});} it has 2 distinct terms corresponding to all the subsets of S , each subset giving the product of the corresponding variables X s . Now setting all of

1390-467: A common example in the use of different computer programming styles and methods. The computation of n ! {\displaystyle n!} can be expressed in pseudocode using iteration as or using recursion based on its recurrence relation as Other methods suitable for its computation include memoization , dynamic programming , and functional programming . The computational complexity of these algorithms may be analyzed using

1529-545: A definition for the factorial at all complex numbers other than the negative integers. One property of the gamma function, distinguishing it from other continuous interpolations of the factorials, is given by the Bohr–Mollerup theorem , which states that the gamma function (offset by one) is the only log-convex function on the positive real numbers that interpolates the factorials and obeys the same functional equation. A related uniqueness theorem of Helmut Wielandt states that

SECTION 10

#1733085348882

1668-421: A factor of two to produce one of these trailing zeros. The leading digits of the factorials are distributed according to Benford's law . Every sequence of digits, in any base, is the sequence of initial digits of some factorial number in that base. Another result on divisibility of factorials, Wilson's theorem , states that ( n − 1 ) ! + 1 {\displaystyle (n-1)!+1}

1807-697: A function of the number of digits or bits in the result. By Stirling's formula, n ! {\displaystyle n!} has b = O ( n log ⁡ n ) {\displaystyle b=O(n\log n)} bits. The Schönhage–Strassen algorithm can produce a b {\displaystyle b} -bit product in time O ( b log ⁡ b log ⁡ log ⁡ b ) {\displaystyle O(b\log b\log \log b)} , and faster multiplication algorithms taking time O ( b log ⁡ b ) {\displaystyle O(b\log b)} are known. However, computing

1946-677: A generalization of the negative binomial formula (with one of the variables set to 1), which justifies calling the ( ( α k ) ) {\displaystyle \left(\!\!{\alpha \choose k}\!\!\right)} negative binomial coefficients: ( 1 − X ) − α = ∑ k = 0 ∞ ( ( α k ) ) X k . {\displaystyle (1-X)^{-\alpha }=\sum _{k=0}^{\infty }\left(\!\!{\alpha \choose k}\!\!\right)X^{k}.} This Taylor series formula

2085-445: A given set S of n elements in some fixed order, which establishes a bijection from an interval of ( n k ) {\displaystyle {\tbinom {n}{k}}} integers with the set of those k -combinations. Assuming S is itself ordered, for instance S = { 1, 2, ..., n }, there are two natural possibilities for ordering its k -combinations: by comparing their smallest elements first (as in

2224-487: A modified form of the factorial, omitting the factors in the factorial that are divisible by p . The digamma function is the logarithmic derivative of the gamma function. Just as the gamma function provides a continuous interpolation of the factorials, offset by one, the digamma function provides a continuous interpolation of the harmonic numbers , offset by the Euler–Mascheroni constant . The factorial function

2363-510: A multiset A {\displaystyle A} in a universe U is the underlying set of the multiset. Using the multiplicity function m {\displaystyle m} , it is characterized as Supp ⁡ ( A ) := { x ∈ U ∣ m A ( x ) > 0 } . {\displaystyle \operatorname {Supp} (A):=\{x\in U\mid m_{A}(x)>0\}.} A multiset

2502-425: A multiset are generally taken in a fixed set U , sometimes called a universe , which is often the set of natural numbers . An element of U that does not belong to a given multiset is said to have a multiplicity 0 in this multiset. This extends the multiplicity function of the multiset to a function from U to the set N {\displaystyle \mathbb {N} } of non-negative integers. This defines

2641-497: A natural number n . Here the underlying set of elements is the set of prime factors of n . For example, the number 120 has the prime factorization 120 = 2 3 3 1 5 1 , {\displaystyle 120=2^{3}3^{1}5^{1},} which gives the multiset {2, 2, 2, 3, 5} . A related example is the multiset of solutions of an algebraic equation . A quadratic equation , for example, has two solutions. However, in some cases they are both

2780-421: A notation that is meant to resemble that of binomial coefficients ; it is used for instance in (Stanley, 1997), and could be pronounced " n multichoose k " to resemble " n choose k " for ( n k ) . {\displaystyle {\tbinom {n}{k}}.} Like the binomial distribution that involves binomial coefficients, there is a negative binomial distribution in which

2919-404: A proof of Euclid's theorem that the number of primes is infinite. When n ! ± 1 {\displaystyle n!\pm 1} is itself prime it is called a factorial prime ; relatedly, Brocard's problem , also posed by Srinivasa Ramanujan , concerns the existence of square numbers of the form n ! + 1 {\displaystyle n!+1} . In contrast,

SECTION 20

#1733085348882

3058-440: A representation known as stars and bars . Factorial In mathematics , the factorial of a non-negative integer n {\displaystyle n} , denoted by n ! {\displaystyle n!} , is the product of all positive integers less than or equal to n {\displaystyle n} . The factorial of n {\displaystyle n} also equals

3197-405: A s, 2 b s, 3 c s, 7 d s) in this form: This is a multiset of cardinality k = 18 made of elements of a set of cardinality n = 4 . The number of characters including both dots and vertical lines used in this notation is 18 + 4 − 1 . The number of vertical lines is 4 − 1. The number of multisets of cardinality 18 is then the number of ways to arrange the 4 − 1 vertical lines among

3336-422: A sequence. Factorials appear more broadly in many formulas in combinatorics , to account for different orderings of objects. For instance the binomial coefficients ( n k ) {\displaystyle {\tbinom {n}{k}}} count the k {\displaystyle k} -element combinations (subsets of k {\displaystyle k} elements) from

3475-573: A set S is often denoted by ( S k ) {\displaystyle \textstyle {\binom {S}{k}}} . A combination is a combination of n things taken k at a time without repetition . To refer to combinations in which repetition is allowed, the terms k -combination with repetition, k - multiset , or k -selection, are often used. If, in the above example, it were possible to have two of any one kind of fruit there would be 3 more 2-selections: one with two apples, one with two oranges, and one with two pears. Although

3614-469: A set S of size n is given by a set of k not necessarily distinct elements of S , where order is not taken into account: two sequences define the same multiset if one can be obtained from the other by permuting the terms. In other words, it is a sample of k elements from a set of n elements allowing for duplicates (i.e., with replacement) but disregarding different orderings (e.g. {2,1,2} = {1,2,2}). Associate an index to each element of S and think of

3753-399: A set with n {\displaystyle n} elements, and can be computed from factorials using the formula ( n k ) = n ! k ! ( n − k ) ! . {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.} The Stirling numbers of the first kind sum to the factorials, and count

3892-603: A specific example, one can compute the number of five-card hands possible from a standard fifty-two card deck as: ( 52 5 ) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311,875,200 120 = 2,598,960. {\displaystyle {52 \choose 5}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.} Alternatively one may use

4031-418: A subset of exceptions with asymptotic density zero), it coincides with the largest prime factor of x {\displaystyle x} . The product of two factorials, m ! ⋅ n ! {\displaystyle m!\cdot n!} , always evenly divides ( m + n ) ! {\displaystyle (m+n)!} . There are infinitely many factorials that equal

4170-537: A symmetry that is evident from the binomial formula, and can also be understood in terms of k -combinations by taking the complement of such a combination, which is an ( n − k ) -combination. Finally there is a formula which exhibits this symmetry directly, and has the merit of being easy to remember: ( n k ) = n ! k ! ( n − k ) ! , {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},} where n ! denotes

4309-569: A term attributed to Peter Deutsch . A multiset has been also called an aggregate, heap, bunch, sample, weighted set, occurrence set, and fireset (finitely repeated element set). Although multisets were used implicitly from ancient times, their explicit exploration happened much later. The first known study of multisets is attributed to the Indian mathematician Bhāskarāchārya circa 1150, who described permutations of multisets. The work of Marius Nizolius (1498–1576) contains another early reference to

Combination - Misplaced Pages Continue

4448-953: A total of ( ( n k − 1 ) ) {\displaystyle \left(\!\!{n \choose k-1}\!\!\right)} possibilities. If n does not appear, then our original multiset is equal to a multiset of cardinality k with elements from [ n − 1] , of which there are ( ( n − 1 k ) ) . {\displaystyle \left(\!\!{n-1 \choose k}\!\!\right).} Thus, ( ( n k ) ) = ( ( n k − 1 ) ) + ( ( n − 1 k ) ) . {\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right).} The generating function of

4587-419: Is 1 {\displaystyle 1} , or in symbols, 0 ! = 1 {\displaystyle 0!=1} . There are several motivations for this definition: The earliest uses of the factorial function involve counting permutations : there are n ! {\displaystyle n!} different ways of arranging n {\displaystyle n} distinct objects into

4726-447: Is finite if its support is finite, or, equivalently, if its cardinality | A | = ∑ x ∈ Supp ⁡ ( A ) m A ( x ) = ∑ x ∈ U m A ( x ) {\displaystyle |A|=\sum _{x\in \operatorname {Supp} (A)}m_{A}(x)=\sum _{x\in U}m_{A}(x)}

4865-525: Is 1, according to the convention for an empty product . Factorials have been discovered in several ancient cultures, notably in Indian mathematics in the canonical works of Jain literature , and by Jewish mystics in the Talmudic book Sefer Yetzirah . The factorial operation is encountered in many areas of mathematics, notably in combinatorics , where its most basic use counts the possible distinct sequences –

5004-565: Is a common feature in scientific calculators . It is also included in scientific programming libraries such as the Python mathematical functions module and the Boost C++ library . If efficiency is not a concern, computing factorials is trivial: just successively multiply a variable initialized to 1 {\displaystyle 1} by the integers up to n {\displaystyle n} . The simplicity of this computation makes it

5143-415: Is a function from A to the set of positive integers, giving the multiplicity – that is, the number of occurrences – of the element a in the multiset as the number m ( a ) . (It is also possible to allow multiplicity 0 or ∞ {\displaystyle \infty } , especially when considering submultisets. This article is restricted to finite, positive multiplicities.) Representing

5282-1061: Is a polynomial in n , it and the generating function are well defined for any complex value of n . The multiplicative formula allows the definition of multiset coefficients to be extended by replacing n by an arbitrary number α (negative, real , or complex): ( ( α k ) ) = α k ¯ k ! = α ( α + 1 ) ( α + 2 ) ⋯ ( α + k − 1 ) k ( k − 1 ) ( k − 2 ) ⋯ 1 for  k ∈ N  and arbitrary  α . {\displaystyle \left(\!\!{\alpha \choose k}\!\!\right)={\frac {\alpha ^{\overline {k}}}{k!}}={\frac {\alpha (\alpha +1)(\alpha +2)\cdots (\alpha +k-1)}{k(k-1)(k-2)\cdots 1}}\quad {\text{for }}k\in \mathbb {N} {\text{ and arbitrary }}\alpha .} With this definition one has

5421-550: Is a single multiplication of a number with O ( n log ⁡ n ) {\displaystyle O(n\log n)} bits. Again, at each level of recursion the numbers involved have a constant fraction as many bits (because otherwise repeatedly squaring them would produce too large a final result) so again the amounts of time for these steps in the recursive calls add in a geometric series to O ( n log 2 ⁡ n ) {\displaystyle O(n\log ^{2}n)} . Consequentially,

5560-475: Is also the number of monomials of degree d in n indeterminates. Thus, the above series is also the Hilbert series of the polynomial ring k [ x 1 , … , x n ] . {\displaystyle k[x_{1},\ldots ,x_{n}].} As ( ( n d ) ) {\displaystyle \left(\!\!{n \choose d}\!\!\right)}

5699-663: Is changed to keep all but the last term, it would define a product of the same form, for a smaller factorial. This leads to a recurrence relation , according to which each value of the factorial function can be obtained by multiplying the previous value by n {\displaystyle n} : n ! = n ⋅ ( n − 1 ) ! . {\displaystyle n!=n\cdot (n-1)!.} For example, 5 ! = 5 ⋅ 4 ! = 5 ⋅ 24 = 120 {\displaystyle 5!=5\cdot 4!=5\cdot 24=120} . The factorial of 0 {\displaystyle 0}

Combination - Misplaced Pages Continue

5838-558: Is divisible by n {\displaystyle n} if and only if n {\displaystyle n} is a prime number . For any given integer x {\displaystyle x} , the Kempner function of x {\displaystyle x} is given by the smallest n {\displaystyle n} for which x {\displaystyle x} divides n ! {\displaystyle n!} . For almost all numbers (all but

5977-405: Is equivalent to saying that their intersection is the empty multiset or that their sum equals their union. There is an inclusion–exclusion principle for finite multisets (similar to the one for sets ), stating that a finite union of finite multisets is the difference of two sums of multisets: in the first sum we consider all possible intersections of an odd number of the given multisets, while in

6116-588: Is finite. The empty multiset is the unique multiset with an empty support (underlying set), and thus a cardinality 0. The usual operations of sets may be extended to multisets by using the multiplicity function, in a similar way to using the indicator function for subsets. In the following, A and B are multisets in a given universe U , with multiplicity functions m A {\displaystyle m_{A}} and m B . {\displaystyle m_{B}.} Two multisets are disjoint if their supports are disjoint sets . This

6255-440: Is positive. It can be extended to the non-integer points in the rest of the complex plane by solving for Euler's reflection formula Γ ( z ) Γ ( 1 − z ) = π sin ⁡ π z . {\displaystyle \Gamma (z)\Gamma (1-z)={\frac {\pi }{\sin \pi z}}.} However, this formula cannot be used at integers because, for them,

6394-589: Is standard in French, Romanian, Russian, and Chinese texts). The same number however occurs in many other mathematical contexts, where it is denoted by ( n k ) {\displaystyle {\tbinom {n}{k}}} (often read as " n choose k "); notably it occurs as a coefficient in the binomial formula , hence its name binomial coefficient. One can define ( n k ) {\displaystyle {\tbinom {n}{k}}} for all natural numbers k at once by

6533-2406: Is the value of the multiset coefficient and its equivalencies: ( ( 4 18 ) ) = ( 21 18 ) = 21 ! 18 ! 3 ! = ( 21 3 ) , = 4 ⋅ 5 ⋅ 6 ⋅ 7 ⋅ 8 ⋅ 9 ⋅ 10 ⋅ 11 ⋅ 12 ⋅ 13 ⋅ 14 ⋅ 15 ⋅ 16 ⋅ 17 ⋅ 18 ⋅ 19 ⋅ 20 ⋅ 21 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6 ⋅ 7 ⋅ 8 ⋅ 9 ⋅ 10 ⋅ 11 ⋅ 12 ⋅ 13 ⋅ 14 ⋅ 15 ⋅ 16 ⋅ 17 ⋅ 18 , = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋯ 16 ⋅ 17 ⋅ 18 ⋅ 19 ⋅ 20 ⋅ 21 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋯ 16 ⋅ 17 ⋅ 18 ⋅ 1 ⋅ 2 ⋅ 3 , = 19 ⋅ 20 ⋅ 21 1 ⋅ 2 ⋅ 3 . {\displaystyle {\begin{aligned}\left(\!\!{4 \choose 18}\!\!\right)&={21 \choose 18}={\frac {21!}{18!\,3!}}={21 \choose 3},\\[1ex]&={\frac {{\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}\cdot \mathbf {19\cdot 20\cdot 21} }{\mathbf {1\cdot 2\cdot 3} \cdot {\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}}},\\[1ex]&={\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;19\cdot 20\cdot 21} }{\,1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;1\cdot 2\cdot 3\quad } }},\\[1ex]&={\frac {19\cdot 20\cdot 21}{1\cdot 2\cdot 3}}.\end{aligned}}} From

6672-536: Is to perform the multiplications as a divide-and-conquer algorithm that multiplies a sequence of i {\displaystyle i} numbers by splitting it into two subsequences of i / 2 {\displaystyle i/2} numbers, multiplies each subsequence, and combines the results with one last multiplication. This approach to the factorial takes total time O ( n log 3 ⁡ n ) {\displaystyle O(n\log ^{3}n)} : one logarithm comes from

6811-473: Is usually defined as their multiplicity as roots of the characteristic polynomial . However two other multiplicities are naturally defined for eigenvalues, their multiplicities as roots of the minimal polynomial , and the geometric multiplicity , which is defined as the dimension of the kernel of A − λI (where λ is an eigenvalue of the matrix A ). These three multiplicities define three multisets of eigenvalues, which may be all different: Let A be

6950-1089: Is valid for all complex numbers α and X with | X | < 1 . It can also be interpreted as an identity of formal power series in X , where it actually can serve as definition of arbitrary powers of series with constant coefficient equal to 1; the point is that with this definition all identities hold that one expects for exponentiation , notably ( 1 − X ) − α ( 1 − X ) − β = ( 1 − X ) − ( α + β ) and ( ( 1 − X ) − α ) − β = ( 1 − X ) − ( − α β ) , {\displaystyle (1-X)^{-\alpha }(1-X)^{-\beta }=(1-X)^{-(\alpha +\beta )}\quad {\text{and}}\quad ((1-X)^{-\alpha })^{-\beta }=(1-X)^{-(-\alpha \beta )},} and formulas such as these can be used to prove identities for

7089-574: Is zero when k > n {\displaystyle k>n} . This formula can be derived from the fact that each k -combination of a set S of n members has k ! {\displaystyle k!} permutations so P k n = C k n × k ! {\displaystyle P_{k}^{n}=C_{k}^{n}\times k!} or C k n = P k n / k ! {\displaystyle C_{k}^{n}=P_{k}^{n}/k!} . The set of all k -combinations of

SECTION 50

#1733085348882

7228-967: The ∼ {\displaystyle \sim } symbol means that, as n {\displaystyle n} goes to infinity, the ratio between the left and right sides approaches one in the limit . Stirling's formula provides the first term in an asymptotic series that becomes even more accurate when taken to greater numbers of terms: n ! ∼ 2 π n ( n e ) n ( 1 + 1 12 n + 1 288 n 2 − 139 51840 n 3 − 571 2488320 n 4 + ⋯ ) . {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{12n}}+{\frac {1}{288n^{2}}}-{\frac {139}{51840n^{3}}}-{\frac {571}{2488320n^{4}}}+\cdots \right).} An alternative version uses only odd exponents in

7367-416: The sin ⁡ π z {\displaystyle \sin \pi z} term would produce a division by zero . The result of this extension process is an analytic function , the analytic continuation of the integral formula for the gamma function. It has a nonzero value at all complex numbers, except for the non-positive integers where it has simple poles . Correspondingly, this provides

7506-419: The abc conjecture that there are only finitely many nontrivial examples. The greatest common divisor of the values of a primitive polynomial of degree d {\displaystyle d} over the integers evenly divides d ! {\displaystyle d!} . There are infinitely many ways to extend the factorials to a continuous function . The most widely used of these uses

7645-528: The Sackur–Tetrode equation must correct the count of microstates by dividing by the factorials of the numbers of each type of indistinguishable particle to avoid the Gibbs paradox . Quantum physics provides the underlying reason for why these corrections are necessary. As a function of n {\displaystyle n} , the factorial has faster than exponential growth , but grows more slowly than

7784-467: The Wallis product , which expresses π {\displaystyle \pi } as a limiting ratio of factorials and powers of two. The result of these corrections is Stirling's approximation : n ! ∼ 2 π n ( n e ) n . {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\,.} Here,

7923-428: The X s equal to the unlabeled variable X , so that the product becomes (1 + X ) , the term for each k -combination from S becomes X , so that the coefficient of that power in the result equals the number of such k -combinations. Binomial coefficients can be computed explicitly in various ways. To get all of them for the expansions up to (1 + X ) , one can use (in addition to the basic cases already given)

8062-465: The exponential generating function , which for a combinatorial class with n i {\displaystyle n_{i}} elements of size i {\displaystyle i} is defined as the power series ∑ i = 0 ∞ x i n i i ! . {\displaystyle \sum _{i=0}^{\infty }{\frac {x^{i}n_{i}}{i!}}.} In number theory ,

8201-453: The factorial of n . It is obtained from the previous formula by multiplying denominator and numerator by ( n − k ) !, so it is certainly computationally less efficient than that formula. The last formula can be understood directly, by considering the n ! permutations of all the elements of S . Each such permutation gives a k -combination by selecting its first k elements. There are many duplicate selections: any combined permutation of

8340-459: The gamma function , which can be defined for positive real numbers as the integral Γ ( z ) = ∫ 0 ∞ x z − 1 e − x d x . {\displaystyle \Gamma (z)=\int _{0}^{\infty }x^{z-1}e^{-x}\,dx.} The resulting function is related to the factorial of a non-negative integer n {\displaystyle n} by

8479-530: The gamma function . Adrien-Marie Legendre included Legendre's formula , describing the exponents in the factorization of factorials into prime powers , in an 1808 text on number theory . The notation n ! {\displaystyle n!} for factorials was introduced by the French mathematician Christian Kramp in 1808. Many other notations have also been used. Another later notation | n _ {\displaystyle \vert \!{\underline {\,n}}} , in which

SECTION 60

#1733085348882

8618-408: The permutations – of n {\displaystyle n} distinct objects: there are n ! {\displaystyle n!} . In mathematical analysis , factorials are used in power series for the exponential function and other functions, and they also have applications in algebra , number theory , probability theory , and computer science . Much of the mathematics of

8757-406: The prime number theorem , so the time for the first step is O ( n log 2 ⁡ n ) {\displaystyle O(n\log ^{2}n)} , with one logarithm coming from the divide and conquer and another coming from the multiplication algorithm. In the recursive calls to the algorithm, the prime number theorem can again be invoked to prove that the numbers of bits in

8896-594: The 18 + 4 − 1 characters, and is thus the number of subsets of cardinality 4 − 1 of a set of cardinality 18 + 4 − 1 . Equivalently, it is the number of ways to arrange the 18 dots among the 18 + 4 − 1 characters, which is the number of subsets of cardinality 18 of a set of cardinality 18 + 4 − 1 . This is ( 4 + 18 − 1 4 − 1 ) = ( 4 + 18 − 1 18 ) = 1330 , {\displaystyle {4+18-1 \choose 4-1}={4+18-1 \choose 18}=1330,} thus

9035-413: The 20th century. For example, Hassler Whitney (1933) described generalized sets ("sets" whose characteristic functions may take any integer value: positive, negative or zero). Monro (1987) investigated the category Mul of multisets and their morphisms , defining a multiset as a set with an equivalence relation between elements "of the same sort ", and a morphism between multisets as

9174-418: The analysis of brute-force searches over permutations, factorials arise in the lower bound of log 2 ⁡ n ! = n log 2 ⁡ n − O ( n ) {\displaystyle \log _{2}n!=n\log _{2}n-O(n)} on the number of comparisons needed to comparison sort a set of n {\displaystyle n} items, and in

9313-403: The analysis of chained hash tables , where the distribution of keys per cell can be accurately approximated by a Poisson distribution. Moreover, factorials naturally appear in formulae from quantum and statistical physics , where one often considers all the possible permutations of a set of particles. In statistical mechanics , calculations of entropy such as Boltzmann's entropy formula or

9452-542: The argument of the factorial was half-enclosed by the left and bottom sides of a box, was popular for some time in Britain and America but fell out of use, perhaps because it is difficult to typeset. The word "factorial" (originally French: factorielle ) was first used in 1800 by Louis François Antoine Arbogast , in the first work on Faà di Bruno's formula , but referring to a more general concept of products of arithmetic progressions . The "factors" that this name refers to are

9591-486: The basic cases ( n 0 ) = 1 = ( n n ) {\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}} , these allow successive computation of respectively all numbers of combinations from the same set (a row in Pascal's triangle), of k -combinations of sets of growing sizes, and of combinations with a complement of fixed size n − k . As

9730-407: The case that there are multiple records with name "Sara" in the student table, all of them are shown. That means the result of an SQL query is a multiset; if the result were instead a set, the repetitive records in the result set would have been eliminated. Another application of multisets is in modeling multigraphs . In multigraphs there can be multiple edges between any two given vertices . As such,

9869-730: The chance of drawing any one hand at random is 1 / 2,598,960. The number of k -combinations from a given set S of n elements is often denoted in elementary combinatorics texts by C ( n , k ) {\displaystyle C(n,k)} , or by a variation such as C k n {\displaystyle C_{k}^{n}} , n C k {\displaystyle {}_{n}C_{k}} , n C k {\displaystyle {}^{n}C_{k}} , C n , k {\displaystyle C_{n,k}} or even C n k {\displaystyle C_{n}^{k}} (the last form

10008-432: The coefficients of other Taylor series (in particular those of the trigonometric and hyperbolic functions ), where they cancel factors of n ! {\displaystyle n!} coming from the n {\displaystyle n} th derivative of x n {\displaystyle x^{n}} . This usage of factorials in power series connects back to analytic combinatorics through

10147-400: The complex gamma function and its scalar multiples are the only holomorphic functions on the positive complex half-plane that obey the functional equation and remain bounded for complex numbers with real part between 1 and 2. Other complex functions that interpolate the factorial values include Hadamard's gamma function , which is an entire function over all the complex numbers, including

10286-437: The concept of a set that, unlike a set, allows for multiple instances for each of its elements . The number of instances given for each element is called the multiplicity of that element in the multiset. As a consequence, an infinite number of multisets exist that contain only elements a and b , but vary in the multiplicities of their elements: These objects are all different when viewed as multisets, although they are

10425-437: The concept of multisets predates the coinage of the word multiset by many centuries. Knuth himself attributes the first study of multisets to the Indian mathematician Bhāskarāchārya , who described permutations of multisets around 1150. Other names have been proposed or used for this concept, including list , bunch , bag , heap , sample , weighted set , collection , and suite . Wayne Blizard traced multisets back to

10564-434: The concept of multisets. Athanasius Kircher found the number of multiset permutations when one element can be repeated. Jean Prestet published a general rule for multiset permutations in 1675. John Wallis explained this rule in more detail in 1685. Multisets appeared explicitly in the work of Richard Dedekind . Other mathematicians formalized multisets and began to study them as precise mathematical structures in

10703-459: The construction of Pascal's triangle . For determining an individual binomial coefficient, it is more practical to use the formula ( n k ) = n ( n − 1 ) ( n − 2 ) ⋯ ( n − k + 1 ) k ! . {\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.} The numerator gives

10842-721: The correction terms: n ! ∼ 2 π n ( n e ) n exp ⁡ ( 1 12 n − 1 360 n 3 + 1 1260 n 5 − 1 1680 n 7 + ⋯ ) . {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\exp \left({\frac {1}{12n}}-{\frac {1}{360n^{3}}}+{\frac {1}{1260n^{5}}}-{\frac {1}{1680n^{7}}}+\cdots \right).} Many other variations of these formulas have also been developed, by Srinivasa Ramanujan , Bill Gosper , and others. The binary logarithm of

10981-515: The corresponding products decrease by a constant factor at each level of recursion, so the total time for these steps at all levels of recursion adds in a geometric series to O ( n log 2 ⁡ n ) {\displaystyle O(n\log ^{2}n)} . The time for the squaring in the second step and the multiplication in the third step are again O ( n log 2 ⁡ n ) {\displaystyle O(n\log ^{2}n)} , because each

11120-496: The denominators of power series , most notably in the series for the exponential function , e x = 1 + x 1 + x 2 2 + x 3 6 + ⋯ = ∑ i = 0 ∞ x i i ! , {\displaystyle e^{x}=1+{\frac {x}{1}}+{\frac {x^{2}}{2}}+{\frac {x^{3}}{6}}+\cdots =\sum _{i=0}^{\infty }{\frac {x^{i}}{i!}},} and in

11259-569: The elements of S as types of objects, then we can let x i {\displaystyle x_{i}} denote the number of elements of type i in a multisubset. The number of multisubsets of size k is then the number of nonnegative integer (so allowing zero) solutions of the Diophantine equation : x 1 + x 2 + … + x n = k . {\displaystyle x_{1}+x_{2}+\ldots +x_{n}=k.} If S has n elements,

11398-424: The elements of the multiset are numbers, a confusion is possible with ordinary arithmetic operations ; those normally can be excluded from the context. On the other hand, the latter notation is coherent with the fact that the prime factorization of a positive integer is a uniquely defined multiset, as asserted by the fundamental theorem of arithmetic . Also, a monomial is a multiset of indeterminates ; for example,

11537-464: The elements selected, starting with {0 .. k −1} (zero-based) or {1 .. k } (one-based) as the first allowed k -combination. Then, repeatedly move to the next allowed k -combination by incrementing the smallest index number for which this would not create two equal index numbers, at the same time resetting all smaller index numbers to their initial values. A k - combination with repetitions , or k - multicombination , or multisubset of size k from

11676-407: The entity that specifies the edges is a multiset, and not a set. There are also other applications. For instance, Richard Rado used multisets as a device to investigate the properties of families of sets. He wrote, "The notion of a set takes no account of multiple occurrence of any one of its members, and yet it is just this kind of information that is frequently of importance. We need only think of

11815-471: The equation n ! = Γ ( n + 1 ) , {\displaystyle n!=\Gamma (n+1),} which can be used as a definition of the factorial for non-integer arguments. At all values x {\displaystyle x} for which both Γ ( x ) {\displaystyle \Gamma (x)} and Γ ( x − 1 ) {\displaystyle \Gamma (x-1)} are defined,

11954-505: The expression of binomial coefficients using a falling factorial power: ( n k ) = n k _ k ! . {\displaystyle {n \choose k}={n^{\underline {k}} \over k!}.} For example, there are 4 multisets of cardinality 3 with elements taken from the set {1, 2} of cardinality 2 ( n = 2 , k = 3 ), namely {1, 1, 1} , {1, 1, 2} , {1, 2, 2} , {2, 2, 2} . There are also 4 subsets of cardinality 3 in

12093-420: The factorial function are commonly used as an example of different computer programming styles, and are included in scientific calculators and scientific computing software libraries. Although directly computing large factorials using the product formula or recurrence is not efficient, faster algorithms are known, matching to within a constant factor the time for fast multiplication algorithms for numbers with

12232-407: The factorial function was developed beginning in the late 18th and early 19th centuries. Stirling's approximation provides an accurate approximation to the factorial of large numbers, showing that it grows more quickly than exponential growth . Legendre's formula describes the exponents of the prime numbers in a prime factorization of the factorials, and can be used to count the trailing zeros of

12371-907: The factorial implies that n ! {\displaystyle n!} is divisible by all prime numbers that are at most n {\displaystyle n} , and by no larger prime numbers. More precise information about its divisibility is given by Legendre's formula , which gives the exponent of each prime p {\displaystyle p} in the prime factorization of n ! {\displaystyle n!} as ∑ i = 1 ∞ ⌊ n p i ⌋ = n − s p ( n ) p − 1 . {\displaystyle \sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ={\frac {n-s_{p}(n)}{p-1}}.} Here s p ( n ) {\displaystyle s_{p}(n)} denotes

12510-722: The factorial involves repeated products, rather than a single multiplication, so these time bounds do not apply directly. In this setting, computing n ! {\displaystyle n!} by multiplying the numbers from 1 to n {\displaystyle n} in sequence is inefficient, because it involves n {\displaystyle n} multiplications, a constant fraction of which take time O ( n log 2 ⁡ n ) {\displaystyle O(n\log ^{2}n)} each, giving total time O ( n 2 log 2 ⁡ n ) {\displaystyle O(n^{2}\log ^{2}n)} . A better approach

12649-620: The factorial, used to analyze comparison sorting , can be very accurately estimated using Stirling's approximation. In the formula below, the O ( 1 ) {\displaystyle O(1)} term invokes big O notation . log 2 ⁡ n ! = n log 2 ⁡ n − ( log 2 ⁡ e ) n + 1 2 log 2 ⁡ n + O ( 1 ) . {\displaystyle \log _{2}n!=n\log _{2}n-(\log _{2}e)n+{\frac {1}{2}}\log _{2}n+O(1).} The product formula for

12788-658: The factorials arise through the binomial theorem , which uses binomial coefficients to expand powers of sums. They also occur in the coefficients used to relate certain families of polynomials to each other, for instance in Newton's identities for symmetric polynomials . Their use in counting permutations can also be restated algebraically: the factorials are the orders of finite symmetric groups . In calculus , factorials occur in Faà di Bruno's formula for chaining higher derivatives. In mathematical analysis , factorials frequently appear in

12927-431: The factorials. Daniel Bernoulli and Leonhard Euler interpolated the factorial function to a continuous function of complex numbers , except at the negative integers, the (offset) gamma function . Many other notable functions and number sequences are closely related to the factorials, including the binomial coefficients , double factorials , falling factorials , primorials , and subfactorials . Implementations of

13066-401: The factorization of a binomial coefficient. Grouping the prime factors of the factorial into prime powers in different ways produces the multiplicative partitions of factorials . The special case of Legendre's formula for p = 5 {\displaystyle p=5} gives the number of trailing zeros in the decimal representation of the factorials. According to this formula,

13205-1189: The first k elements among each other, and of the final ( n  −  k ) elements among each other produces the same combination; this explains the division in the formula. From the above formulas follow relations between adjacent numbers in Pascal's triangle in all three directions: ( n k ) = { ( n k − 1 ) n − k + 1 k if  k > 0 ( n − 1 k ) n n − k if  k < n ( n − 1 k − 1 ) n k if  n , k > 0 . {\displaystyle {\binom {n}{k}}={\begin{cases}\displaystyle {\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\\displaystyle {\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\\displaystyle {\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}.} Together with

13344-466: The first results of Paul Erdős , was based on the divisibility properties of factorials. The factorial number system is a mixed radix notation for numbers in which the place values of each digit are factorials. Factorials are used extensively in probability theory , for instance in the Poisson distribution and in the probabilities of random permutations . In computer science , beyond appearing in

13483-962: The first, is based on writing ( n k ) = ( n − 0 ) 1 × ( n − 1 ) 2 × ( n − 2 ) 3 × ⋯ × ( n − ( k − 1 ) ) k , {\displaystyle {n \choose k}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times \cdots \times {\frac {(n-(k-1))}{k}},} which gives ( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2,598,960. {\displaystyle {52 \choose 5}={\frac {52}{1}}\times {\frac {51}{2}}\times {\frac {50}{3}}\times {\frac {49}{4}}\times {\frac {48}{5}}=2{,}598{,}960.} When evaluated in

13622-1707: The following order, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5 , this can be computed using only integer arithmetic. The reason is that when each division occurs, the intermediate result that is produced is itself a binomial coefficient, so no remainders ever occur. Using the symmetric formula in terms of factorials without performing simplifications gives a rather extensive calculation: ( 52 5 ) = n ! k ! ( n − k ) ! = 52 ! 5 ! ( 52 − 5 ) ! = 52 ! 5 ! 47 ! = 80 , 658 , 175 , 170 , 943 , 878 , 571 , 660 , 636 , 856 , 403 , 766 , 975 , 289 , 505 , 440 , 883 , 277 , 824 , 000 , 000 , 000 , 000 120 × 258 , 623 , 241 , 511 , 168 , 180 , 642 , 964 , 355 , 153 , 611 , 979 , 969 , 197 , 632 , 389 , 120 , 000 , 000 , 000 = 2,598,960. {\displaystyle {\begin{aligned}{52 \choose 5}&={\frac {n!}{k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\\[6pt]&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\[6pt]&=2{,}598{,}960.\end{aligned}}} One can enumerate all k -combinations of

13761-1952: The formula in terms of factorials and cancel the factors in the numerator against parts of the factors in the denominator, after which only multiplication of the remaining factors is required: ( 52 5 ) = 52 ! 5 ! 47 ! = 52 × 51 × 50 × 49 × 48 × 47 ! 5 × 4 × 3 × 2 × 1 × 47 ! = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 = ( 26 × 2 ) × ( 17 × 3 ) × ( 10 × 5 ) × 49 × ( 12 × 4 ) 5 × 4 × 3 × 2 = 26 × 17 × 10 × 49 × 12 = 2,598,960. {\displaystyle {\begin{alignedat}{2}{52 \choose 5}&={\frac {52!}{5!47!}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}}{5\times 4\times 3\times 2\times {\cancel {1}}\times {\cancel {47!}}}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\\[5pt]&={\frac {(26\times {\cancel {2}})\times (17\times {\cancel {3}})\times (10\times {\cancel {5}})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}}\times {\cancel {2}}}}\\[5pt]&={26\times 17\times 10\times 49\times 12}\\[5pt]&=2{,}598{,}960.\end{alignedat}}} Another alternative computation, equivalent to

13900-482: The function m by its graph (the set of ordered pairs { ( a , m ( a ) ) : a ∈ A } {\displaystyle \{(a,m(a)):a\in A\}} ) allows for writing the multiset { a , a , b } as {( a , 2), ( b , 1) }, and the multiset { a , b } as {( a , 1), ( b , 1) }. This notation is however not commonly used; more compact notations are employed. If A = {

14039-427: The gamma function obeys the functional equation Γ ( n ) = ( n − 1 ) Γ ( n − 1 ) , {\displaystyle \Gamma (n)=(n-1)\Gamma (n-1),} generalizing the recurrence relation for the factorials. The same integral converges more generally for any complex number z {\displaystyle z} whose real part

14178-405: The illustrations above) or by comparing their largest elements first. The latter option has the advantage that adding a new largest element to S will not change the initial part of the enumeration, but just add the new k -combinations of the larger set after the previous ones. Repeating this process, the enumeration can be extended indefinitely with k -combinations of ever larger sets. If moreover

14317-411: The intervals of the integers are taken to start at 0, then the k -combination at a given place i in the enumeration can be computed easily from i , and the bijection so obtained is known as the combinatorial number system . It is also known as "rank"/"ranking" and "unranking" in computational mathematics. There are many ways to enumerate k combinations. One way is to track k index numbers of

14456-402: The monomial x y corresponds to the multiset { x , x , x , y , y }. A multiset corresponds to an ordinary set if the multiplicity of every element is 1. An indexed family ( a i ) i ∈ I , where i varies over some index set I , may define a multiset, sometimes written { a i } . In this view the underlying set of the multiset is given by the image of the family, and

14595-449: The most salient property of factorials is the divisibility of n ! {\displaystyle n!} by all positive integers up to n {\displaystyle n} , described more precisely for prime factors by Legendre's formula . It follows that arbitrarily large prime numbers can be found as the prime factors of the numbers n ! ± 1 {\displaystyle n!\pm 1} , leading to

14734-586: The multiplicity of any element x is the number of index values i such that a i = x {\displaystyle a_{i}=x} . In this article the multiplicities are considered to be finite, so that no element occurs infinitely many times in the family; even in an infinite multiset, the multiplicities are finite numbers. It is possible to extend the definition of a multiset by allowing multiplicities of individual elements to be infinite cardinals instead of positive integers, but not all properties carry over to this generalization. Elements of

14873-576: The multiset coefficients is very simple, being ∑ d = 0 ∞ ( ( n d ) ) t d = 1 ( 1 − t ) n . {\displaystyle \sum _{d=0}^{\infty }\left(\!\!{n \choose d}\!\!\right)t^{d}={\frac {1}{(1-t)^{n}}}.} As multisets are in one-to-one correspondence with monomials , ( ( n d ) ) {\displaystyle \left(\!\!{n \choose d}\!\!\right)}

15012-804: The multiset coefficients occur. Multiset coefficients should not be confused with the unrelated multinomial coefficients that occur in the multinomial theorem . The value of multiset coefficients can be given explicitly as ( ( n k ) ) = ( n + k − 1 k ) = ( n + k − 1 ) ! k ! ( n − 1 ) ! = n ( n + 1 ) ( n + 2 ) ⋯ ( n + k − 1 ) k ! , {\displaystyle \left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={\frac {(n+k-1)!}{k!\,(n-1)!}}={n(n+1)(n+2)\cdots (n+k-1) \over k!},} where

15151-404: The multiset coefficients. If α is a nonpositive integer n , then all terms with k > − n are zero, and the infinite series becomes a finite sum. However, for other values of α , including positive integers and rational numbers , the series is infinite. Multisets have various applications. They are becoming fundamental in combinatorics . Multisets have become an important tool in

15290-423: The non-positive integers. In the p -adic numbers , it is not possible to continuously interpolate the factorial function directly, because the factorials of large integers (a dense subset of the p -adics) converge to zero according to Legendre's formula, forcing any continuous function that is close to their values to be zero everywhere. Instead, the p -adic gamma function provides a continuous interpolation of

15429-592: The number of k -permutations of n , i.e., of sequences of k distinct elements of S , while the denominator gives the number of such k -permutations that give the same k -combination when the order is ignored. When k exceeds n /2, the above formula contains factors common to the numerator and the denominator, and canceling them out gives the relation ( n k ) = ( n n − k ) , {\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},} for 0 ≤ k ≤ n . This expresses

15568-407: The number of bits in the factorial, a second comes from the multiplication algorithm, and a third comes from the divide and conquer. Even better efficiency is obtained by computing n ! from its prime factorization, based on the principle that exponentiation by squaring is faster than expanding an exponent into a product. An algorithm for this by Arnold Schönhage begins by finding the list of

15707-671: The number of such k -multisubsets is denoted by ( ( n k ) ) , {\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right),} a notation that is analogous to the binomial coefficient which counts k -subsets. This expression, n multichoose k , can also be given in terms of binomial coefficients: ( ( n k ) ) = ( n + k − 1 k ) . {\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}.} This relationship can be easily proved using

15846-460: The number of zeros can be obtained by subtracting the base-5 digits of n {\displaystyle n} from n {\displaystyle n} , and dividing the result by four. Legendre's formula implies that the exponent of the prime p = 2 {\displaystyle p=2} is always larger than the exponent for p = 5 {\displaystyle p=5} , so each factor of five can be paired with

15985-423: The numbers n ! + 2 , n ! + 3 , … n ! + n {\displaystyle n!+2,n!+3,\dots n!+n} must all be composite, proving the existence of arbitrarily large prime gaps . An elementary proof of Bertrand's postulate on the existence of a prime in any interval of the form [ n , 2 n ] {\displaystyle [n,2n]} , one of

16124-454: The permutations of n {\displaystyle n} grouped into subsets with the same numbers of cycles. Another combinatorial application is in counting derangements , permutations that do not leave any element in its original position; the number of derangements of n {\displaystyle n} items is the nearest integer to n ! / e {\displaystyle n!/e} . In algebra ,

16263-458: The primes up to n {\displaystyle n} , for instance using the sieve of Eratosthenes , and uses Legendre's formula to compute the exponent for each prime. Then it computes the product of the prime powers with these exponents, using a recursive algorithm, as follows: The product of all primes up to n {\displaystyle n} is an O ( n ) {\displaystyle O(n)} -bit number, by

16402-864: The product of n {\displaystyle n} with the next smaller factorial: n ! = n × ( n − 1 ) × ( n − 2 ) × ( n − 3 ) × ⋯ × 3 × 2 × 1 = n × ( n − 1 ) ! {\displaystyle {\begin{aligned}n!&=n\times (n-1)\times (n-2)\times (n-3)\times \cdots \times 3\times 2\times 1\\&=n\times (n-1)!\\\end{aligned}}} For example, 5 ! = 5 × 4 ! = 5 × 4 × 3 × 2 × 1 = 120. {\displaystyle 5!=5\times 4!=5\times 4\times 3\times 2\times 1=120.} The value of 0!

16541-949: The product of other factorials: if n {\displaystyle n} is itself any product of factorials, then n ! {\displaystyle n!} equals that same product multiplied by one more factorial, ( n − 1 ) ! {\displaystyle (n-1)!} . The only known examples of factorials that are products of other factorials but are not of this "trivial" form are 9 ! = 7 ! ⋅ 3 ! ⋅ 3 ! ⋅ 2 ! {\displaystyle 9!=7!\cdot 3!\cdot 3!\cdot 2!} , 10 ! = 7 ! ⋅ 6 ! = 7 ! ⋅ 5 ! ⋅ 3 ! {\displaystyle 10!=7!\cdot 6!=7!\cdot 5!\cdot 3!} , and 16 ! = 14 ! ⋅ 5 ! ⋅ 2 ! {\displaystyle 16!=14!\cdot 5!\cdot 2!} . It would follow from

16680-414: The recursion relation ( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) , {\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},} for 0 < k < n , which follows from (1 + X ) = (1 + X )(1 + X ) ; this leads to

16819-782: The recursive version takes linear space to store its call stack . However, this model of computation is only suitable when n {\displaystyle n} is small enough to allow n ! {\displaystyle n!} to fit into a machine word . The values 12! and 20! are the largest factorials that can be stored in, respectively, the 32-bit and 64-bit integers . Floating point can represent larger factorials, but approximately rather than exactly, and will still overflow for factorials larger than 170 ! {\displaystyle 170!} . The exact computation of larger factorials involves arbitrary-precision arithmetic , because of fast growth and integer overflow . Time of computation can be analyzed as

16958-698: The relation ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},} from which it is clear that ( n 0 ) = ( n n ) = 1 , {\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,} and further ( n k ) = 0 {\displaystyle {\binom {n}{k}}=0} for k  >  n . To see that these coefficients count k -combinations from S , one can first consider

17097-1891: The relation between binomial coefficients and multiset coefficients, it follows that the number of multisets of cardinality k in a set of cardinality n can be written ( ( n k ) ) = ( − 1 ) k ( − n k ) . {\displaystyle \left(\!\!{n \choose k}\!\!\right)=(-1)^{k}{-n \choose k}.} Additionally, ( ( n k ) ) = ( ( k + 1 n − 1 ) ) . {\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{k+1 \choose n-1}\!\!\right).} A recurrence relation for multiset coefficients may be given as ( ( n k ) ) = ( ( n k − 1 ) ) + ( ( n − 1 k ) ) for  n , k > 0 {\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right)\quad {\mbox{for }}n,k>0} with ( ( n 0 ) ) = 1 , n ∈ N , and ( ( 0 k ) ) = 0 , k > 0. {\displaystyle \left(\!\!{n \choose 0}\!\!\right)=1,\quad n\in \mathbb {N} ,\quad {\mbox{and}}\quad \left(\!\!{0 \choose k}\!\!\right)=0,\quad k>0.} The above recurrence may be interpreted as follows. Let [ n ] := { 1 , … , n } {\displaystyle [n]:=\{1,\dots ,n\}} be

17236-560: The result (and ignoring the negligible + 1 {\displaystyle +1} term) approximates n ! {\displaystyle n!} as ( n / e ) n {\displaystyle (n/e)^{n}} . More carefully bounding the sum both above and below by an integral, using the trapezoid rule , shows that this estimate needs a correction factor proportional to n {\displaystyle {\sqrt {n}}} . The constant of proportionality for this correction can be found from

17375-417: The same number of digits. The concept of factorials has arisen independently in many cultures: From the late 15th century onward, factorials became the subject of study by Western mathematicians. In a 1494 treatise, Italian mathematician Luca Pacioli calculated factorials up to 11!, in connection with a problem of dining table arrangements. Christopher Clavius discussed factorials in a 1603 commentary on

17514-427: The same number. Thus the multiset of solutions of the equation could be {3, 5} , or it could be {4, 4} . In the latter case it has a solution of multiplicity 2. More generally, the fundamental theorem of algebra asserts that the complex solutions of a polynomial equation of degree d always form a multiset of cardinality d . A special case of the above are the eigenvalues of a matrix , whose multiplicity

17653-416: The same set, since they all consist of the same elements. As with sets, and in contrast to tuples , the order in which elements are listed does not matter in discriminating multisets, so { a , a , b } and { a , b , a } denote the same multiset. To distinguish between sets and multisets, a notation that incorporates square brackets is sometimes used: the multiset { a , a , b } can be denoted by [

17792-650: The second expression is as a binomial coefficient; many authors in fact avoid separate notation and just write binomial coefficients. So, the number of such multisets is the same as the number of subsets of cardinality k of a set of cardinality n + k − 1 . The analogy with binomial coefficients can be stressed by writing the numerator in the above expression as a rising factorial power ( ( n k ) ) = n k ¯ k ! , {\displaystyle \left(\!\!{n \choose k}\!\!\right)={n^{\overline {k}} \over k!},} to match

17931-469: The second sum we consider all possible intersections of an even number of the given multisets. The number of multisets of cardinality k , with elements taken from a finite set of cardinality n , is sometimes called the multiset coefficient or multiset number . This number is written by some authors as ( ( n k ) ) {\displaystyle \textstyle \left(\!\!{n \choose k}\!\!\right)} ,

18070-442: The set {1, 2, 3, 4} of cardinality 4 ( n + k − 1 ), namely {1, 2, 3} , {1, 2, 4} , {1, 3, 4} , {2, 3, 4} . One simple way to prove the equality of multiset coefficients and binomial coefficients given above involves representing multisets in the following way. First, consider the notation for multisets that would represent { a , a , a , a , a , a , b , b , c , c , c , d , d , d , d , d , d , d } (6

18209-413: The set of three fruits was small enough to write a complete list of combinations, this becomes impractical as the size of the set increases. For example, a poker hand can be described as a 5-combination ( k  = 5) of cards from a 52 card deck ( n  = 52). The 5 cards of the hand are all distinct, and the order of cards in the hand does not matter. There are 2,598,960 such combinations, and

18348-509: The source set. There is always exactly one (empty) multiset of size 0, and if n = 0 there are no larger multisets, which gives the initial conditions. Now, consider the case in which n , k > 0 . A multiset of cardinality k with elements from [ n ] might or might not contain any instance of the final element n . If it does appear, then by removing n once, one is left with a multiset of cardinality k − 1 of elements from [ n ] , and every such multiset can arise, which gives

18487-420: The sum of the base - p {\displaystyle p} digits of n {\displaystyle n} , and the exponent given by this formula can also be interpreted in advanced mathematics as the p -adic valuation of the factorial. Applying Legendre's formula to the product formula for binomial coefficients produces Kummer's theorem , a similar result on the exponent of each prime in

18626-736: The terms of the product formula for the factorial. The factorial function of a positive integer n {\displaystyle n} is defined by the product of all positive integers not greater than n {\displaystyle n} n ! = 1 ⋅ 2 ⋅ 3 ⋯ ( n − 2 ) ⋅ ( n − 1 ) ⋅ n . {\displaystyle n!=1\cdot 2\cdot 3\cdots (n-2)\cdot (n-1)\cdot n.} This may be written more concisely in product notation as n ! = ∏ i = 1 n i . {\displaystyle n!=\prod _{i=1}^{n}i.} If this product formula

18765-399: The theory of relational databases , which often uses the synonym bag . For instance, multisets are often used to implement relations in database systems. In particular, a table (without a primary key) works as a multiset, because it can have multiple identical records. Similarly, SQL operates on multisets and returns identical records. For instance, consider "SELECT name from Student". In

18904-480: The unit-cost random-access machine model of computation, in which each arithmetic operation takes constant time and each number uses a constant amount of storage space. In this model, these methods can compute n ! {\displaystyle n!} in time O ( n ) {\displaystyle O(n)} , and the iterative version uses space O ( 1 ) {\displaystyle O(1)} . Unless optimized for tail recursion ,

19043-633: The very origin of numbers, arguing that "in ancient times, the number n was often represented by a collection of n strokes, tally marks , or units." These and similar collections of objects can be regarded as multisets, because strokes, tally marks, or units are considered indistinguishable. This shows that people implicitly used multisets even before mathematics emerged. Practical needs for this structure have caused multisets to be rediscovered several times, appearing in literature under different names. For instance, they were important in early AI languages, such as QA4, where they were referred to as bags,

19182-403: The whole algorithm takes time O ( n log 2 ⁡ n ) {\displaystyle O(n\log ^{2}n)} , proportional to a single multiplication with the same number of bits in its result. Several other integer sequences are similar to or related to the factorials: Multiset In mathematics , a multiset (or bag , or mset ) is a modification of

19321-542: The work of Johannes de Sacrobosco , and in the 1640s, French polymath Marin Mersenne published large (but not entirely correct) tables of factorials, up to 64!, based on the work of Clavius. The power series for the exponential function , with the reciprocals of factorials for its coefficients, was first formulated in 1676 by Isaac Newton in a letter to Gottfried Wilhelm Leibniz . Other important works of early European mathematics on factorials include extensive coverage in

#881118