Think about how binomial coefficients arise. Suppose you want to expand out the product (a+b)^n = (a+b)(a+b)...(a+b) into a polynomial. If you just expanded

Think about how binomial coefficients arise. Suppose you want to expand out the product (a+b)^n = (a+b)(a+b)...(a+b) into a polynomial. If you just expanded it out, without grouping terms, there would be 2^n terms. Each of these terms would be obtained by choosing either a or b from the first factor; a or b from the second factor; ...; a or b from the nth factor, and then multiplying those a's and b's together. If you then group the terms, you'll find that the coefficient of the a^r b^(n-r) term will be nCr, the binomial coefficient. Thinking back to the a-or-b selection process, note that each a^r b^(n-r) term corresponds to a path where you chose r a's and (n-r) b's. Now imagine that the n factors correspond to forming a subset of a set of n objects, where choosing a at position i means "include the i'th object in the subset" and choosing b at position i means "exclude the i'th object from the subset". Thus, each distinct choice of a's and b's defines a distinct subset of the n objects. Choosing r a's and (n-r) b's means forming a subset of r out of the n elements. Hence the interpretation of nCr as the number of combinations of r elements out of a total of n elements.