nLab
double factorial

Contents

Context

Arithmetic

Combinatorics

Contents

Definition

For nn a natural number, the double factorial (2n+1)!!(2n+1)!! is defined to be the product (2n+1)(2n1)1(2n+1)(2n-1)\ldots 1. Alternatively, in terms of the ordinary factorial,

(2n1)!!=12 n(2n)!n!(2n-1)!! = \frac1{2^n} \frac{(2n)!}{n!}

so that in particular, (1)!!(-1)!! is defined to be 11. Relatedly, we may define (2n)!!=2 nn!(2n)!! = 2^n n!.

Double-factorials have a number of applications in enumerative combinatorics. They are particularly prone to appear whenever dealing with binomial coefficients

(xn)=x(x1)(xn+1)n!\binom{x}{n} = \frac{x(x-1)\ldots (x-n+1)}{n!}

in the case x=1/2x = 1/2 or x=1/2x = -1/2, or when dealing with middle binomial coefficients (2nn)\binom{2n}{n}, or when dealing with the values of the Gamma function at half-integers.

According to the combinatorial interpretation below, the exponential generating function of the sequence a na_n defined by a 2n=(2n1)!!a_{2n} = (2n-1)!! and a 2n+1=0a_{2n+1} = 0 is

n0a nx nn!=exp(x 2/2).\sum_{n \geq 0} \frac{a_n x^n}{n!} = \exp(x^2/2).

This is related to the fact that the double-factorials also crop up in calculations dealing with Gaussian integrals such as

0 p(x)e x 2/2dx\int_0^\infty p(x) e^{-x^2/2}\; d x

for even polynomials pp, with consequent applications in quantum mechanics, for example calculations surrounding the quantum harmonic oscillator. See the section below on moments of Gaussian distributions.

Combinatorial interpretation

The double-factorials (2n1)!!(2n-1)!! count the number of involutions without fixed points on a set with 2n2n elements, or the number of partitions of a (2n)(2n)-element set into 22-element sets, or the number of isomorphism classes of rooted chord diagrams with nn chords. This follows readily from the exponential generating function expression above, and follows readily by considering the species composition of the exponential species exp\exp (the terminal object in the category of species) with the species x 2/2x^2/2, defined to be terminal at 22-element sets and empty at others.

Moments of the standard Gaussian distribution

The computation begins with a famous observation

12π e x 2/2dx=1\frac1{\sqrt{2\pi}} \int_{-\infty}^\infty e^{-x^2/2}\; d x = 1

which says that x12πe x 2/2x \mapsto \frac1{\sqrt{2\pi}} e^{-x^2/2} is a probability distribution on \mathbb{R} with Lebesgue measure.

Proposition

For each n0n \geq 0,

12π x ne x 2/2dx=a n\frac1{\sqrt{2\pi}} \int_{-\infty}^\infty x^n e^{-x^2/2}\; d x = a_n

where a na_n are the MacLaurin coefficients in e y 2/2= n0a ny nn!e^{y^2/2} = \sum_{n \geq 0} \frac{a_n y^n}{n!}, namely, a n=0a_n = 0 if nn is odd, and a 2n=(2n1)!!a_{2n} = (2n-1)!!.

Proof

By matching MacLaurin coefficients, it is enough to show

n0(12π x ne x 2/2dx)y nn!=e y 2/2\sum_{n \geq 0} \left(\frac1{\sqrt{2\pi}} \int_{-\infty}^\infty x^n e^{-x^2/2} \; d x\right) \frac{y^n}{n!} = e^{y^2/2}

However, the left side equals

12π n0(xy) nn!e x 2/2dx = 12π e xye x 2/2dx = e y 2/212π e (xy) 2/2dx = e y 2/2\array{ \frac1{\sqrt{2\pi}} \displaystyle\int_{-\infty}^\infty \sum_{n \geq 0} \frac{(x y)^n}{n!} e^{-x^2/2}\; d x & = & \frac1{\sqrt{2\pi}} \displaystyle\int_{-\infty}^\infty e^{x y} e^{-x^2/2} \;d x \\ & = & e^{y^2/2} \cdot \frac1{\sqrt{2\pi}} \displaystyle\int_{-\infty}^\infty e^{-(x-y)^2/2} \;d x \\ & = & e^{y^2/2} }

where the last line results from the famous observation by substituting xyx-y for xx.

References

See also

Last revised on September 17, 2018 at 09:00:05. See the history of this page for a list of all contributions to it.