Combinatorics: combinations and permutations

Combinatorics is a branch of mathematics focused on the number of ways structures can be arranged. This page looks at the formulae for permutations and combinations and efficient ways to compute them, including an efficient way to compute the factorial of a number using binary splitting. It gives some Python code to compute the formulae, and introduces a command-line utility bdCombinat.exe based on our BigDigits library.

Permutations and combinations

For a set of $n$ distinct items, a permutation is an ordered selection of $k$ items, and a combination is an unordered selection of $k$ items.

The number of permutations of $k$ items from $n$ items is written as ${}^nP_k$ or $P(n,k)$, read “$n$ permute $k$”. The formula is \[ {}^nP_k = \frac{n!}{(n-k)!} \] where $n!$ denotes the factorial of $n$ defined as the product of all integers less than or equal to $n$: \[ n! = 1 \times 2 \times 3 \times \ldots \times n \] with $0! = 1$ by definition.

The number of combinations of $k$ items from $n$ items is written as ${}^nC_k$ or $\binom{n}{k}$, read “$n$ choose $k$”. \[ {}^nC_k = \binom{n}{k} = \frac{n!}{k!(n-k)!} \]

Aside: $\binom{n}{k}$ is the binomial coefficient, which appears in the binomial theorem for $(a + b)^n$. The symbols ${}^nC_k$ and $\binom{n}{k}$ represent the same value.

Note that the number of different permutations of $n$ elements is ${}^nP_n = n!$ and that ${}^nC_k = \frac{{}^nP_k}{k!}$.

Computing the factorial

A naive and inefficient method to compute the factorial is

def factorial(n):
  if n <= 1:
    return 1
  return n * factorial(n - 1)

This becomes slow very quickly, even for small values of $n$.

Binary Splitting Method for Computing Factorials

One highly efficient method to compute the factorial of large integers is the binary splitting method. This recursively divides the range of multiplication into smaller, balanced pairs, reducing the number of large multiplications.

Binary splitting defines a product function for $a \ge b$ \[ Pr(a,b)=(b+1)\times(b+2)\times\ldots\times a= \frac{a!}{b!} \] and recursively computes \[ Pr(a,b)=Pr(a,m)\times Pr(m,b), \text{ where } m = \left\lfloor \frac{a + b}{2} \right\rfloor, \] until the range $a-b$ becomes small ($\leq 3 $), at which point it is computed directly. To calculate $ n! $, compute $ Pr(n, 0) $. Here is a formal description of the algorithm.

\begin{algorithm}
\caption{Factorial}
\begin{algorithmic}
\FUNCTION{Factorial}{$n$}
    \RETURN\CALL{Product}{$n, 0$}
\ENDFUNCTION
\FUNCTION{Product}{$a, b$}
    \STATE $d = a - b$
    \IF{$d = 0$}
		\RETURN $1$
	\ELIF{$d=1$}
		\RETURN $a$
	\ELIF{$d=2$}
		\RETURN $a \times (a-1)$
	\ELIF{$d=3$}
		\RETURN $a \times (a-1) \times (a-2)$
	\ENDIF
	\STATE $ m = \left\lfloor \frac{a + b}{2} \right\rfloor $
	\RETURN \CALL{Product}{$a,m$} $\times$ \CALL{Product}{$m,b$}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

In Python

def factorial_binary_split(n):
    def pr(a, b):
        d = a - b
        if d == 0:
            return 1
        if d == 1:
            return a
        if d == 2:
            return a * (a - 1)
        if d == 3:
            return a * (a - 1) * (a - 2)
        m = (a + b) // 2
        return pr(a, m) * pr(m, b)
    return pr(n, 0)

Python has the advantage that it will cope with large integers automatically, unlike most languages that will overflow and give an invalid result as the numbers get too large. See our bdCombinat.exe program below.

Efficient Algorithm for Computing Binomial Coefficients

The most efficient general-purpose algorithm for computing binomial coefficients $ \binom{n}{k} $ is based on the identity: \[ \binom{n}{k} = \frac{n \cdot (n-1) \cdot \ldots \cdot (n-k+1)}{k \cdot (k-1) \cdot \ldots \cdot 1} = \frac{n}{1} \cdot \frac{n-1}{2} \cdot \frac{n-2}{3} \cdot \ldots \cdot \frac{n-k+1}{k} \] Use symmetry $\binom{n}{k} = \binom{n}{n-k}$ to minimise $k$, ensuring $k\le n/2$. Note that there are exactly $k$ items in both the numerator and the denominiator.

In Python code

def binomial_coefficient(n, k):
    if k > n - k:
        k = n - k  # Use symmetry
    result = 1
    for i in range(k):
        result = result * (n - i) // (i + 1)
    return result

To understand the identity above, consider the full formula for the example of $\binom{10}{4}$ and note how the 6 items of $(n-k)!$ in the denominator cancel out the last 6 items of $n!$ in the numerator, leaving just 4 terms that can be computed as fractions. \[ \require{enclose} \frac{n!}{k!(n-k)!} = \frac{10!}{4!(10-4)!} = \frac{10\cdot 9\cdot 8\cdot 7\cdot \enclose{horizontalstrike}{6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}}{(1\cdot 2\cdot 3\cdot 4)(\enclose{horizontalstrike}{6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1})} \]

Computing number of permutations

The formula for $n$ permute $k$ reduces to \[ {}^nP_k = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdot \ldots \cdot (n-k+1) \]

In Python code

def permutations(n, k):
    if k > n or k < 0:
        return 0
    result = 1
    for i in range(k):
        result *= (n - i)
    return result

bdCombinat: A command-line utility to compute combinatorics

bdCombinat.exe is a standalone command-line program that computes the values of factorial(n), binomial(n,k) and permutations(n,k) using arbitrary large nonnegative integers. It provides simple arithmetic operators: addition (+), subtraction (-), multiplication (*), division (/), and parentheses for grouping (e.g., (2+3)*4). Examples:

> bdCombinat factorial(52)
factorial(52)=80658175170943878571660636856403766975289505440883277824000000000000

> bdCombinat binomial(52,13)
binomial(52,13)=635013559600

> bdCombinat -q binomial(52,13)*binomial(39,13)*binomial(26,13)*binomial(13,13)
53644737765488792839237440000

> bdCombinat permutations(52,13)
permutations(52,13)=3954242643911239680000

> bdCombinat permutations(52,13)/factorial(13)
permutations(52,13)/factorial(13)=635013559600

bdCombinat.exe is written in ANSI C using our BigDigits library. For more details and download, see bdCombinat: A command-line utility to compute combinatorics.

Contact us

To contact us or comment on this page, please send us a message.

This page first published 26 March 2026. Last updated 26 March 2026