## Combinatorics

Catalan
`Catalan (n)`

Get `n`th Catalan number.

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

Factorial
`Factorial (n)`

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

FallingFactorial
`FallingFactorial (n,k)`

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

Fibonacci
`Fibonacci (x)`

Aliases: `fib`

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

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.

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.

HarmonicNumber
`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
`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)`.

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));```
```

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.

Permutations
`Permutations (k,n)`

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

RisingFactorial
`RisingFactorial (n,k)`

Aliases: `Pochhammer`

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

StirlingNumberFirst
`StirlingNumberFirst (n,m)`

Aliases: `StirlingS1`

Stirling number of the first kind.

StirlingNumberSecond
`StirlingNumberSecond (n,m)`

Aliases: `StirlingS2`

Stirling number of the second kind.

Subfactorial
`Subfactorial (n)`

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

Triangular
`Triangular (nth)`

Calculate the `n`th triangular number.

nCr
`nCr (n,r)`

Aliases: `Binomial`

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

nPr
`nPr (n,r)`

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