What is the formula for combinations, and why are they called binomial coefficients?

"And in general, that’s all we have to do. To find the number of combinations of k things taken from a total of n things we have: n choose k = n! / ((n − k)! k!) combinations. This pattern, too, comes up so often that mathematicians have invented (yet) another special notation for it. It looks a bit strange at first, almost like a fraction without a horizontal bar: (n choose k) = n! / ((n − k)! k!). This is pronounced “n-choose-k”. Again, examples abound. How many different 5-card poker hands are there? Answer: (52 choose 5), since it doesn’t matter what order you’re dealt the cards, only which five cards you get. If there are 1024 sectors on our disk, but only 256 cache blocks in memory to hold them, how many different combinations of sectors can be in memory at one time? (1024 choose 256). If we want to choose 4 or 5 of our top 10 customers to participate in a focus group, how many different combinations of participants could we have? (10 choose 4) + (10 choose 5), since we want the number of ways to pick 4 of them plus the number of ways to pick 5 of them. And for our late night movie channel, of course, there are (500 choose 4) possible movie lineups to attract audiences, if we don’t care which film is aired at which time. The “n-choose-k” notation (n choose k) has another name: values of this sort are called binomial coefficients. This is because one way to generate them, believe it or not, is to repeatedly multiply a binomial times itself (or, equivalently, take a binomial to a power.) A binomial, recall, is a polynomial with just two terms: x + y. The coefficients for this binomial are of course 1 and 1, since “x” really means “1 · x.” Now if we multiply this by itself, we get: (x + y) · (x + y) = x² + 2xy + y², the coefficients of the terms being 1, 2, and 1. We do it again: (x² + 2xy + y²) · (x + y) = x³ + 3x²y + 3xy² + y³ to get 1, 3, 3, and 1, and do it again: (x³ + 3x²y + 3xy² + y³) · (x + y) = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴ to get 1, 4, 6, 4, and 1. At this point you might be having flashbacks to Pascal’s triangle, which perhaps you learned about in grade school, in which each entry in a row is the sum of the two entries immediately above it (to the left and right), as in Figure 6.1. The first six rows are: 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1; 1 5 10 10 5 1. Now you might be wondering where I’m going with this. What do fun algebra tricks have to do with counting combinations of items? The answer is that the values of (n choose k) are precisely the coefficients of these multiplied polynomials. Let n be 4, which corresponds to the last polynomial we multiplied out. We can then compute all the combinations of items taken from a group of four: (4 choose 0) = 1, (4 choose 1) = 4, (4 choose 2) = 6, (4 choose 3) = 4, and (4 choose 4) = 1. In other words, there is exactly one way of taking no items out of 4 (you simply don’t take any). There are four ways of taking one item out of 4 — you could take the first, or the second, or the third, or the fourth. There are six ways of taking two items out of four; namely:"