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.