---
title: "Combinatorial Functions"
canonical: "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/combinatorics.html"
source: "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/combinatorics.md"
part: "Basic Rings"
chapter: "Ring of Integers"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Basic Rings", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/index-basic-rings.md"}
  - {"title": "Ring of Integers", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/index-integers.md"}
prev: {"title": "Arithmetic Functions", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/arithmetic-function.md"}
next: {"title": "Primes and Primality Testing", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/prime.md"}
intrinsics:
  - {"name": "Binomial", "signature": "Binomial(n, r): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "Multinomial", "signature": "Multinomial(n, [r₁, ... rₙ]): RngIntElt, [RngIntElt] -> RngIntElt"}
  - {"name": "Factorial", "signature": "Factorial(n): RngIntElt -> RngIntElt"}
  - {"name": "IsFactorial", "signature": "IsFactorial(n): RngIntElt -> BoolElt, RngIntElt"}
  - {"name": "Partitions", "signature": "Partitions(n): RngIntElt -> [ [ RngIntElt ] ]"}
  - {"name": "NumberOfPartitions", "signature": "NumberOfPartitions(n): RngIntElt -> RngIntElt"}
  - {"name": "RestrictedPartitions", "signature": "RestrictedPartitions(n, M): RngIntElt, SetEnum -> [ [ RngIntElt ] ]"}
  - {"name": "RestrictedPartitions", "signature": "RestrictedPartitions(n, k, M): RngIntElt, RngIntElt, SetEnum -> [ [ RngIntElt ] ]"}
  - {"name": "StirlingFirst", "signature": "StirlingFirst(n, k): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "StirlingSecond", "signature": "StirlingSecond(n, k): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "Bell", "signature": "Bell(n): RngIntElt -> RngIntElt"}
  - {"name": "Fibonacci", "signature": "Fibonacci(n): RngIntElt -> RngIntElt"}
  - {"name": "Lucas", "signature": "Lucas(n): RngIntElt -> RngIntElt"}
  - {"name": "GeneralizedFibonacciNumber", "signature": "GeneralizedFibonacciNumber(g0, g1, n): RngIntElt, RngIntElt, RngIntElt -> RngIntElt"}
---

# Combinatorial Functions

<a id="function-binomial-rngintelt-rngintelt"></a>
## `Binomial(n, r): RngIntElt, RngIntElt -> RngIntElt`

The binomial coefficient $n\choose r$.

<a id="function-multinomial-rngintelt-rngintelt"></a>
## `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$.

<a id="function-factorial-rngintelt"></a>
## `Factorial(n): RngIntElt -> RngIntElt`

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

<a id="function-isfactorial-rngintelt"></a>
## `IsFactorial(n): RngIntElt -> BoolElt, RngIntElt`

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

<a id="function-partitions-rngintelt"></a>
## `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.

<a id="function-numberofpartitions-rngintelt"></a>
## `NumberOfPartitions(n): RngIntElt -> RngIntElt`

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

<a id="function-restrictedpartitions-rngintelt-setenum"></a>
## `RestrictedPartitions(n, M): RngIntElt, SetEnum -> [ [ RngIntElt ] ]`

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

<a id="function-restrictedpartitions-rngintelt-rngintelt-setenum"></a>
## `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$.

<a id="function-stirlingfirst-rngintelt-rngintelt"></a>
## `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.

<a id="function-stirlingsecond-rngintelt-rngintelt"></a>
## `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.

<a id="function-bell-rngintelt"></a>
## `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).

<a id="function-fibonacci-rngintelt"></a>
## `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$.

<a id="function-lucas-rngintelt"></a>
## `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$.

<a id="function-generalizedfibonaccinumber-rngintelt-rngintelt-rngintelt"></a>
## `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.
