Double factorial

thumb|360px|The fifteen different [[Chord diagram (mathematics)|chord diagrams on six points, or equivalently the fifteen different perfect matchings on a six-vertex complete graph. These are counted by the double factorial .]]

In mathematics, the double factorial, or semifactorial, of a positive integer is the product of all the positive integers up to that have the same parity (odd or even) as . 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 , the double factorial 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 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>

A few examples are:

Often, both and are considered empty products that evaluate to 1.

The sequence of double factorials for even = starts as

The sequence of double factorials for odd = starts as

The term odd factorial is sometimes used for the double factorial of an odd number.

<!--

The odd factorial of n is defined to be the product of all odd positive integers up to n, that is, n‼ if n is odd and (n−1)‼ if n is even.

-->

There is another definition of double factorial, which can be evaluated for most complex numbers; see below.

History and usage

In a 1902 paper, the physicist Arthur Schuster wrote:

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. 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.

Stirling permutations, permutations of the multiset of numbers in which each pair of equal numbers is separated only by larger numbers, where . The two copies of must be adjacent; removing them from the permutation leaves a permutation in which the maximum element is , with positions into which the adjacent pair of values may be placed. From this recursive construction, a proof that the Stirling permutations are counted by the double permutations follows by induction.
Heap-ordered trees, trees with nodes labeled , 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.
Unrooted binary trees with labeled leaves. Each such tree may be formed from a tree with one fewer leaf, by subdividing one of the tree edges and making the new vertex be the parent of a new leaf.
Rooted binary trees with 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.

The even double factorials give the numbers of elements of the hyperoctahedral groups (signed permutations or symmetries of a hypercube)

Asymptotics

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>

Extensions

Negative arguments

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

Using this inverted recurrence, , , and ; negative odd numbers with greater magnitude have fractional double factorials.

<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 its reciprocal is well defined for all complex numbers. This double factorial satisfies 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 for non-negative even integer values of . 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

<math>0!! = \sqrt{ \frac{2}{\pi} } \approx 0.797\,884\,5608\dots</math> .

Using this generalized formula as the definition, the volume of an -dimensional hypersphere of radius can be expressed as

<math display="block">V_n=\frac{2 \left(2\pi\right)^\frac{n-1}{2{n!!} R^n\,,</math>

regardless of whether is even or odd.

Additional identities

For integer values of ,

<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

Double factorials can also be used to evaluate integrals of more complicated trigonometric polynomials.

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:

Exact finite sums involving multiple factorial functions

Suppose that and are integer-valued. Then we can expand the next single finite sums involving the multifactorial, or -factorial functions, , in terms of the Pochhammer symbol and the generalized, rational-valued binomial coefficients as

\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

\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 given by .

<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. Additional finite sum expansions of congruences for the -factorial functions, , modulo any prescribed integer for any are given by .

References

fr:Analogues de la factorielle#Multifactorielles

de:Doppelfakultät