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.