3.2.6 Combinatorial Functions

n!	factorial
n!!	double factorial
Binomial[n, m]	binomial coefficient
Multinomial[, , ... ]	multinomial coefficient
Fibonacci[n]	Fibonacci number
Fibonacci[n, x]	Fibonacci polynomial
HarmonicNumber[n]	harmonic number
HarmonicNumber[n, r]	harmonic number of order
BernoulliB[n]	Bernoulli number
BernoulliB[n, x]	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
PartitionsP[n]	the number of unrestricted partitions of the integer
PartitionsQ[n]	the number of partitions of into distinct parts
Signature[{, , ... }]	the signature of a permutation

The factorial function n! gives the number of ways of ordering objects. For non-integer , the numerical value of is obtained from the gamma function, discussed in Section 3.2.11.

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 multinomial coefficient Multinomial[, , ... ], denoted , gives the number of ways of partitioning distinct objects into sets of sizes (with ).

This gives the number of ways of partitioning objects into sets containing 6 and 5 objects.

In[4]:=  Multinomial[6, 5] Out[4]=

The result is the same as .

In[5]:=  Binomial[11, 6] 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 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 .

This gives the second Bernoulli polynomial .

In[6]:=  BernoulliB[2, x] Out[6]=

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] give the number of ways of partitioning a set of elements into non-empty subsets. They satisfy the relation .

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

The partition function increases asymptotically like . Note that you cannot simply use Plot to generate a plot of a function like PartitionsP because the function can only be evaluated with integer arguments.

In[12]:=  ListPlot[ Table[ N[Log[ PartitionsP[n] ]], {n, 100} ] ] Out[12]=

The functions in this section allow you to enumerate various kinds of combinatorial objects. Functions like Permutations allow you instead to generate lists of various combinations of elements.

The signature function Signature[{, , ... }] 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, m}]
	Clebsch-Gordan coefficient
ThreeJSymbol[{, }, {, }, {, }]
	Wigner 3-j symbol
SixJSymbol[{, , }, {, , }]
	Racah 6-j symbol

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, 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[{, }, {, }, {, }] 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[{, , }, {, , }] give the couplings of three quantum mechanical angular momentum states. The Racah coefficients are related by a phase to the 6-j symbols.