Double factorial

The fifteen different chord diagrams on six points or equivalently the fifteen different perfect matchings on a six-vertex complete graph
The fifteen different rooted binary trees (with unordered children) on a set of four labeled leaves

In mathematics, the product of all the integers from 1 up to some non-negative integer n that have the same parity as n is called the double factorial or semifactorial of n and is denoted by n!!.[1] That is,

where A consequence of this definition is that (as an empty product)

The double factorial should not be confused with the factorial function iterated twice, which is written as (n!)! and not n!!

For example, 9!! = 1 × 3 × 5 × 7 × 9 = 945.

For even n the double factorial is

For odd n it is

The sequence of double factorials for even n = 0, 2, 4, 6, 8, ... starts as

1, 2, 8, 48, 384, 3840, 46080, 645120, .... (sequence A000165 in the OEIS)

The sequence of double factorials for odd n = 1, 3, 5, 7, ... starts as

1, 3, 15, 105, 945, 10395, 135135, .... (sequence A001147 in the OEIS)

Merserve (1948)[2] (possibly the earliest publication to use double factorial notation)[3] states that the double factorial was originally introduced in order to simplify the expression of certain trigonometric integrals arising 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][4]

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

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

For an even positive integer n = 2k, k  0, the double factorial may be expressed as

For odd n = 2k  1, k  1, it has the expressions

In this expression, the first denominator equals (2k)!! and cancels the unwanted even factors from the numerator.

For an odd positive integer n = 2k  1, k  1, the double factorial may be expressed in terms of k-permutations of 2k as[1][3]


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

to give

Using this inverted recurrence, −1!! = 1, −3!! = −1, and −5!! = 1/3; negative odd numbers with greater magnitude have fractional double factorials.[1] In particular, this gives, when n is an odd number,

Complex arguments

Disregarding the above definition of n!! for even values of n, the double factorial for odd integers can be extended to most real and complex numbers z by noting that when z is a positive odd integer then [6] [7]

From this one can derive an alternative definition of z!! for non-negative even integer values of z:

with the value for 0!! in this case being

The expression found for z!! is defined for all complex numbers except the negative even integers. Using it as the definition, the volume of an n-dimensional hypersphere of radius R can be expressed as[8]

Applications in enumerative combinatorics

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

Callan (2009) and Dale & Moon (1993) 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 Rubey (2008) and Marsh & Martin (2011).[13][14]

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

Additional identities

For integral values of n,

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.[2][15]

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

Some additional identities involving double factorials of odd numbers are:



  1. 1 2 3 4 5 6 7 8 9 10 11 12 Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317Freely accessible.
  2. 1 2 Meserve, B. E. (1948), "Classroom Notes: Double Factorials", The American Mathematical Monthly, 55 (7): 425–426, doi:10.2307/2306136, MR 1527019
  3. 1 2 Gould, Henry; Quaintance, Jocelyn (2012), "Double fun with double factorials", Mathematics Magazine, 85 (3): 177–192, doi:10.4169/math.mag.85.3.177, MR 2924154.
  4. 1 2 3 4 Dale, M. R. T.; Moon, J. W. (1993), "The permuted analogues of three Catalan sets", Journal of Statistical Planning and Inference, 34 (1): 75–87, doi:10.1016/0378-3758(93)90035-5, MR 1209991.
  5. E.g., in Henderson, Daniel J.; Parmeter, Christopher F. (2012), "Canonical higher-order kernels for density derivative estimation", Statistics & Probability Letters, 82 (7): 1383–1387, doi:10.1016/j.spl.2012.03.013, MR 2929790 and Nielsen, B. (1999), "The likelihood-ratio test for rank in bivariate canonical correlation analysis", Biometrika, 86 (2): 279–288, doi:10.1093/biomet/86.2.279, MR 1705359.
  6. Hassani, Sadri (2000), Mathematical Methods: For Students of Physics and Related Fields, Undergraduate Texts in Mathematics, Springer, p. 266, ISBN 9780387989587.
  7. Double factorial: Specific values (formula, Wolfram Research, 2001-10-29, retrieved 2013-03-23.
  8. Mezey, Paul G. (2009), "Some dimension problems in molecular databases", Journal of Mathematical Chemistry, 45 (1): 1–6, doi:10.1007/s10910-008-9365-8.
  9. Kitaev, Sergey (2011), Patterns in Permutations and Words, EATCS Monographs in Theoretical Computer Science, Springer, p. 96, ISBN 9783642173332.
  10. Dale, M. R. T.; Narayana, T. V. (1986), "A partition of Catalan permuted sequences with applications", Journal of Statistical Planning and Inference, 14 (2): 245–249, doi:10.1016/0378-3758(86)90161-8, MR 852528.
  11. Tichy, Robert F.; Wagner, Stephan (2005), "Extremal problems for topological indices in combinatorial chemistry" (PDF), Journal of Computational Biology, 12 (7): 1004–1013, doi:10.1089/cmb.2005.12.1004.
  12. Janson, Svante (2008), "Plane recursive trees, Stirling permutations and an urn model", Fifth Colloquium on Mathematics and Computer Science, Discrete Math. Theor. Comput. Sci. Proc., AI, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, pp. 541–547, arXiv:0803.1129Freely accessible, MR 2508813.
  13. Rubey, Martin (2008), "Nestings of matchings and permutations and north steps in PDSAWs", 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), Discrete Math. Theor. Comput. Sci. Proc., AJ, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, pp. 691–704, MR 2721495.
  14. Marsh, Robert J.; Martin, Paul (2011), "Tiling bijections between paths and Brauer diagrams", Journal of Algebraic Combinatorics, 33 (3): 427–453, arXiv:0906.0912Freely accessible, doi:10.1007/s10801-010-0252-6, MR 2772541.
  15. Dassios, George; Kiriaki, Kiriakie (1987), "A useful application of Gauss theorem", Bulletin de la Société Mathématique de Grèce, 28 (part A): 40–43, MR 935868.

External links

This article is issued from Wikipedia - version of the 11/25/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.