What's behind binomial coefficients?
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 elements from a set of elements:
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.
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 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 orderings (= permutations) per subset and subsets in total, we have variations. (The expression is read as " over ".)
If you want to visualize this process, check out this illustration below.
Since we have counted variations in two different ways, the results must be equal. Thus, we have
This is true in the general case as well: the number permutations times combinations equals the number of variations.
By dividing with , 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
So, why is the combinatorial definition useful?
For one, think about the famous binomial theorem:
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.