How to Derive the Formula for Combinations

How to Derive the Formula for Combinations 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 examining the formula for combinations. The derivation of this formula really just relies upon the multiplication principle. The Multiplication Principle Suppose there is a task to do and 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 after multiplying these numbers together, the number of ways to perform the task is 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 10 to get 30 sundaes. Forming Permutations Now, use 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 forming a permutation of r elements from a total of n. Look at this as a two-step process. First, 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 to order r elements 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. This formula is written with factorial notation. The Derivation of the Formula To recap, P(n,r ), the number of ways to form a permutation of r elements from a total of n is determined by: Forming a combination of r elements out of a total of n in any one of C(n,r ) waysOrdering 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!. Using the formula for permutations P(n,r ) n!/(n - r)!, that can be substituted 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 demonstrated, 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.