# Combinatorial Functions

n! | factorial |

n!! | double factorial |

Binomial[n,m] | binomial coefficient |

Multinomial[n_{1},n_{2},...] | multinomial coefficient |

CatalanNumber[n] | Catalan number |

Hyperfactorial[n] | hyperfactorial |

BarnesG[n] | Barnes G-function |

Subfactorial[n] | number of derangements of objects |

Fibonacci[n] | Fibonacci number |

Fibonacci[n,x] | Fibonacci polynomial |

LucasL[n] | Lucas number |

LucasL[n,x] | Lucas polynomial |

HarmonicNumber[n] | harmonic number |

HarmonicNumber[n,r] | harmonic number of order |

BernoulliB[n] | Bernoulli number |

BernoulliB[n,x] | Bernoulli polynomial |

NorlundB[n,a] | Nörlund polynomial |

NorlundB[n,a,x] | generalized Bernoulli polynomial |

EulerE[n] | Euler number |

EulerE[n,x] | Euler polynomial |

StirlingS1[n,m] | Stirling number of the first kind |

StirlingS2[n,m] | Stirling number of the second kind |

BellB[n] | Bell number |

BellB[n,x] | Bell polynomial |

PartitionsP[n] | the number of unrestricted partitions of the integer |

IntegerPartitions[n] | partitions of an integer |

PartitionsQ[n] | the number of partitions of into distinct parts |

Signature[{i_{1},i_{2},...}] | the signature of a permutation |

The factorial function gives the number of ways of ordering objects. For non-integer , the numerical value of is obtained from the gamma function, discussed in "Special Functions".

The binomial coefficient Binomial[n, m] can be written as . It gives the number of ways of choosing objects from a collection of objects, without regard to order. The Catalan numbers, which appear in various tree enumeration problems, are given in terms of binomial coefficients as .

The subfactorial Subfactorial[n] gives the number of permutations of objects that leave no object fixed. Such a permutation is called a derangement. The subfactorial is given by .

The multinomial coefficient Multinomial[n_{1}, n_{2}, ...], denoted , gives the number of ways of partitioning distinct objects into sets of sizes (with ).

In[1]:= |

Out[1]= |

In[2]:= |

Out[2]= |

In[3]:= |

Out[3]= |

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]= |

The Fibonacci numbers Fibonacci[n] satisfy the recurrence relation with . They appear in a wide range of discrete mathematical problems. For large , approaches the golden ratio. The Lucas numbers LucasL[n] satisfy the same recurrence relation as the Fibonacci numbers do, but with initial conditions and .

The Fibonacci polynomials Fibonacci[n, x] appear as the coefficients of in the expansion of .

The harmonic numbers HarmonicNumber[n] are given by ; the harmonic numbers of order HarmonicNumber[n, r] are given by . Harmonic numbers appear in many combinatorial estimation problems, often playing the role of discrete analogs of logarithms.

The Bernoulli polynomials BernoulliB[n, x] satisfy the generating function relation . The Bernoulli numbers BernoulliB[n] are given by . The appear as the coefficients of the terms in the Euler-Maclaurin summation formula for approximating integrals. The Bernoulli numbers are related to the Genocchi numbers by .

Numerical values for Bernoulli numbers are needed in many numerical algorithms. You can always get these numerical values by first finding exact rational results using BernoulliB[n], and then applying N.

The Euler polynomials EulerE[n, x] have generating function , and the Euler numbers EulerE[n] are given by .

The Nörlund polynomials NorlundB[n, a] satisfy the generating function relation . The Nörlund polynomials give the Bernoulli numbers when . For other positive integer values of , the Nörlund polynomials give higher-order Bernoulli numbers. The generalized Bernoulli polynomials NorlundB[n, a, x] satisfy the generating function relation .

In[6]:= |

Out[6]= |

In[7]:= |

Out[7]= |

In[8]:= |

Out[8]= |

Stirling numbers show up in many combinatorial enumeration problems. For Stirling numbers of the first kind StirlingS1[n, m], gives the number of permutations of elements which contain exactly cycles. These Stirling numbers satisfy the generating function relation . Note that some definitions of the differ by a factor from what is used in *Mathematica*.

Stirling numbers of the second kind StirlingS2[n, m], sometimes denoted , give the number of ways of partitioning a set of elements into non-empty subsets. They satisfy the relation .

The Bell numbers BellB[n] give the total number of ways that a set of elements can be partitioned into non-empty subsets. The Bell polynomials BellB[n, x] satisfy the generating function relation .

The partition function PartitionsP[n] gives the number of ways of writing the integer as a sum of positive integers, without regard to order. PartitionsQ[n] gives the number of ways of writing as a sum of positive integers, with the constraint that all the integers in each sum are distinct.

IntegerPartitions[n] gives a list of the partitions of , with length .

In[9]:= |

Out[9]= |

In[10]:= |

Out[10]= |

In[11]:= |

Out[11]= |

In[12]:= |

Out[12]= |

In[13]:= |

Out[13]= |

In[14]:= |

Out[14]= |

Most of the functions here allow you to *count* various kinds of combinatorial objects. Functions like IntegerPartitions and Permutations allow you instead to *generate* lists of various combinations of elements.

The signature function Signature[{i_{1}, i_{2}, ...}] gives the signature of a permutation. It is equal to for even permutations (composed of an even number of transpositions), and to for odd permutations. The signature function can be thought of as a totally antisymmetric tensor, Levi-Civita symbol or epsilon symbol.

ClebschGordan[{j_{1},m_{1}},{j_{2},m_{2}},{j,m}] | Clebsch-Gordan coefficient |

ThreeJSymbol[{j_{1},m_{1}},{j_{2},m_{2}},{j_{3},m_{3}}] | Wigner 3-j symbol |

SixJSymbol[{j_{1},j_{2},j_{3}},{j_{4},j_{5},j_{6}}] | Racah 6-j symbol |

Rotational coupling coefficients.

Clebsch-Gordan coefficients and -j symbols arise in the study of angular momenta in quantum mechanics, and in other applications of the rotation group. The Clebsch-Gordan coefficients ClebschGordan[{j_{1}, m_{1}}, {j_{2}, m_{2}}, {j, m}] give the coefficients in the expansion of the quantum mechanical angular momentum state in terms of products of states .

The 3-j symbols or Wigner coefficients ThreeJSymbol[{j_{1}, m_{1}}, {j_{2}, m_{2}}, {j_{3}, m_{3}}] are a more symmetrical form of Clebsch-Gordan coefficients. In *Mathematica*, the Clebsch-Gordan coefficients are given in terms of 3-j symbols by .

The 6-j symbols SixJSymbol[{j_{1}, j_{2}, j_{3}}, {j_{4}, j_{5}, j_{6}}] give the couplings of three quantum mechanical angular momentum states. The Racah coefficients are related by a phase to the 6-j symbols.

In[15]:= |

Out[15]= |