{{#invoke:Hatnote|hatnote}}
In mathematics, the double factorial of a number Template:Mvar, denoted by Template:Math, is the product of all the positive integers up to Template:Mvar that have the same parity (odd or even) as Template:Mvar.<ref name="callan">Template:Cite arXiv</ref> That is,
<math display="block">n!! = \prod_{k=0}^{\left\lceil\frac{n}{2}\right\rceil - 1} (n-2k) = n (n-2) (n-4) \cdots.</math>
Restated, this says that for even Template:Mvar, the double factorial<ref>Some authors define the double factorial differently for even numbers; see Template:Slink below.</ref> is <math display="block">n!! = \prod_{k=1}^\frac{n}{2} (2k) = n(n-2)(n-4)\cdots 4\cdot 2 \,,</math> while for odd Template:Mvar it is <math display="block">n!! = \prod_{k=1}^\frac{n+1}{2} (2k-1) = n(n-2)(n-4)\cdots 3\cdot 1 \,.</math> For example, Template:Math. The zero double factorial Template:Math as an empty product.<ref name=":0">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
The sequence of double factorials for even Template:Mvar = Template:Math starts as Template:Block indent The sequence of double factorials for odd Template:Mvar = Template:Math starts as Template:Block indent
The term odd factorial is sometimes used for the double factorial of an odd number.<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref>
The term semifactorial is also used by Knuth as a synonym of double factorial.<ref>Template:Cite book</ref>
History and usageEdit
In a 1902 paper, the physicist Arthur Schuster wrote:<ref>Template:Cite journal See in particular p. 99.</ref> Template:Quote
Template:Harvtxt<ref name="meserve">Template:Cite journal</ref> states that the double factorial was originally introduced in order to simplify the expression of certain trigonometric integrals that arise in the derivation of the Wallis product. Double factorials also arise in expressing the volume of a hyperball and surface area of a hypersphere, and they have many applications in enumerative combinatorics.<ref name="callan"/><ref name="dm93"/> They occur in [[Student's t-distribution|Student's Template:Mvar-distribution]] (1908), though Gosset did not use the double exclamation point notation.
Relation to the factorialEdit
Because the double factorial only involves about half the factors of the ordinary factorial, its value is not substantially larger than the square root of the factorial Template:Math, and it is much smaller than the iterated factorial Template:Math.
The factorial of a positive Template:Mvar may be written as the product of two double factorials:<ref name=":0" /> <math display="block">n! = n!! \cdot (n-1)!!\,,</math> and therefore <math display="block">n!! = \frac{n!}{(n-1)!!} = \frac{(n+1)!}{(n+1)!!}\,,</math> where the denominator cancels the unwanted factors in the numerator. (The last form also applies when Template:Math.)
For an even non-negative integer Template:Math with Template:Math, the double factorial may be expressed as <math display="block">(2k)!! = 2^k k!\,.</math>
For odd Template:Math with Template:Math, combining the two previous formulas yields <math display="block">(2k-1)!! = \frac{(2k)!}{2^k k!} = \frac{(2k-1)!}{2^{k-1} (k-1)!}\,.</math>
For an odd positive integer Template:Math with Template:Math, the double factorial may be expressed in terms of [[Permutation#Permutations without repetitions|Template:Mvar-permutations of Template:Math]]<ref name="callan"/><ref name="gq12">Template:Cite journal</ref> or a falling factorial as <math display="block">(2k-1)!! = \frac {_{2k}P_k} {2^k} = \frac {(2k)^{\underline k}} {2^k}\,.</math>
Applications in enumerative combinatoricsEdit
Double factorials are motivated by the fact that they occur frequently in enumerative combinatorics and other settings. For instance, Template:Math for odd values of Template:Mvar counts
- Perfect matchings of the complete graph Template:Math for odd Template:Mvar. In such a graph, any single vertex v has Template:Mvar possible choices of vertex that it can be matched to, and once this choice is made the remaining problem is one of selecting a perfect matching in a complete graph with two fewer vertices. For instance, a complete graph with four vertices a, b, c, and d has three perfect matchings: ab and cd, ac and bd, and ad and bc.<ref name="callan"/> Perfect matchings may be described in several other equivalent ways, including involutions without fixed points on a set of Template:Math items (permutations in which each cycle is a pair)<ref name="callan"/> or chord diagrams (sets of chords of a set of Template:Math points evenly spaced on a circle such that each point is the endpoint of exactly one chord, also called Brauer diagrams).<ref name="dm93"/><ref>Template:Cite book</ref><ref>Template:Cite journal</ref> The numbers of matchings in complete graphs, without constraining the matchings to be perfect, are instead given by the telephone numbers, which may be expressed as a summation involving double factorials.<ref>Template:Cite journal</ref>
- Stirling permutations, permutations of the multiset of numbers Template:Math in which each pair of equal numbers is separated only by larger numbers, where Template:Math. The two copies of Template:Mvar must be adjacent; removing them from the permutation leaves a permutation in which the maximum element is Template:Math, with Template:Mvar positions into which the adjacent pair of Template:Mvar values may be placed. From this recursive construction, a proof that the Stirling permutations are counted by the double permutations follows by induction.<ref name="callan"/> Alternatively, instead of the restriction that values between a pair may be larger than it, one may also consider the permutations of this multiset in which the first copies of each pair appear in sorted order; such a permutation defines a matching on the Template:Math positions of the permutation, so again the number of permutations may be counted by the double permutations.<ref name="dm93">Template:Cite journal</ref>
- Heap-ordered trees, trees with Template:Math nodes labeled Template:Math, such that the root of the tree has label 0, each other node has a larger label than its parent, and such that the children of each node have a fixed ordering. An Euler tour of the tree (with doubled edges) gives a Stirling permutation, and every Stirling permutation represents a tree in this way.<ref name="callan"/><ref>Template:Cite conference</ref>
- Unrooted binary trees with Template:Math labeled leaves. Each such tree may be formed from a tree with one fewer leaf, by subdividing one of the Template:Mvar tree edges and making the new vertex be the parent of a new leaf.
- Rooted binary trees with Template:Math labeled leaves. This case is similar to the unrooted case, but the number of edges that can be subdivided is even, and in addition to subdividing an edge it is possible to add a node to a tree with one fewer leaf by adding a new root whose two children are the smaller tree and the new leaf.<ref name="callan"/><ref name="dm93"/>
Template:Harvtxt and Template:Harvtxt list several additional objects with the same counting sequence, including "trapezoidal words" (numerals in a mixed radix system with increasing odd radixes), height-labeled Dyck paths, height-labeled ordered trees, "overhang paths", and certain vectors describing the lowest-numbered leaf descendant of each node in a rooted binary tree. For bijective proofs that some of these objects are equinumerous, see Template:Harvtxt and Template:Harvtxt.<ref>Template:Cite conference</ref><ref>Template:Cite journal</ref>
The even double factorials give the numbers of elements of the hyperoctahedral groups (signed permutations or symmetries of a hypercube)
AsymptoticsEdit
Stirling's approximation for the factorial can be used to derive an asymptotic equivalent for the double factorial. In particular, since <math>n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n,</math> one has as <math>n</math> tends to infinity that
<math display=block>n!! \sim \begin{cases} \displaystyle \sqrt{\pi n}\left(\frac{n}{e}\right)^{n/2} & \text{if } n \text{ is even}, \\[5pt] \displaystyle \sqrt{2 n}\left(\frac{n}{e}\right)^{n/2} & \text{if } n \text{ is odd}. \end{cases}</math>
ExtensionsEdit
Negative argumentsEdit
The ordinary factorial, when extended to the gamma function, has a pole at each negative integer, preventing the factorial from being defined at these numbers. However, the double factorial of odd numbers may be extended to any negative odd integer argument by inverting its recurrence relation <math display="block">n!! = n \times (n-2)!!</math> to give <math display="block">n!! = \frac{(n+2)!!}{n+2}\,.</math> Using this inverted recurrence, (−1)!! = 1, (−3)!! = −1, and (−5)!! = Template:Sfrac; negative odd numbers with greater magnitude have fractional double factorials.<ref name="callan"/> In particular, when Template:Mvar is an odd number, this gives <math display="block">(-n)!! \times n!! = (-1)^\frac{n-1}{2} \times n\,.</math>
Complex argumentsEdit
Disregarding the above definition of Template:Math for even values of Template:Mvar, the double factorial for odd integers can be extended to most real and complex numbers Template:Mvar by noting that when Template:Mvar is a positive odd integer then<ref>Template:Cite book</ref><ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
<math display="block">\begin{align} z!! &= z(z-2)\cdots 5 \cdot 3 \\[3mu] &= 2^\frac{z-1}{2}\left(\frac z2\right)\left(\frac{z-2}2\right)\cdots \left(\frac{5}{2}\right) \left(\frac{3}{2}\right) \\[5mu] &= 2^\frac{z-1}{2} \frac{\Gamma\left(\tfrac z2+1\right)}{\Gamma\left(\tfrac12+1\right)} \\[5mu] &= \sqrt{\frac{2}{\pi}} 2^\frac{z}{2} \Gamma\left(\tfrac z2+1\right) \,,\end{align}</math> where <math>\Gamma(z)</math> is the gamma function.
The final expression is defined for all complex numbers except the negative even integers and satisfies Template:Math everywhere it is defined. As with the gamma function that extends the ordinary factorial function, this double factorial function is logarithmically convex in the sense of the Bohr–Mollerup theorem. Asymptotically, <math display=inline>n!! \sim \sqrt{2 n^{n+1} e^{-n}}\,.</math>
The generalized formula <math>\sqrt{\frac{2}{\pi}} 2^\frac{z}{2} \Gamma\left(\tfrac z2+1\right)</math> does not agree with the previous product formula for Template:Math for non-negative even integer values of Template:Mvar. Instead, this generalized formula implies the following alternative: <math display="block">(2k)!! = \sqrt{\frac{2}{\pi}} 2^k \Gamma\left(k+1\right) = \sqrt{ \frac{2}{\pi} } \prod_{i=1}^k (2i) \,,</math> with the value for 0!! in this case being Template:Startplainlist
- <math>0!! = \sqrt{ \frac{2}{\pi} } \approx 0.797\,884\,5608\dots</math> (sequence A076668 in the OEIS).
Using this generalized formula as the definition, the volume of an Template:Mvar-dimensional hypersphere of radius Template:Mvar can be expressed as<ref>Template:Cite journal</ref>
<math display="block">V_n=\frac{2 \left(2\pi\right)^\frac{n-1}{2}}{n!!} R^n\,.</math>
Additional identitiesEdit
For integer values of Template:Mvar, <math display="block">\int_{0}^\frac{\pi}{2}\sin^n x\,dx=\int_{0}^\frac{\pi}{2}\cos^n x\,dx=\frac{(n-1)!!}{n!!}\times \begin{cases}1 & \text{if } n \text{ is odd} \\ \frac{\pi}{2} & \text{if } n \text{ is even.}\end{cases}</math> Using instead the extension of the double factorial of odd numbers to complex numbers, the formula is <math display="block">\int_{0}^\frac{\pi}{2}\sin^n x\,dx=\int_{0}^\frac{\pi}{2}\cos^n x\,dx=\frac{(n-1)!!}{n!!} \sqrt{\frac{\pi}{2}}\,.</math>
Double factorials can also be used to evaluate integrals of more complicated trigonometric polynomials.<ref name="meserve"/><ref>Template:Cite journal</ref>
Double factorials of odd numbers are related to the gamma function by the identity:
<math display="block">(2n-1)!! = 2^n \cdot \frac{\Gamma\left(\frac{1}{2} + n\right)} {\sqrt{\pi}} = (-2)^n \cdot \frac{\sqrt{\pi}} { \Gamma\left(\frac{1}{2} - n\right)}\,.</math>
Some additional identities involving double factorials of odd numbers are:<ref name="callan"/>
<math display="block">\begin{align} (2n-1)!! &= \sum_{k=0}^{n-1} \binom{n}{k+1} (2k-1)!! (2n-2k-3)!! \\
&= \sum_{k=1}^{n} \binom{n}{k} (2k-3)!! (2(n-k)-1)!! \\
&= \sum_{k=0}^{n} \binom{2n-k-1}{k-1} \frac{(2k-1)(2n-k+1)}{k+1}(2n-2k-3)!! \\
&= \sum_{k=1}^{n} \frac{(n-1)!}{(k-1)!} k(2k-3)!!\,.
\end{align}</math>
An approximation for the ratio of the double factorial of two consecutive integers is <math display="block"> \frac{(2n)!!}{(2n-1)!!} \approx \sqrt{\pi n}. </math> This approximation gets more accurate as Template:Mvar increases, which can be seen as a result of the Wallis Integral.
GeneralizationsEdit
DefinitionsEdit
In the same way that the double factorial generalizes the notion of the single factorial, the following definition of the integer-valued multiple factorial functions (multifactorials), or Template:Mvar-factorial functions, extends the notion of the double factorial function for positive integers <math>\alpha</math>:
<math display="block"> n!_{(\alpha)} = \begin{cases}
n \cdot (n-\alpha)!_{(\alpha)} & \text{ if } n > \alpha \,; \\
n & \text{ if } 1 \leq n \leq \alpha \,; \text{and} \\
(n+\alpha)!_{(\alpha)} / (n+\alpha) & \text{ if } n \leq 0 \text{ and is not a negative multiple of } \alpha \,;
\end{cases} </math>
Alternative extension of the multifactorialEdit
Alternatively, the multifactorial Template:Math can be extended to most real and complex numbers Template:Mvar by noting that when Template:Mvar is one more than a positive multiple of the positive integer Template:Mvar then
<math display="block">\begin{align} z!_{(\alpha)} &= z(z-\alpha)\cdots (\alpha+1) \\ &= \alpha^\frac{z-1}{\alpha}\left(\frac{z}{\alpha}\right)\left(\frac{z-\alpha}{\alpha}\right)\cdots \left(\frac{\alpha+1}{\alpha}\right) \\ &= \alpha^\frac{z-1}{\alpha} \frac{\Gamma\left(\frac{z}{\alpha}+1\right)}{\Gamma\left(\frac{1}{\alpha}+1\right)}\,. \end{align}</math>
This last expression is defined much more broadly than the original. In the same way that Template:Math is not defined for negative integers, and Template:Math is not defined for negative even integers, Template:Math is not defined for negative multiples of Template:Mvar. However, it is defined and satisfies Template:Math for all other complex numbers Template:Mvar. This definition is consistent with the earlier definition only for those integers Template:Mvar satisfying Template:Math.
In addition to extending Template:Math to most complex numbers Template:Mvar, this definition has the feature of working for all positive real values of Template:Mvar. Furthermore, when Template:Math, this definition is mathematically equivalent to the Template:Math function, described above. Also, when Template:Math, this definition is mathematically equivalent to the alternative extension of the double factorial.
Generalized Stirling numbers expanding the multifactorial functionsEdit
A class of generalized Stirling numbers of the first kind is defined for Template:Math by the following triangular recurrence relation:
<math display="block">\left[\begin{matrix} n \\ k \end{matrix} \right]_{\alpha}
= (\alpha n+1-2\alpha) \left[\begin{matrix} n-1 \\ k \end{matrix} \right]_{\alpha} + \left[\begin{matrix} n-1 \\ k-1 \end{matrix} \right]_{\alpha} + \delta_{n,0} \delta_{k,0}\,.
</math>
These generalized Template:Mvar-factorial coefficients then generate the distinct symbolic polynomial products defining the multiple factorial, or Template:Mvar-factorial functions, Template:Math, as
<math display="block"> \begin{align} (x-1|\alpha)^{\underline{n}} & := \prod_{i=0}^{n-1} \left(x-1-i\alpha\right) \\ & = (x-1)(x-1-\alpha)\cdots\bigl(x-1-(n-1)\alpha\bigr) \\ & = \sum_{k=0}^n \left[\begin{matrix} n \\ k \end{matrix} \right] (-\alpha)^{n-k} (x-1)^k \\ & = \sum_{k=1}^n \left[\begin{matrix} n \\ k \end{matrix} \right]_{\alpha} (-1)^{n-k} x^{k-1}\,. \end{align} </math>
The distinct polynomial expansions in the previous equations actually define the Template:Mvar-factorial products for multiple distinct cases of the least residues Template:Math for Template:Math.
The generalized Template:Mvar-factorial polynomials, Template:Math where Template:Math, which generalize the Stirling convolution polynomials from the single factorial case to the multifactorial cases, are defined by
<math display="block">\sigma_n^{(\alpha)}(x) := \left[\begin{matrix} x \\ x-n \end{matrix} \right]_{(\alpha)} \frac{(x-n-1)!}{x!}</math>
for Template:Math. These polynomials have a particularly nice closed-form ordinary generating function given by
<math display="block">\sum_{n \geq 0} x \cdot \sigma_n^{(\alpha)}(x) z^n = e^{(1-\alpha)z} \left(\frac{\alpha z e^{\alpha z}}{e^{\alpha z}-1}\right)^x\,. </math>
Other combinatorial properties and expansions of these generalized Template:Mvar-factorial triangles and polynomial sequences are considered in Template:Harvtxt.<ref>Template:Cite journal</ref>
Exact finite sums involving multiple factorial functionsEdit
Suppose that Template:Math and Template:Math are integer-valued. Then we can expand the next single finite sums involving the multifactorial, or Template:Mvar-factorial functions, Template:Math, in terms of the Pochhammer symbol and the generalized, rational-valued binomial coefficients as
<math display="block"> \begin{align} (\alpha n-1)!_{(\alpha)} & = \sum_{k=0}^{n-1} \binom{n-1}{k+1} (-1)^k \times \left(\frac{1}{\alpha}\right)_{-(k+1)} \left(\frac{1}{\alpha}-n\right)_{k+1} \times \bigl(\alpha(k+1)-1\bigr)!_{(\alpha)} \bigl(\alpha(n-k-1)-1\bigr)!_{(\alpha)} \\ & = \sum_{k=0}^{n-1} \binom{n-1}{k+1} (-1)^k \times \binom{\frac{1}{\alpha}+k-n}{k+1} \binom{\frac{1}{\alpha}-1}{k+1} \times \bigl(\alpha(k+1)-1\bigr)!_{(\alpha)} \bigl(\alpha(n-k-1)-1\bigr)!_{(\alpha)}\,, \end{align} </math>
and moreover, we similarly have double sum expansions of these functions given by
<math display="block"> \begin{align} (\alpha n-1)!_{(\alpha)} & = \sum_{k=0}^{n-1} \sum_{i=0}^{k+1} \binom{n-1}{k+1} \binom{k+1}{i} (-1)^k \alpha^{k+1-i} (\alpha i-1)!_{(\alpha)} \bigl(\alpha(n-1-k)-1\bigr)!_{(\alpha)} \times (n-1-k)_{k+1-i} \\ & = \sum_{k=0}^{n-1} \sum_{i=0}^{k+1} \binom{n-1}{k+1} \binom{k+1}{i} \binom{n-1-i}{k+1-i} (-1)^k \alpha^{k+1-i} (\alpha i-1)!_{(\alpha)} \bigl(\alpha(n-1-k)-1\bigr)!_{(\alpha)} \times (k+1-i)!. \end{align} </math>
The first two sums above are similar in form to a known non-round combinatorial identity for the double factorial function when Template:Math given by Template:Harvtxt.
<math display="block">(2n-1)!! = \sum_{k=0}^{n-1} \binom{n}{k+1} (2k-1)!! (2n-2k-3)!!.</math>
Similar identities can be obtained via context-free grammars.<ref>Template:Cite journal</ref> Additional finite sum expansions of congruences for the Template:Mvar-factorial functions, Template:Math, modulo any prescribed integer Template:Math for any Template:Math are given by Template:Harvtxt.<ref>Template:Cite journal</ref>