Combinations

My mind tends to consider extremes. From thinking I have no options to feeling overwhelmed by options, making choices can be challenging. Counting, when possible, calms my mind and simplifies reality. As summer was beginning, I posted about Pascal’s Triangle, a tool for counting combinations. Considering combinations turns our thinking from a set into a variety of possible subsets; a few options may become many.

The triangular arrangement of values is handy for answering questions such as, “How many combinations of 3 things are possible when choosing from a set of 5 things?” Said more simply, “What is the value of 5 choose 3?” The answer sits in the 5th line. (Counting from 0, the 0th line of Pascal’s Triangle is the 1 at the very top.)

Those numbers are the values of 5 choose 0, 5 choose 1, and so on. The fourth number is the value of 5 choose 3. It is 10, the second one. That 10 could have been the end of the story, but I wanted to answer a similar question.

How many distinct goat-pairs are possible if we could choose from 1000 goats?

I did not want to march Pascal’s Triangle out to the 1000th line. (That is when overwhelm would kick in.) I wanted to track a shorter path to a value in the 1000th line, really to any value in any line. I wanted to arrive at a formula for any number in Pascal’s Triangle, a formula for the number of combinations of k objects when choosing from a set with n objects, a formula for n choose k.

(I admit I have had the formula the whole time. But, I have had it as something memorized. I wanted to deepen my relationship to it. I wanted to grow familiar. Maybe you did, too. Now, where were we?)

I followed a path starting with permutations. A permutation is an ordered arrangement; {a,b,c} is distinct from {b,a,c}. Whereas, order does not matter when counting combinations; {a,b,c} is the same as {b,a,c}. Sometimes positions matter (president, vice-president, etc.), and sometimes they don’t.

On a path to 5 choose 3, we started with the number of permutations of a set of 5 objects.

$5!=5\cdot4\cdot3\cdot2\cdot1=120$

One quick division gave us the number of 3-permutations of 5, P(5,3).

$P(5,3)=\frac{5!}{2!}=5\cdot4\cdot3=60$

$P(n,k)=\frac{n!}{(n-k)!}$

A permutation is a rearrangement, so order matters. We are after a formula for the number of combinations of 3 objects if picking from a group of 5.

There are 3! = 3 ⋅ 2 ⋅ 1 = 6 ways to rearrange 3 objects. For each combination of 3, there are six ways to arrange the order. There are six times as many 3-permutations of 5 as there are combinations. This can be written as an equation, if you don’t mind using C(5,3) to reference “5 choose 3”. (You may have also seen the equivalent notation _nC_k.)

$P(5,3)=6 \cdot C(5,3)$

$P(n,k)=k! \cdot C(n,k)$

That is, we can get C(5,3) by dividing P(5,3) by the number of rearrangements.

$C(5,3) =\frac{P(5,3)}{3!}=\frac{P(5,3)}{6}$

Remember, P(5,3) is 5! divided by 2!. C(5,3) results from dividing 5! by both 2! and 3!.

$C(5,3)=\frac{P(5,3)}{3!}=\frac{5!/2!}{3!}=\frac{5!}{2!}\cdot\frac{1}{3!}=\frac{5!}{2!3!}$

It is no mistake the two numbers in the denominator (the bottom of the fraction) add up to 5. One is 5 – 3 and the other is 3. Add those up: 5 – 3 + 3 = 5. We divided by the number of permutations of objects we left out (the (5 – 3 = 2)!), and then we divided by the number of permutations of 3 objects (the 3!). Since order doesn’t matter with combinations, we divide off the numbers of possible rearrangements.

Let’s make sure this equals 10. A calculator (or a few moments of neuron firing) will confirm 5! = 120, 2! = 2, and 3! = 6.

$C(5,3)=\frac{5!}{2!3!}=\frac{120}{2\cdot6}=\frac{120}{12}=10$

If a, b, c, d, and e are the members of our set of 5, what are the 10 combinations of 3 members? Here is a hint. You are looking for distinct combinations; order does not matter. {a,b,c} is the same as {b,a,c}.

One example does not make the proof, but the reasoning we have followed is sound. It does generalize. The path to C(5,3) works for any n and k.

$C(n,k)=\frac{n!}{(n-k)!k!}$

Before using this formula to answer our goat pairing question, check it out on some other values from Pascal’s Triangle. Confirm it works for some of the values in the 6th or 7th line. Be careful checking the 1s. For example, C(6,0) and C(6,6) both equal 1.

How many distinct goat-pairs are possible if we are free to choose from 1000 goats?