Double factorial explained

In mathematics, the double factorial of a number, denoted by, is the product of all the positive integers up to that have the same parity (odd or even) as .^[1] That is,

$$n!!\; =\; \backslash prod\_^\; (n-2k)\; =\; n\; (n-2)\; (n-4)\; \backslash cdots.$$

Restated, this says that for even, the double factorial^[2] is$$n!!\; =\; \backslash prod\_^\backslash frac\; (2k)\; =\; n(n-2)(n-4)\backslash cdots\; 4\backslash cdot\; 2\; \backslash ,,$$while for odd it is$$n!!\; =\; \backslash prod\_^\backslash frac\; (2k-1)\; =\; n(n-2)(n-4)\backslash cdots\; 3\backslash cdot\; 1\; \backslash ,.$$For example, . The zero double factorial as an empty product.^{[3] [4]}

The sequence of double factorials for even = starts asThe sequence of double factorials for odd = starts as

The term odd factorial is sometimes used for the double factorial of an odd number.^{[5] [6]}

The term semifactorial is also used by Knuth as a synonym of double factorial.^[7]

History and usage

In a 1902 paper, the physicist Arthur Schuster wrote:^[8]

^[9] 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 hypersphere, and they have many applications in enumerative combinatorics.^[1] They occur in Student's -distribution (1908), though Gosset did not use the double exclamation point notation.

Relation to the factorial

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, and it is much smaller than the iterated factorial .

The factorial of a positive may be written as the product of two double factorials:$$n!\; =\; n!!\; \backslash cdot\; (n-1)!!\backslash ,,$$and therefore$$n!!\; =\; \backslash frac\; =\; \backslash frac\backslash ,,$$where the denominator cancels the unwanted factors in the numerator. (The last form also applies when .)

For an even non-negative integer with, the double factorial may be expressed as$$(2k)!!\; =\; 2^k\; k!\backslash ,.$$

For odd with, combining the two previous formulas yields$$(2k-1)!!\; =\; \backslash frac\; =\; \backslash frac\backslash ,.$$

For an odd positive integer with, the double factorial may be expressed in terms of -permutations of ^{[1] [10]} or a falling factorial as$$(2k-1)!!\; =\; \backslash frac\; =\; \backslash frac\; \backslash ,.$$

Applications in enumerative combinatorics

Double factorials are motivated by the fact that they occur frequently in enumerative combinatorics and other settings. For instance, for odd values of counts

• Perfect matchings of the complete graph for odd . In such a graph, any single vertex v has 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.^[1] Perfect matchings may be described in several other equivalent ways, including involutions without fixed points on a set of items (permutations in which each cycle is a pair)^[1] or chord diagrams (sets of chords of a set of points evenly spaced on a circle such that each point is the endpoint of exactly one chord, also called Brauer diagrams).^{[11] [12]} 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.^[13]
• 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.^[1] 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 positions of the permutation, so again the number of permutations may be counted by the double permutations.^[14]
• 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.^{[1] [15]}
• 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.^{[1] [14]}

and 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 and .^{[16] [17]}

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

n! \sim \sqrt{ 2 \pi n}\left( (n)/(e) \right) ^{n,} one has as n tends to infinity that

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$$n!!\; =\; n\; \backslash times\; (n-2)!!$$to give$$n!!\; =\; \backslash frac\backslash ,.$$Using this inverted recurrence, (−1)!! = 1, (−3)!! = −1, and (−5)!! = ; negative odd numbers with greater magnitude have fractional double factorials.^[1] In particular, when is an odd number, this gives$$(-n)!!\; \backslash times\; n!!\; =\; (-1)^\backslash frac\; \backslash times\; n\backslash ,.$$

Complex arguments

Disregarding the above definition of for even values of , the double factorial for odd integers can be extended to most real and complex numbers by noting that when is a positive odd integer then^{[18] [19]}

where

\Gamma(z) is the gamma function.

The final expression is defined for all complex numbers except the negative even integers and 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, $n!!\; \backslash sim\; \backslash sqrt\backslash ,.$

The generalized formula

\sqrt{ (2)/(\pi) } 2^\frac \Gamma\left(\tfrac z2+1\right) does not agree with the previous product formula for for non-negative even integer values of . Instead, this generalized formula implies the following alternative:$$(2k)!!\; =\; \backslash sqrt\; 2^k\; \backslash Gamma\backslash left(k+1\backslash right)\; =\; \backslash sqrt\; \backslash prod\_^k\; (2i)\; \backslash ,,$$with the value for 0!! in this case being0 !! = \sqrt{ (2)/(\pi) } ≈ 0 . 7978845608... .

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

$$V\_n=\backslash frac\; R^n\backslash ,.$$

Additional identities

For integer values of,Using instead the extension of the double factorial of odd numbers to complex numbers, the formula is$$\backslash int\_^\backslash frac\backslash sin^n\; x\backslash ,dx=\backslash int\_^\backslash frac\backslash cos^n\; x\backslash ,dx=\backslash frac\; \backslash sqrt\backslash ,.$$

Double factorials can also be used to evaluate integrals of more complicated trigonometric polynomials.^{[9] [21]}

Double factorials of odd numbers are related to the gamma function by the identity:

$$(2n-1)!!\; =\; 2^n\; \backslash cdot\; \backslash frac\; =\; (-2)^n\; \backslash cdot\; \backslash frac\; \backslash ,.$$

Some additional identities involving double factorials of odd numbers are:^[1]

An approximation for the ratio of the double factorial of two consecutive integers is$$\backslash frac\; \backslash approx\; \backslash sqrt.$$This approximation gets more accurate as increases, which can be seen as a result of the Wallis Integral.

Generalizations

Definitions

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 -factorial functions, extends the notion of the double factorial function for positive integers

\alpha :

Alternative extension of the multifactorial

Alternatively, the multifactorial can be extended to most real and complex numbers by noting that when is one more than a positive multiple of the positive integer then

This last expression is defined much more broadly than the original. In the same way that is not defined for negative integers, and is not defined for negative even integers, is not defined for negative multiples of . However, it is defined for and satisfies for all other complex numbers . This definition is consistent with the earlier definition only for those integers satisfying .

In addition to extending to most complex numbers , this definition has the feature of working for all positive real values of . Furthermore, when, this definition is mathematically equivalent to the function, described above. Also, when, this definition is mathematically equivalent to the alternative extension of the double factorial.

Generalized Stirling numbers expanding the multifactorial functions

A class of generalized Stirling numbers of the first kind is defined for by the following triangular recurrence relation:

$$\backslash left[\backslash begin\{matrix\}\; n\; \backslash \backslash \; k\; \backslash end\{matrix\}\; \backslash right]\_\; =\; (\backslash alpha\; n+1-2\backslash alpha)\; \backslash left[\backslash begin\{matrix\}\; n-1\; \backslash \backslash \; k\; \backslash end\{matrix\}\; \backslash right]\_\; +\; \backslash left[\backslash begin\{matrix\}\; n-1\; \backslash \backslash \; k-1\; \backslash end\{matrix\}\; \backslash right]\_\; +\; \backslash delta\_\; \backslash delta\_\backslash ,.$$

These generalized -factorial coefficients then generate the distinct symbolic polynomial products defining the multiple factorial, or -factorial functions,, as

The distinct polynomial expansions in the previous equations actually define the -factorial products for multiple distinct cases of the least residues for

Notes and References

1. A combinatorial survey of identities for the double factorial. David. Callan. 0906.1317. 2009. math.CO.
2. Some authors define the double factorial differently for even numbers; see below.
3. Web site: Weisstein. Eric W.. Double Factorial. 2020-09-10. mathworld.wolfram.com. en.
4. Web site: Double Factorials and Multifactorials Brilliant Math & Science Wiki. 2020-09-10. brilliant.org. en-us.
5. Henderson . Daniel J. . Parmeter . Christopher F. . 10.1016/j.spl.2012.03.013 . 7 . Statistics & Probability Letters . 2929790 . 1383–1387 . Canonical higher-order kernels for density derivative estimation . 82 . 2012.
6. Nielsen . B. . 10.1093/biomet/86.2.279 . 2 . Biometrika . 1705359 . 279–288 . The likelihood-ratio test for rank in bivariate canonical correlation analysis . 86 . 1999.
7. Book: Knuth, Donald Ervin . Donald Knuth

   . Donald Knuth . The art of computer programming. volume 4B part 2: Combinatorial algorithms . 2023 . Addison-Wesley . 978-0-201-03806-4 . Boston Munich.

8. Schuster . Arthur . 10.1098/rspl.1902.0068 . free . Proceedings of the Royal Society of London . 116355 . 97–101 . On some definite integrals and a new method of reducing a function of spherical co-ordinates to a series of spherical harmonics . 71 . 1902. 467–476 . See in particular p. 99.
9. Meserve . B. E. . 10.2307/2306136 . 7 . . 1527019 . 425–426 . Classroom Notes: Double Factorials . 55 . 1948. 2306136 .
10. Gould . Henry . Quaintance . Jocelyn . 10.4169/math.mag.85.3.177 . 3 . . 2924154 . 177–192 . Double fun with double factorials . 85 . 2012. 117120280 .
11. Book: Kitaev, Sergey. Patterns in Permutations and Words. EATCS Monographs in Theoretical Computer Science . Sergey Kitaev. Springer. 2011. 9783642173332. 96.
12. Dale . M. R. T. . Narayana . T. V. . 10.1016/0378-3758(86)90161-8 . 2 . Journal of Statistical Planning and Inference . 852528 . 245–249 . A partition of Catalan permuted sequences with applications . 14 . 1986.
13. Tichy . Robert F. . Wagner . Stephan . 10.1089/cmb.2005.12.1004 . 7 . . 1004–1013 . Extremal problems for topological indices in combinatorial chemistry . 12 . 2005. 16201918.
14. Dale . M. R. T. . Moon . J. W. . 10.1016/0378-3758(93)90035-5 . 1 . Journal of Statistical Planning and Inference . 1209991 . 75–87 . The permuted analogues of three Catalan sets . 34 . 1993.
15. Janson . Svante . Svante Janson . 0803.1129 . Plane recursive trees, Stirling permutations and an urn model . 2508813 . 541–547 . Assoc. Discrete Math. Theor. Comput. Sci., Nancy . Discrete Math. Theor. Comput. Sci. Proc., AI . Fifth Colloquium on Mathematics and Computer Science . 2008. 2008arXiv0803.1129J.
16. Rubey . Martin . Nestings of matchings and permutations and north steps in PDSAWs . 2721495 . 691–704 . Assoc. Discrete Math. Theor. Comput. Sci., Nancy . Discrete Math. Theor. Comput. Sci. Proc., AJ . 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) . 2008.
17. Marsh . Robert J. . Martin . Paul . 0906.0912 . 10.1007/s10801-010-0252-6 . 3 . . 2772541 . 427–453 . Tiling bijections between paths and Brauer diagrams . 33 . 2011. 7264692 .
18. Book: Hassani, Sadri. Mathematical Methods: For Students of Physics and Related Fields. Undergraduate Texts in Mathematics. Springer. 2000. 9780387989587. 266.
19. Web site: Double factorial: Specific values (formula 06.02.03.0005) . Wolfram Research. 2001-10-29 . 2013-03-23.
20. Some dimension problems in molecular databases. Paul G.. Mezey. 2009. Journal of Mathematical Chemistry. 45. 1. 1–6. 10.1007/s10910-008-9365-8. 120103389.
21. Dassios . George . George Dassios . Kiriaki . Kiriakie . A . Bulletin de la Société Mathématique de Grèce . 935868 . 40–43 . A useful application of Gauss theorem . 28 . 1987.