11.10. Combinatorics

Catalan (n)

Get n'th catalan number.

See Planetmath for more information.

Combinations (k,n)

Get all combinations of k numbers from 1 to n as a vector of vectors. (See also NextCombination)

DoubleFactorial (n)

Double factorial: n(n-2)(n-4)...

See Planetmath for more information.

Factorial (n)

Factorial: n(n-1)(n-2)...

See Planetmath for more information.

FallingFactorial (n,k)

Falling factorial: (n)_k = n(n-1)...(n-(k-1))

See Planetmath for more information.

Fibonacci (x)

Aliases: fib

Calculate nth fibonacci number. That is the number defined recursively by Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2) and Fibonacci(1) = Fibonacci(2) = 1.

See Wikipedia or Planetmath or Mathworld for more information.

FrobeniusNumber (v,arg...)

Calculate the Frobenius number. That is calculate smallest number that cannot be given as a nonnegative integer linear combination of a given vector of nonnegative integers. The vector can be given as separate numbers or a single vector. All the numbers given should have GCD of 1.

See Mathworld for more information.

GaloisMatrix (combining_rule)

Galois matrix given a linear combining rule (a_1*x_+...+a_n*x_n=x_(n+1)).

FrobeniusNumber (n,v)

Find the vector c of nonnegative integers such that taking the dot product with v is equal to n. If not possible returns null. v should be given sorted in increasing order and should consist of nonnegative integers.

See Mathworld for more information.

HarmonicNumber (n,r)

Aliases: HarmonicH

Harmonic Number, the n'th harmonic number of order r.

Hofstadter (n)

Hofstadter's function q(n) defined by q(1)=1, q(2)=1, q(n)=q(n-q(n-1))+q(n-q(n-2)).

LinearRecursiveSequence (seed_values,combining_rule,n)

Compute linear recursive sequence using galois stepping.

Multinomial (v,arg...)

Calculate multinomial coefficients. Takes a vector of k nonnegative integers and computes the multinomial coefficient. This corresponds to the coefficient in the homogeneous polynomial in k variables with the corresponding powers.

The formula for Multinomial(a,b,c) can be written as:

(a+b+c)! / (a!b!c!)

See Planetmath, Mathworld, or Wikipedia for more information.

NextCombination (v,n)

Get combination that would come after v in call to combinations, first combination should be [1:k]. This function is useful if you have many combinations to go through and you don't want to waste memory to store them all.

For example with Combination you would normally write a loop like:

for n in Combinations (4,6) do (
  SomeFunction (n)
);

n:=[1:4];
do (
  SomeFunction (n)
) while not IsNull(n:=NextCombination(n,6));

Pascal (i)

Get the Pascal's triangle as a matrix. This will return an i+1 by i+1 lower diagonal matrix which is the Pascal's triangle after i iterations.

See Planetmath for more information.

Permutations (k,n)

Get all permutations of k numbers from 1 to n as a vector of vectors.

See Mathworld or Wikipedia for more information.

RisingFactorial (n,k)

Aliases: Pochhammer

(Pochhammer) Rising factorial: (n)_k = n(n+1)...(n+(k-1)).

See Planetmath for more information.

StirlingNumberFirst (n,m)

Aliases: StirlingS1

Stirling number of the first kind.

See Planetmath or Mathworld for more information.

StirlingNumberSecond (n,m)

Aliases: StirlingS2

Stirling number of the second kind.

See Planetmath or Mathworld for more information.

Subfactorial (n)

Subfactorial: n! times sum_{k=1}^n (-1)^k/k!.

Triangular (nth)

Calculate the n'th triangular number.

See Planetmath for more information.

nCr (n,r)

Aliases: Binomial

Calculate combinations, that is, the binomial coefficient. n can be any real number.

See Planetmath for more information.

nPr (n,r)

Calculate the number of permutations of size rof numbers from 1 to n.

See Mathworld or Wikipedia for more information.