# Combinatorial Functions

## `Binomial(n, r): RngIntElt, RngIntElt -> RngIntElt`

The binomial coefficient $n\choose r$.

## `Multinomial(n, [r₁, ... rₙ]): RngIntElt, [RngIntElt] -> RngIntElt`

Given a sequence $Q = [r_1, \ldots, r_k]$ of positive integers such that $n = r_1 + ... + r_k$, return the multinomial coefficient $n\choose r_1, \ldots, r_k$.

## `Factorial(n): RngIntElt -> RngIntElt`

The factorial $n!$ for positive small integer $n$.

## `IsFactorial(n): RngIntElt -> BoolElt, RngIntElt`

Tests if $n = k!$ for some $k$. If so, return `true` and $k$, `false` otherwise.

## `Partitions(n): RngIntElt -> [ [ RngIntElt ] ]`

The unrestricted partitions of the positive integer $n$. This function returns a sequence of integer sequences, each of which is a different sequence of positive integers (in descending order) adding up to $n$. The integer $n$ must be small.

## `NumberOfPartitions(n): RngIntElt -> RngIntElt`

The number of unrestricted partitions of the non-negative integer $n$. The integer $n$ must be small.

## `RestrictedPartitions(n, M): RngIntElt, SetEnum -> [ [ RngIntElt ] ]`

The partitions of the positive integer $n$, restricted to elements of the positive integer sequence $M$.

## `RestrictedPartitions(n, k, M): RngIntElt, RngIntElt, SetEnum -> [ [ RngIntElt ] ]`

The partitions of the positive integer $n$ into $k$ parts, restricted to elements of the positive integer sequence $M$.

## `StirlingFirst(n, k): RngIntElt, RngIntElt -> RngIntElt`

The Stirling number of the first type, $s(n, k) = [{n\atop k}]$, where $n$ and $k$ are non-negative integers.

## `StirlingSecond(n, k): RngIntElt, RngIntElt -> RngIntElt`

The Stirling number of the second type, $S(n,k)=\{{n\atop k}\}$, where $n$ and $k$ are non-negative integers.

## `Bell(n): RngIntElt -> RngIntElt`

The $n$th Bell number, giving the number of partitions of a set of size $n$. (Not to be confused with `NumberOfPartitions(n)`, which gives the number of partitions of the *integer* $n$.) This is equal to the sum of `StirlingSecond(n,k)` for $k$ between 0 and $n$ (inclusive).

## `Fibonacci(n): RngIntElt -> RngIntElt`

Given an integer $n$, this function returns the $n$-th Fibonacci number $F_n$, which can be defined via the recursion $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for all integers $n$. Note that $n$ is allowed to be negative, and that $F_{-n} = (-1)^{n+1} F_n$.

## `Lucas(n): RngIntElt -> RngIntElt`

Given an integer $n$, this function returns the $n$-th Lucas number $L_n$, which can be defined via the recursion $L_0 = 2$, $L_1 = 1$ and $L_n = L_{n-1} + L_{n-2}$ for all integers $n$. Note that $n$ is allowed to be negative, and that $L_{-n} = (-1)^{n}L_n$.

## `GeneralizedFibonacciNumber(g0, g1, n): RngIntElt, RngIntElt, RngIntElt -> RngIntElt`

The $n$th member of the generalized Fibonacci sequence defined by $G_0 = g_0$, $G_1 = g_1$ and $G_n = G_{n-1} + G_{n-2}$ for all integers $n$. Note that $n$ is allowed to be negative. The Fibonacci and Lucas numbers are special cases where $(g_0, g_1) = (0, 1)$ or $(2, 1)$ respectively.