Q: How do I count the number of ways of picking/choosing/taking k items from a list/group/set of n items when order does/doesn’t matter?

Mathematician: Suppose that we have a list containing three items, {A,B,C}, and we want to know how many different ways there are of choosing two items from this list. If we care about the order that items are selected from the list, then the possibilities are

{A,B}, {A,C}, {B, A}, {B, C}, {C,A}, {C,B}

(where {A,B} here means that we’ve selected item A and then item B from the list {A,B,C} ) so the answer is that there are six possible ways of choosing two items out of three. If on the other hand we don’t care about what order the items were selected in (so {A,B} is considered the same as {B,A}) then all the possible unique arrangements are

{A,B}, {A,C}, {B, C}

so the answer is that there are three possible ways of choosing two items out of three when order doesn’t matter.

When there are small numbers of items, it isn’t difficult to just write down all the possible combinations (when order doesn’t matter) or permutations (when order does matter). But what do we do when there are larger numbers of items? For example, it turns out there are 15,504 different ways to choose 5 items out of 20 (when the order of items selected doesn’t matter), far too many to write down. In cases like these we want to use a formula that depends only on n (the number of items in our set) and k (the number of items we will be selecting from it) that can quickly give us the answer we need. Let’s see if we can figure out what this formula should be.

For the time being we are going to assume that the order we select items in does matter (so the selection of A followed by the selection of B is not the same as the selection of B followed by the selection of A). Now notice that since we have n items in total, there are n choices for the first item that we pick. Once we’ve chosen the first item, there are n-1 items left in our list, so for our second selection we have n-1 possible choices. The number of total possible ways of choosing the first two items is therefore n * (n-1) because for each of the n first items we could choose we have n-1 second items possible. Now, for the 3rd item selected there are n-2 items left in the list (since we’ve already used up 2 items out of a total of n), which means that in choosing three items there are a total of n (n-1) (n-2) possible permutations. This pattern continues for each of the k items we are choosing, so that we find that the total number of ways of choosing k items is

(n)(n-1)(n-2)…(n-k+2)(n-k+1)

which can be written using the factorial function as

Remember however that in this analysis the order of the items selected made a difference. If what we are interested in is the number of ways of choosing k items from a list of n such that order does NOT matter (i.e. in each selection all that matters is which items are in that selection, not which order those items were chosen) then we have to adjust our formula somewhat by making the following considerations.

If we are going to be choosing k items, then how many different orderings of those k items exist? Well, there are k possible choices for which item goes first. After we have chosen which one goes first, there are k-1 that can go second. This leads to a total number of k*(k-1) arrangements for the first two items. Then, there are k-2 items to choose from for the 3rd item, and so on, leading to k*(k-1)*(k-2)*(k-3)*…*3*2*1 total arrangements. Note though that this is just the same as the definition of k factorial, so we just write k! to represent the expression. Now, we observe that the number of ways to choose k items from n such that order matters is k! times bigger than the number of ways to choose k items from n where order doesn’t matter. The reason is because for each of the ways we can make a selection of k items when order doesn’t matter, there are k! different orderings in which we could have chosen each of our k selected items. Hence, since there are   possible choices when order matters, but this is k! times greater than the case when order doesn’t matter, we have that the total number of different possible selections when order doesn’t matter is just given by

This happens to be the definition of what is called the “choose function”, sometimes known as the binomial coefficient or pascal’s triangle, which mathematicians write as .

Now, to put our work into action. Let’s suppose that we have ten salad ingredients (peppers, avocado, pears, walnuts, beans, peas, corn, croutons, soy beans and olives) and we want to know how many distinct salads can be made using just two ingredients. Well, if our salad is mixed up, then it doesn’t matter what order we put the ingredients in, so this is equivalent to the problem of asking how many ways there are to select two items from a list of ten when order doesn’t matter. This is given by

= = = =

so there are 45 two ingredient salads you can make from ten ingredients. How many distinct salads can you make that have anywhere from 2 to 10 of our ingredients? The answer is just the number of two ingredient salads plus the number of three ingredients salads plus the number of four ingredient salads, etc. up to the number of ten ingredient salads. In mathematical notation, this is

+ + + …  + +

= 45 + 120 + 210 + 252 + 210 + 120 + 45 + 10 + 1  = 1013

which is simply the number of salads with two or more ingredients that could be made from our ten ingredients.