Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm currently studying some combinatorics and I'm trying to understand combinations ${{n}\choose{r}}$ conceptually. I don't have trouble understanding permutations (n!) and r-permutations P(n,r) because I can draw out a possibility tree and see actual choices being cancelled out. Can anyone provide a good example or way to understand combinations. Basically, why are you preforming the following division $\frac{P(n,r)}{r!}$

share|improve this question

1 Answer 1

up vote 4 down vote accepted

It's probably easier to understand the other way round. Suppose that $C(n,k)$ denotes the number of $k$-element subsets of a set of $n$ elements. Now you pick one of those $k$-element subsets, all in a lump, and decide to list its elements in some order. There are $k!$ different orders. You can pick the first element in the list in $k$ ways. Having done that, you have $k-1$ choices for the second element in the list. And so on, down to the last element on the list, in which you have no choice, since there's only one element left in the set.

Thus, the number of $k$-element lists (permutations) that you can choose from the $n$-element set is $C(n,k)\cdot k!$. But you already know that there are $P(n,k)$ such permutations, so $C(n,k)\cdot k!=P(n,k)$, and therefore $$C(n,k)=\frac{P(n,k)}{k!}\;.$$

The calculation of $P(n,k)$ that you're familiar with counts these permutations one at a time, without paying attention to the fact that many of them are just rearrangements of others. The calculation above first isolates a particular set of $k$ of the $n$ objects and counts the number of permutations of that set: there are $k!$. To get the total $P(n,k)$, therefore, we just multiply the number of $k$-element subsets, $C(n,k)$, by $k!$. If we already know $P(n,k)$, as you do, this reasoning can be inverted to get $C(n,k)$ from $P(n,k)$, by dividing by $k!$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.