How to Derive the Formula for Combinations

Deriving Formula for Combinations
PeopleImages.com / Getty Images

After seeing formulas printed in a textbook or written on the board by a teacher, it is sometimes surprising to find out that many of these formulas can be derived from some fundamental definitions and careful thought. This is particularly true in probability when we examine the formula for combinations. The derivation of this formula really just relies upon the multiplication principle.

The Multiplication Principle

Suppose that we have a task to do and that this task is broken into a total of two steps. The first step can be done in k ways and the second step can be done in n ways. This means that when we multiply these numbers together, we will obtain the number of ways to perform the task as nk.

For example, if you have ten kinds of ice cream to choose from and three different toppings, how many one scoop one topping sundaes can you make? Multiply three by ten to get 30 sundaes.

Forming Permutations

We can now use this idea of the multiplication principle to derive the formula for the number of combination of r elements taken from a set of n elements. Let P(n,r) denote the number of permutations of r elements from a set of n and C(n,r) denote the number of combinations of r elements from a set of n elements.

Think about what happens when we form a permutation of r elements from a total of n. We can look at this as a two-step process. First, we choose a set of r elements from a set of n. This is a combination and there are C(n, r) ways to do this. The second step in the process is that once we have our r elements we order them with r choices for the first, r - 1 choices for the second, r - 2 for the third, 2 choices for the penultimate and 1 for the last. By the multiplication principle, there are r x (r -1 ) x . . . x 2 x 1 = r! ways to do this. (Here we are using factorial notation.)

The Derivation of the Formula

To recap what we have discussed above, P(n,r ), the number of ways to form a permutation of r elements from a total of n is determined by:

  1. Forming a combination of r elements out of a total of n in any one of C(n,r ) ways
  2. Ordering these r elements any one of r! ways.

By the multiplication principle, the number of ways to form a permutation is P(n,r ) = C(n,r ) x r!.

Since we have a formula for permutations P(n,r ) = n!/(n - r)!, we may substitute this into the above formula:

n!/(n - r)! = C(n,r ) r!.

Now solve this the number of combinations, C(n,r ), and see that C(n,r ) = n!/[r!(n - r)!].

As we can see, a little bit of thought and algebra can go a long way. Other formulas in probability and statistics can also be derived with some careful applications of definitions.