# Combinatorial Functions

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

The factorial $n!$ for non-negative small integer $n$.

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

The number of permutations of $n$ distinct objects taken $k$ at a time.

## `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$.

## `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$, $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$.

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

Given a small non-negative integer $n$, this function returns the $n$-th Catalan number $C_n$, defined via the recursion $C_0 = 1$, $C_{n+1} = C_n\cdot(4n+2)/(n+2)$.

## `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$, $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$, $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.

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

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

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

The Stirling number of the second type, $\{{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).

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

The number $E(n,r)$ of permutations $p$ of $\{1, \dots, n\}$ having exactly $r$ ascents (i.e., places where $p_i < p_{i+1}$)

## `HarmonicNumber(n): RngIntElt -> FldRatElt`

The $n$th harmonic number $H_n = \Sigma_{i=1}^n {1\over i}$.

## `BernoulliNumber(n): RngIntElt -> FldRatElt`

Returns the $n$th Bernoulli number $B_n$ as a rational number.

## `BernoulliApproximation(n): RngIntElt -> FldPrElt`

Returns a real approximation to the $n$th Bernoulli number $B_n$.

## `BernoulliPolynomial(n): RngIntElt -> RngUPolElt`

The $n$th Bernoulli polynomial $B_n(x) = \sum_{k=0}^n {n \choose k} B_k x^{n-k}$ where $B_n$ is the $n$th Bernoulli number.