• Introduction
• Iteration
  • Summation
  • Product
  • Set Notation
  • Nested Iteration
  • Conditions on indices
  • Union and Intersection
  • General Iteration
• General Symbols
  • Cases
  • Function Composition
  • Set Containment
  • Kronecker
• Operations
  • Factorial
  • Binomial
• Differentiation
  • Derivative
  • Partial Derivative
  • Gradient

Binomial coefficient $\binom{n}{k}$

The binomial coefficient comes up in various combinatorics related formulas. It tells you the following: If you have n different objects and you take out k of them (without putting any back), how many different combinations of objects can you pick out (disregarding the order). n and k must both be non-negative integers and $k\leq n$. For $k>n$ $\binom{n}{k} = 0$.

Be careful not to confuse this one with fractions or vectors/matrices. It is just two numbers on top of each other inside brackets.

It is defined the following way:

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

This formula is generally most useful for proofs, less so for computation. While you could implement it directly using the factorial formula, this will quickly break due to the extreme growth of the factorial, which will overflow integer variables quickly. Using floats might be tempting, but they will become imprecise pretty quickly and give you wrong results.

We won't go too far into the derivation here, but we can observe that $n!$ and $(n-k)!$ share the first $n-k$ product terms and can thus be cancelled out! This leaves

$$\frac{n(n-1)(n-2)\cdots(n-k +1)}{k(k-1)(k-2)\cdots 1}$$

One can write that as a product (see the product symbol section)

$$\binom{n}{k} = \prod\limits_{i=1}^k \frac{n+1 -i}{i}$$

See for example Wikipedia

Furthermore, there is a symmetry property that $\binom{n}{k} = \binom{n}{n-k}$. So we can choose the lesser of $k$ and $n-k$ to reduce the work we have to do.

This allows for a pretty simple computation. If a binomial coefficient function exists in your language, it is good to use it, as they have probably/hopefully taken care of range issues like this.

Code: