Introduction to Discrete Mathematics

Recall that \(\binom{n}{k}\) counts the number of subsets of size \(k\) taken from a set of size \(n\text{.}\) Each \(\binom{n}{k}\) is called a binomial coefficient, which likely seems like a strange name. Why are these numbers called binomial coefficients? In general a binomial is just a polynomial with two terms. Let’s see what we can discover.

This time the coefficients are \(1,3,3,1\text{,}\) which is the next row of Pascal’s Triangle. What’s going on here?

Consider the expansion of \((x+y)^n\text{.}\) The key observation is that before commuting factors and collecting like terms, the terms in the expansion consist of all possible products where we choose either \(x\) or \(y\) from each factor. Each such term will consist of \(n\) letters. In particular, if there are \(k\) copies of \(x\) in a term, there will be \(n-k\) copies of \(y\) (and vice versa). Moreover, every possible configuration of \(k\) copies of \(x\) (i.e., location of the \(x\)’s in the term before doing any commuting with \(x\) and \(y\)) will be represented. This means there will be precisely \(\binom{n}{k}\) many terms with \(k\) copies of \(x\) (and \(n-k\) copies of \(y\)). Thus, when we commute and then collect like terms, the coefficient on \(x^ky^{n-k}\) will indeed be \(\binom{n}{k}\text{.}\) This leads us to the following remarkable fact, known as the Binomial Theorem.

In light of the Binomial Theorem, the binomial coefficients are the positive integers that occur as coefficients in the expansions of powers of binomials. Said another way, the coefficients in the expansion of \((x+y)^n\) correspond to the entries in the \(n\)th row of Pascal’s Triangle.