Derive the formula for the number n k of options to chose k

Derive the formula for the number (n k) of options to chose k objects out of n.

Solution

The mathematics we use in calculating the number of combinations of, say, 6 things from 49 comes under the general heading of Permutations and Combinations. Most textbooks in intermediate algebra or in basic probability will have chapters covering this topic, and you should consult such a book to find the proofs of the formulae employed. They are not difficult to understand and I will give a brief outline below. PERMUTATIONS If we have, say, 10 different objects (e.g. letters a - j of the alphabet), how many different \'words\' could be made using 4 of the letters? In this context we simply want 4 letters, such as bghc; they do not need to spell a known English word. But the ORDER of the letters does matter, so hgcb is different from bghc. With 10 letters to choose from we can select the first letter in 10 ways. We are now down to 9 letters, so the second letter can be chosen in 9 ways, then the third letter in 8 ways, and the 4th letter in 7 ways. The total number of ways of arranging 4 letters chosen from 10 is 10 x 9 x 8 x 7 = 5040. We use the symbol nPr to represent the number of ways of arranging r things chosen from n different things, so here we have 10P4 = 5040 In ascii notation this is sometimes written P(n,r), so for this problem we have P(10,4) = 5040 We can also express P(10,4) using factorials. Factorial notation uses the exclamation mark ! to show that it is a factorial, where for example 5! = 5 x 4 x 3 x 2 x 1 = 120 10! = 10 x 9 x 8 x ... x 3 x 2 x 1 = 3628800 You will notice that factorials get very big very quickly. 10! 10 x 9 x 8 x 7 x 6! Using this notation P(10,4) = ----- = ------------------- = 5040 6! 6! n! The general formula for P(n,r) is ------ (n-r)! COMBINATIONS These are closely allied to permutations except that the order does not matter. For example in our problem of 4 letters chosen from 10 letters, the 4 letters hgcb are the SAME combination as bghc. To find the number of combinations we use the fact that the number of permutations of 4 letters from 10 is P(10,4), but now EVERY permutation can be rearranged in 4! = 24 ways without giving rise to a different combination. So the number P(10,4) is too large by a factor of 4! when we calculate the number of combinations. This leads to the following formula for the number of combinations: 10! C(10,4) = ------- = 210 4! 6! The general formula for the number of combinations of r things chosen from n different things is n! C(n,r) = --------- r!(n-r)! We can now answer the question you started with. How many ways can 6 numbers be chosen from 49 numbers? (The order you choose the numbers does not matter). Here we use the combination formula and get: 49! C(49,6) = --------- = 13,983,816 6! 43! This is not the 32 million that you quoted. The second question was the number of ways of choosing 10 numbers from 35. This is given by: 35! C(35,10) = --------- = 183,579,396 10! 25! So now we are up to nearly 184 million possible combinations.