Double factorial

From Wikipedia for FEVERv2
Jump to navigation Jump to search

In mathematics, the double factorial or semifactorial of a number n, denoted by n‼, is the product of all the integers from 1 up to n that have the same parity (odd or even) as n. That is, Double factorial_sentence_0

For even n, the double factorial is Double factorial_sentence_1

and for odd n it is Double factorial_sentence_2

For example, 9‼ = 9 × 7 × 5 × 3 × 1 = 945. Double factorial_sentence_3

The zero double factorial 0‼ = 1 as an empty product. Double factorial_sentence_4

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

Double factorial_description_list_0

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

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

Double factorial_description_list_1

  • 1, 3, 15, 105, 945, 10395, 135135,... (sequence in the OEIS)Double factorial_item_1_1

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

History and usage Double factorial_section_0

(possibly the earliest publication to use double factorial notation) 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 factorial_sentence_8

Double factorials also arise in expressing the volume of a hypersphere, and they have many applications in enumerative combinatorics. Double factorial_sentence_9

They occur in Student's t-distribution (1908), though Gosset did not use the double exclamation point notation. Double factorial_sentence_10

Relation to the factorial Double factorial_section_1

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! Double factorial_sentence_11

)!. Double factorial_sentence_12

The factorial of a non-zero n may be written as the product of two double factorials: Double factorial_sentence_13

and therefore Double factorial_sentence_14

where the denominator cancels the unwanted factors in the numerator. Double factorial_sentence_15

(The last form also applies when n = 0.) Double factorial_sentence_16

For an even non-negative integer n = 2k with k ≥ 0, the double factorial may be expressed as Double factorial_sentence_17

For odd n = 2k − 1 with k ≥ 1, combining the two above displays yields Double factorial_sentence_18

For an odd positive integer n = 2k − 1 with k ≥ 1, the double factorial may be expressed in terms of k-permutations of 2k as Double factorial_sentence_19

Applications in enumerative combinatorics Double factorial_section_2

Double factorials are motivated by the fact that they occur frequently in enumerative combinatorics and other settings. Double factorial_sentence_20

For instance, n‼ for odd values of n counts Double factorial_sentence_21

Double factorial_unordered_list_2

  • Perfect matchings of the complete graph Kn + 1 for odd n. In such a graph, any single vertex v has n 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. Perfect matchings may be described in several other equivalent ways, including involutions without fixed points on a set of n + 1 items (permutations in which each cycle is a pair) or chord diagrams (sets of chords of a set of n + 1 points evenly spaced on a circle such that each point is the endpoint of exactly one chord, also called Brauer diagrams). 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.Double factorial_item_2_2
  • Stirling permutations, permutations of the multiset of numbers 1, 1, 2, 2, ..., k, k in which each pair of equal numbers is separated only by larger numbers, where k = n + 1/2. The two copies of k must be adjacent; removing them from the permutation leaves a permutation in which the maximum element is k − 1, with n positions into which the adjacent pair of k values may be placed. From this recursive construction, a proof that the Stirling permutations are counted by the double permutations follows by induction. 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 2k positions of the permutation, so again the number of permutations may be counted by the double permutations.Double factorial_item_2_3
  • Heap-ordered trees, trees with k + 1 nodes labeled 0, 1, 2, ... k, 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.Double factorial_item_2_4
  • Unrooted binary trees with n + 5/2 labeled leaves. Each such tree may be formed from a tree with one fewer leaf, by subdividing one of the n tree edges and making the new vertex be the parent of a new leaf.Double factorial_item_2_5
  • Rooted binary trees with n + 3/2 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.Double factorial_item_2_6

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

For bijective proofs that some of these objects are equinumerous, see and . Double factorial_sentence_23

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

Extensions Double factorial_section_3

Negative arguments Double factorial_section_4

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

However, the double factorial of odd numbers may be extended to any negative odd integer argument by inverting its recurrence relation Double factorial_sentence_26

to give Double factorial_sentence_27

Using this inverted recurrence, (−1)‼ = 1, (−3)‼ = −1, and (−5)‼ = 1/3; negative odd numbers with greater magnitude have fractional double factorials. Double factorial_sentence_28

In particular, this gives, when n is an odd number, Double factorial_sentence_29

Complex arguments Double factorial_section_5

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 Double factorial_sentence_30

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

with the value for 0‼ in this case being Double factorial_sentence_32

The expression found for z‼ is defined for all complex numbers except the negative even integers. Double factorial_sentence_33

Using it as the definition, the volume of an n-dimensional hypersphere of radius R can be expressed as Double factorial_sentence_34

Additional identities Double factorial_section_6

For integer values of n, Double factorial_sentence_35

Using instead the extension of the double factorial of odd numbers to complex numbers, the formula is Double factorial_sentence_36

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

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

Some additional identities involving double factorials of odd numbers are: Double factorial_sentence_39

An approximation for the ratio of the double factorial of two consecutive integers is Double factorial_sentence_40

This approximation gets more accurate as n increases. Double factorial_sentence_41

Generalizations Double factorial_section_7

Definitions Double factorial_section_8

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 α ∈ ℤ: Double factorial_sentence_42

Alternative extension of the multifactorial Double factorial_section_9

Alternatively, the multifactorial n! Double factorial_sentence_43

(α) can be extended to most real and complex numbers n by noting that when n is one more than a positive multiple of α then Double factorial_sentence_44

This last expression is defined much more broadly than the original. Double factorial_sentence_45

In the same way that n! Double factorial_sentence_46

is not defined for negative integers, and n‼ is not defined for negative even integers, n! Double factorial_sentence_47

(α) is not defined for negative multiples of α. Double factorial_sentence_48

However, it is defined for all other complex numbers. Double factorial_sentence_49

This definition is consistent with the earlier definition only for those integers n satisfying n ≡ 1 mod α. Double factorial_sentence_50

In addition to extending n! Double factorial_sentence_51

(α) to most complex numbers n, this definition has the feature of working for all positive real values of α. Double factorial_sentence_52

Furthermore, when α = 1, this definition is mathematically equivalent to the Π(n) function, described above. Double factorial_sentence_53

Also, when α = 2, this definition is mathematically equivalent to the alternative extension of the double factorial. Double factorial_sentence_54

Generalized Stirling numbers expanding the multifactorial functions Double factorial_section_10

A class of generalized Stirling numbers of the first kind is defined for α > 0 by the following triangular recurrence relation: Double factorial_sentence_55

These generalized α-factorial coefficients then generate the distinct symbolic polynomial products defining the multiple factorial, or α-factorial functions, (x − 1)! Double factorial_sentence_56

(α), as Double factorial_sentence_57

The distinct polynomial expansions in the previous equations actually define the α-factorial products for multiple distinct cases of the least residues x ≡ n0 mod α for n0 ∈ {0, 1, 2, ..., α − 1}. Double factorial_sentence_58

The generalized α-factorial polynomials, σ n(x) where σ n(x) ≡ σn(x), which generalize the Stirling convolution polynomials from the single factorial case to the multifactorial cases, are defined by Double factorial_sentence_59

for 0 ≤ n ≤ x. Double factorial_sentence_60

These polynomials have a particularly nice closed-form ordinary generating function given by Double factorial_sentence_61

Other combinatorial properties and expansions of these generalized α-factorial triangles and polynomial sequences are considered in . Double factorial_sentence_62

Exact finite sums involving multiple factorial functions Double factorial_section_11

Suppose that n ≥ 1 and α ≥ 2 are integer-valued. Double factorial_sentence_63

Then we can expand the next single finite sums involving the multifactorial, or α-factorial functions, (αn − 1)! Double factorial_sentence_64

(α), in terms of the Pochhammer symbol and the generalized, rational-valued binomial coefficients as Double factorial_sentence_65

and moreover, we similarly have double sum expansions of these functions given by Double factorial_sentence_66

The first two sums above are similar in form to a known non-round combinatorial identity for the double factorial function when α := 2 given by . Double factorial_sentence_67

Additional finite sum expansions of congruences for the α-factorial functions, (αn − d)! Double factorial_sentence_68

(α), modulo any prescribed integer h ≥ 2 for any 0 ≤ d < α are given by . Double factorial_sentence_69


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Double factorial.