# 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 |

Combinatorial functions.

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 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, denoted

, gives the number of ways of partitioning

distinct objects into

sets of sizes

(with

).

*Mathematica* gives the exact integer result for the factorial of an integer.

Out[1]= | |

For non-integers,

*Mathematica* evaluates factorials using the gamma function.

Out[2]= | |

*Mathematica* can give symbolic results for some binomial coefficients.

Out[3]= | |

This gives the number of ways of partitioning

objects into sets containing 6 and 5 objects.

Out[4]= | |

The result is the same as

.

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 appear as the coefficients of

in the expansion of

.

The harmonic numbers

HarmonicNumber[n] are given by

; the harmonic numbers of order

HarmonicNumber are given by

. Harmonic numbers appear in many combinatorial estimation problems, often playing the role of discrete analogs of logarithms.

The Bernoulli polynomials

BernoulliB 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 have generating function

, and the Euler numbers

EulerE[n] are given by

.

The Nörlund polynomials

NorlundB 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

.

This gives the second Bernoulli polynomial

.

Out[6]= | |

You can also get Bernoulli polynomials by explicitly computing the power series for the generating function.

Out[7]= | |

BernoulliB[n] gives exact rational-number results for Bernoulli numbers.

Out[8]= | |

Stirling numbers show up in many combinatorial enumeration problems. For Stirling numbers of the first kind

StirlingS1,

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, 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 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

.

This gives a table of Stirling numbers of the first kind.

Out[9]= | |

The Stirling numbers appear as coefficients in this product.

Out[10]= | |

Here are the partitions of 4.

Out[11]= | |

Out[12]= | |

This gives the number of partitions of 100, with and without the constraint that the terms should be distinct.

Out[13]= | |

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.

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

You can give symbolic parameters in 3-j symbols.

Out[15]= | |