Binomial and Multinomial theorems

Ya wouldn't think counting would be so hard, but it can be. Back in August I posted about how the number of possibilities changes based on order and replacement. When selecting r items out of n and order isn't important, we get n! ways. To order the set you're selecting from, divide that by (n-r)! since you don't care about the ordering of the items you didn't take, and further divide by r! because you don't care about the order of the things you did take, either. The result is what's termed "n things taken r at a time", typically shortened in speech to just "n choose r" and (since mathematicians aren't big on using words at all if they can help it) this gets written as:



Ok, I expect that most of my math-oriented readers already knew that. A fairly intuitive result arises when you look at the expansion of the polynomial (x+y)ⁿ. Each term in the resulting expansion will be of the form xⁱy^n-i where i can range from 0 to n. The coefficient is just the number of ways you can choose i x's from the possible n terms in the original, that is n choose i. So,



This result is known as the Binomial theorem, mainly because it matches the pmf of the Binomial distribution. That is, if Y is a random variable representing how many times an event occurred in n independent trials with success rate p:



Generalizing this to the multinomial case gives the Multinomial distribution where Y is now an m-dimensional vector of counts for m possible outcomes in n trials giving:



and the Multinomial theorem:



where A is the set of all vectors of non-negative integers where the sum of the components is equal to n.