Combinatorics

Catalan
Catalan (n)

Get nth Catalan number.

See Planetmath for more information.

Combinations
Combinations (k,n)

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

DoubleFactorial
DoubleFactorial (n)

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

See Planetmath for more information.

Factorial
Factorial (n)

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

See Planetmath for more information.

FallingFactorial
FallingFactorial (n,k)

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

See Planetmath for more information.

Fibonacci
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
FrobeniusNumber (v,arg...)

Calculate the Frobenius number. That is calculate smallest number that cannot be given as a non-negative integer linear combination of a given vector of non-negative 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
GaloisMatrix (combining_rule)

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

GreedyAlgorithm
GreedyAlgorithm (n,v)

Find the vector c of non-negative 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 non-negative integers.

See Mathworld for more information.

HarmonicNumber
HarmonicNumber (n,r)

Aliases: HarmonicH

Harmonic Number, the nth harmonic number of order r.

Hofstadter
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
LinearRecursiveSequence (seed_values,combining_rule,n)

Compute linear recursive sequence using Galois stepping.

Multinomial
Multinomial (v,arg...)

Calculate multinomial coefficients. Takes a vector of k non-negative 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!)

In other words, if we would have only two elements, then Multinomial(a,b) is the same thing as Binomial(a+b,a) or Binomial(a+b,b).

See Wikipedia, Planetmath, or Mathworld for more information.

NextCombination
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 Combinations you would normally write a loop like:

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

But with NextCombination you would write something like:

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

See also Combinations.

Pascal
Pascal (i)

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

See Planetmath for more information.

Permutations
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
RisingFactorial (n,k)

Aliases: Pochhammer

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

See Planetmath for more information.

StirlingNumberFirst
StirlingNumberFirst (n,m)

Aliases: StirlingS1

Stirling number of the first kind.

See Planetmath or Mathworld for more information.

StirlingNumberSecond
StirlingNumberSecond (n,m)

Aliases: StirlingS2

Stirling number of the second kind.

See Planetmath or Mathworld for more information.

Subfactorial
Subfactorial (n)

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

Triangular
Triangular (nth)

Calculate the nth triangular number.

See Planetmath for more information.

nCr
nCr (n,r)

Aliases: Binomial

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

See Planetmath for more information.

nPr
nPr (n,r)

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

See Mathworld or Wikipedia for more information.