Combinatorial Functions

Combinatorial functions.

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

The binomial coefficient (RefLink[Binomial, paclet:ref/Binomial])[n,m] can be written as (({{n}, {m}}))==n!/[m!(n-m)!]. It gives the number of ways of choosing m objects from a collection of n objects, without regard to order. The Catalan numbers, which appear in various tree enumeration problems, are given in terms of binomial coefficients as (Subscript[c, n])==(({{2n}, {n}}))/(n+1).

The subfactorial (RefLink[Subfactorial, paclet:ref/Subfactorial])[n] gives the number of permutations of n objects that leave no object fixed. Such a permutation is called a derangement. The subfactorial is given by n!(∑_(k==0)^n)(((-1))^k)/k!.

The multinomial coefficient (RefLink[Multinomial, paclet:ref/Multinomial])[(Subscript[n, 1]),(Subscript[n, 2]),…], denoted (N;(Subscript[n, 1]),(Subscript[n, 2]),…,(Subscript[n, m]))==N!/((Subscript[n, 1])!(Subscript[n, 2])!… (Subscript[n, m])!), gives the number of ways of partitioning N distinct objects into m sets of sizes (Subscript[n, i]) (with N==(∑_(i==1)^m)(Subscript[n, i])).

The Wolfram Language gives the exact integer result for the factorial of an integer:

30!

For non-integers, the Wolfram Language evaluates factorials using the gamma function:

3.6!

The Wolfram Language can give symbolic results for some binomial coefficients:

Binomial[n,2]

This gives the number of ways of partitioning 6+5==11 objects into sets containing 6 and 5 objects:

Multinomial[6,5]

The result is the same as (({{11}, {6}})):

Binomial[11,6]

The Fibonacci numbers (RefLink[Fibonacci, paclet:ref/Fibonacci])[n] satisfy the recurrence relation (Subscript[F, n])==(Subscript[F, n-1])+(Subscript[F, n-2]) with (Subscript[F, 1])==(Subscript[F, 2])==1. They appear in a wide range of discrete mathematical problems. For large n, (Subscript[F, n])/(Subscript[F, n-1]) approaches the golden ratio. The Lucas numbers (RefLink[LucasL, paclet:ref/LucasL])[n] satisfy the same recurrence relation as the Fibonacci numbers do, but with initial conditions (Subscript[L, 1])==1 and (Subscript[L, 2])==3.

The Fibonacci polynomials (RefLink[Fibonacci, paclet:ref/Fibonacci])[n,x] appear as the coefficients of (t^n) in the expansion of t/(1-xt-(t^2))==(∑_(n==0)^∞)(Subscript[F, n])(x)(t^n) .

The harmonic numbers (RefLink[HarmonicNumber, paclet:ref/HarmonicNumber])[n] are given by (Subscript[H, n])==(∑_(i==1)^n)1/i; the harmonic numbers of order r (RefLink[HarmonicNumber, paclet:ref/HarmonicNumber])[n,r] are given by (Subscript[H, n]^((r)))==(∑_(i==1)^n)1/(i^r). Harmonic numbers appear in many combinatorial estimation problems, often playing the role of discrete analogs of logarithms.

The Bernoulli polynomials (RefLink[BernoulliB, paclet:ref/BernoulliB])[n,x] satisfy the generating function relation t(e^(x t))/((e^t)-1)==(∑_(n==0)^∞)(Subscript[B, n])(x)(t^n)/n! . The Bernoulli numbers (RefLink[BernoulliB, paclet:ref/BernoulliB])[n] are given by (Subscript[B, n])==(Subscript[B, n])(0). The (Subscript[B, n]) 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 (Subscript[G, n])==2(1-(2^n))(Subscript[B, n]).

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 (RefLink[BernoulliB, paclet:ref/BernoulliB])[n], and then applying (RefLink[N, paclet:ref/N]).

The Euler polynomials (RefLink[EulerE, paclet:ref/EulerE])[n,x] have generating function 2(e^(x t))/((e^t)+1)==(∑_(n==0)^∞)(Subscript[E, n])(x)(t^n)/n! , and the Euler numbers (RefLink[EulerE, paclet:ref/EulerE])[n] are given by (Subscript[E, n])==(2^n)(Subscript[E, n])((1/2)).

The Nörlund polynomials (RefLink[NorlundB, paclet:ref/NorlundB])[n,a] satisfy the generating function relation (t^a)/((((e^t)-1))^a)==(∑_(n==0)^∞)(Subscript[B, n]^((a)))(t^n)/n! . The Nörlund polynomials give the Bernoulli numbers when a==1. For other positive integer values of a, the Nörlund polynomials give higher-order Bernoulli numbers. The generalized Bernoulli polynomials (RefLink[NorlundB, paclet:ref/NorlundB])[n,a,x]  satisfy the generating function relation (t^a)(e^(x t))/((((e^t)-1))^a)==(∑_(n==0)^∞)(Subscript[B, n]^((a)))(x)(t^n)/n! .

This gives the second Bernoulli polynomial (Subscript[B, 2])(x):

BernoulliB[2,x]

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

Series[t Exp[x t]/(Exp[t]-1),{t,0,4}]

(RefLink[BernoulliB, paclet:ref/BernoulliB])[n] gives exact rational-number results for Bernoulli numbers:

BernoulliB[20]

Stirling numbers show up in many combinatorial enumeration problems. For Stirling numbers of the first kind (RefLink[StirlingS1, paclet:ref/StirlingS1])[n,m], (((-1))^(n-m))(Subscript[S, n]^((m))) gives the number of permutations of n elements which contain exactly m cycles. These Stirling numbers satisfy the generating function relation x(x-1)…(x-n+1)==(∑_(m==0)^n)(Subscript[S, n]^((m)))(x^m). Note that some definitions of the (Subscript[S, n]^((m))) differ by a factor (((-1))^(n-m)) from what is used in the Wolfram Language.

Stirling numbers of the second kind (RefLink[StirlingS2, paclet:ref/StirlingS2])[n,m], sometimes denoted (Subscript[𝒮, n]^((m))), give the number of ways of partitioning a set of n elements into m non-empty subsets. They satisfy the relation (x^n)==(∑_(m==0)^n)(Subscript[𝒮, n]^((m)))x(x-1)...(x-m+1).

The Bell numbers (RefLink[BellB, paclet:ref/BellB])[n] give the total number of ways that a set of n elements can be partitioned into non-empty subsets. The Bell polynomials (RefLink[BellB, paclet:ref/BellB])[n,x] satisfy the generating function relation (e^(((e^t)-1)x))==(∑_(n==0)^∞)(Subscript[B, n])(x)((t^n)/(n!)).

The partition function (RefLink[PartitionsP, paclet:ref/PartitionsP])[n] gives the number of ways of writing the integer n as a sum of positive integers, without regard to order. (RefLink[PartitionsQ, paclet:ref/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.

(RefLink[IntegerPartitions, paclet:ref/IntegerPartitions])[n] gives a list of the partitions of n, with length (RefLink[PartitionsP, paclet:ref/PartitionsP])[n].

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

Table[StirlingS1[5,i],{i,5}]

The Stirling numbers appear as coefficients in this product:

Expand[Product[x-i,{i,0,4}]]

Here are the partitions of 4:

IntegerPartitions[4]

The number of partitions is given by (RefLink[PartitionsP, paclet:ref/PartitionsP])[4]:

Length[%]==PartitionsP[4]

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

{PartitionsQ[100],PartitionsP[100]}

The partition function p(n) increases asymptotically like (e^(Sqrt[n])). Note that you cannot simply use (RefLink[Plot, paclet:ref/Plot]) to generate a plot of a function like (RefLink[PartitionsP, paclet:ref/PartitionsP]) because the function can only be evaluated with integer arguments:

ListPlot[Table[N[Log[PartitionsP[n]]],{n,100}]]

Most of the functions here allow you to count various kinds of combinatorial objects. Functions like (RefLink[IntegerPartitions, paclet:ref/IntegerPartitions]) and (RefLink[Permutations, paclet:ref/Permutations]) allow you instead to generate lists of various combinations of elements.

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

Rotational coupling coefficients.

Clebsch–Gordan coefficients and n-j symbols arise in the study of angular momenta in quantum mechanics, and in other applications of the rotation group. The Clebsch–Gordan coefficients (RefLink[ClebschGordan, paclet:ref/ClebschGordan])[{(Subscript[j, 1]),(Subscript[m, 1])},{(Subscript[j, 2]),(Subscript[m, 2])},{j,m}] give the coefficients in the expansion of the quantum mechanical angular momentum state |j,m⟩ in terms of products of states |(Subscript[j, 1]),(Subscript[m, 1])⟩ |(Subscript[j, 2]),(Subscript[m, 2])⟩.

The 3-j symbols or Wigner coefficients (RefLink[ThreeJSymbol, paclet:ref/ThreeJSymbol])[{(Subscript[j, 1]),(Subscript[m, 1])},{(Subscript[j, 2]),(Subscript[m, 2])},{(Subscript[j, 3]),(Subscript[m, 3])}] are a more symmetrical form of Clebsch–Gordan coefficients. In the Wolfram Language, the Clebsch–Gordan coefficients are given in terms of 3-j symbols by (Subscript[C, (Subscript[m, 1])(Subscript[m, 2])(Subscript[m, 3])]^((Subscript[j, 1])(Subscript[j, 2])(Subscript[j, 3])))==(((-1))^((Subscript[m, 3])+(Subscript[j, 1])-(Subscript[j, 2])))(Sqrt[2(Subscript[j, 3])+1])(({{(Subscript[j, 1])}, {(Subscript[m, 1])}}) ({{(Subscript[j, 2])}, {(Subscript[m, 2])}}) ({{(Subscript[j, 3])}, {-(Subscript[m, 3])}})).

The 6-j symbols (RefLink[SixJSymbol, paclet:ref/SixJSymbol])[{(Subscript[j, 1]),(Subscript[j, 2]),(Subscript[j, 3])},{(Subscript[j, 4]),(Subscript[j, 5]),(Subscript[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.

You can give symbolic parameters in 3-j symbols:

ThreeJSymbol[{j,m},{j+1/2,-m-1/2},{1/2,1/2}]