Last updated May 30, 2025
While investigating how many hex codes have digits adding to a given sum, something I heard mentioned a lot were generating functions. I didn't really understand any explanations of them until I found this video and its sequel. Seeing how generating functions are used reminded me of something I'd wondered: The "choose function" \(\binom{n}{k}\) is called a binomial coefficient because it's the \(k^{\text{th}}\) coefficient of (\(a+b)^n\) expanded. What do the coefficients of a binomial raised to some power have to do with picking items from a set, though?
I see some of the correlation after doing an expansion by hand, for example:
\[\begin{equation}\begin{split} (a+b)^3 &= (a+b)(a+b)(a+b) \\ &= a^3 + a^2b + a^2b + a^2b + ab^2 + ab^2 + ab^2 + b^3 \\ &= a^3 + 3a^2b + 3ab^2 + b^3 \end{split}\end{equation}\]
When multiplying out \((a+b)(a+b)(a+b)\), you are finding all the ways to choose one of \(a\) or \(b\) from each of the three sets of parentheses. There is one way to choose \(a\) from all three (by never choosing \(b\)), three ways to choose \(a\) twice and \(b\) once, three ways to choose \(a\) once and \(b\) twice, and one way to choose \(b\) all three times. Thus, if you have three items, there is one way to choose none or all of them: \(\binom{3}{0} = \binom{3}{3} = 1\). Likewise, there are three ways to choose either one or two of the items: \(\binom{3}{1} = \binom{3}{2} = 3\).