---
title: "Combinatorial Functions"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/EnumerativeCombinatorics/combinatorics.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/EnumerativeCombinatorics/combinatorics.md"
part: "Combinatorics"
chapter: "Enumerative Combinatorics"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Enumerative Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/EnumerativeCombinatorics/index-enumerative-combinatorics.md"}
prev: {"title": "Introduction", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/EnumerativeCombinatorics/introduction.md"}
next: {"title": "Subsets of a Finite Set", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/EnumerativeCombinatorics/subsets.md"}
intrinsics:
  - {"name": "Factorial", "signature": "Factorial(n): RngIntElt -> RngIntElt"}
  - {"name": "NumberOfPermutations", "signature": "NumberOfPermutations(n, k): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "Binomial", "signature": "Binomial(n, r): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "Multinomial", "signature": "Multinomial(n, [r₁, ... rₙ]): RngIntElt, [RngIntElt] -> RngIntElt"}
  - {"name": "Fibonacci", "signature": "Fibonacci(n): RngIntElt -> RngIntElt"}
  - {"name": "Catalan", "signature": "Catalan(n): RngIntElt -> RngIntElt"}
  - {"name": "Lucas", "signature": "Lucas(n): RngIntElt -> RngIntElt"}
  - {"name": "GeneralizedFibonacciNumber", "signature": "GeneralizedFibonacciNumber(g0, g1, n): RngIntElt, RngIntElt, RngIntElt -> 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": "EulerianNumber", "signature": "EulerianNumber(n, r): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "HarmonicNumber", "signature": "HarmonicNumber(n): RngIntElt -> FldRatElt"}
  - {"name": "BernoulliNumber", "signature": "BernoulliNumber(n): RngIntElt -> FldRatElt"}
  - {"name": "BernoulliApproximation", "signature": "BernoulliApproximation(n): RngIntElt -> FldPrElt"}
  - {"name": "BernoulliPolynomial", "signature": "BernoulliPolynomial(n): RngIntElt -> RngUPolElt"}
---

# Combinatorial Functions

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

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

<a id="function-numberofpermutations-rngintelt-rngintelt"></a>
## `NumberOfPermutations(n, k): RngIntElt, RngIntElt -> RngIntElt`

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

<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-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$, $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-catalan-rngintelt"></a>
## `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)$.

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

<a id="function-stirlingfirst-rngintelt-rngintelt"></a>
## `StirlingFirst(n, k): RngIntElt, RngIntElt -> RngIntElt`

The Stirling number of the first type, $[{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, $\{{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-euleriannumber-rngintelt-rngintelt"></a>
## `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}$)

<a id="function-harmonicnumber-rngintelt"></a>
## `HarmonicNumber(n): RngIntElt -> FldRatElt`

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

<a id="function-bernoullinumber-rngintelt"></a>
## `BernoulliNumber(n): RngIntElt -> FldRatElt`

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

<a id="function-bernoulliapproximation-rngintelt"></a>
## `BernoulliApproximation(n): RngIntElt -> FldPrElt`

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

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