What's behind binomial coefficients?

Tivadar Danka small portrait Tivadar Danka
Binomial coefficients as the ratio of variations and permutations

Understanding math will make you a better engineer.

So, I am writing the best and most comprehensive book about it.

Binomial coefficients are one of the most ubiquitous quantities in mathematics, used in every field from combinatorics to probability.

Behind their formula, there is a principle that reveals a deep connection between combinations, variations, and permutations.

Let's explore it!

By definition, the binomial coefficients describe the number of ways one can select k\textstyle k elements from a set of n\textstyle n elements:

(nk)={S{1,2,,n}:S=k}.\begin{align*} \binom{n}{k} = \big| \big\{ S \subseteq \{1, 2, \dots, n\}: |S| = k \big\} \big|. \end{align*}

How does this definition yield the famous factorial formula? We'll see a special case to shed some light on the question!

Suppose that we have a set of 5 elements and want to know how many of its subsets have exactly 3 elements. A subset is called a combination, and the order of elements doesn't matter.

Three-element subsets of a set with five elements

Counting combinations seems complicated, so let's make the problem a bit more special: let's count the 3-element tuples, where the ordering is important! Such a tuple is called a variation.

There are 543 5 \cdot 4 \cdot 3 possible variations, as we have

  • 5 options for the 1st position,
  • 4 remaining options for the 2nd position,
  • and 3 remaining options for the 3rd position.


Now let's count variations again, a bit differently this time!

A variation can be obtained by first selecting a subset, then putting its elements into order. As there are 3!3! orderings (= permutations) per subset and (53) \binom{5}{3} subsets in total, we have 3!(53)3! \binom{5}{3} variations. (The expression (nk) \binom{n}{k} is read as "n\textstyle n over k\textstyle k".)

If you want to visualize this process, check out this illustration below.

Counting variations by selecting subsets and counting individual permutations

Since we have counted variations in two different ways, the results must be equal. Thus, we have

3!(53)=5!(53)!. 3! \binom{5}{3} = \frac{5!}{(5 - 3)!}.

This is true in the general case as well: the number permutations times combinations equals the number of variations.

Permutations times combinations equal variations

By dividing with k!k!, we obtain the formula used to compute binomials. (Well, up to certain computational limitations. Factorials blow up really fast, and dividing two huge numbers is not a good idea.) That is, we have

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

So, why is the combinatorial definition useful?

For one, think about the famous binomial theorem:

(a+b)n=k=0n(nk)akbnk.(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n - k}.

How would you prove it? The simplest way is to use combinatorics and count the number of ways each a-b term can be obtained from the product, which is given by the binomial coefficients.

Having a deep understanding of math will make you a better engineer.

I want to help you with this, so I am writing a comprehensive book that takes you from high school math to the advanced stuff.
Join me on this journey and let's do this together!