Combinatorial Functions

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

The binomial coefficient n choose r.

Multinomial(n, [a_1, ... a_n]) : RngIntElt, [RngIntElt] -> RngIntElt

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

Factorial(n) : RngIntElt -> RngIntElt

The factorial n! for positive small integer n.

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, Q) : RngIntElt, SetEnum -> [ [ RngIntElt ] ]

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

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

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

StirlingFirst(m, n) : RngIntElt, RngIntElt -> RngIntElt

The Stirling number of the first type, [(m atop n)], where m and n are non-negative integers.

StirlingSecond(m, n) : RngIntElt, RngIntElt -> RngIntElt

The Stirling number of the second type, {(m atop n)}, where m and n are non-negative integers.

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 nth 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.