Combinations

After understanding Permutations I decided to learn about Combinations. Here is the definition

A collection of things, in which the order does not matter.

In other words “A Permutation is an ordered Combination”. The formula is

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

The formula did not make a lot of sense to me. I started to experiment with a simple example

In how many ways can a 2 person committee be chosen from a group of 4 people where the order in which we chose the 2 people doesn’t matter.

I constructed the following table.

1st Person 2nd Person
Alice Bob
Carole
Dan
Bob Alice
Carole
Dan
Carole Alice
Bob
Dan
Dan Alice
Bob
Carole

If you add the total number of names in the 2nd Person column it comes to 12 possible ways. If you look at them closely Alice – Bob and Bob – Alice is counted twice. Remember from the definition that the order does not matter. Hence this pair should be counted only once. From the table given below you can clearly see that we have double counted each pair. Hence the total possible ways is 12/2 = 6

Alice Bob
Bob Alice
Alice Carole
Carole Alice
Alice Dan
Dan Alice
Bob Carole
Carole Bob
Bob Dan
Dan Bob
Carole Dan
Dan Carole

The difference between Permutations and Combinations formula is

P(n,r) = n! / (n - r)!
C(n,r) = n! / r! * (n - r)!

The only difference is dividing it r! But Why?

In the above example r = 2 and there are 2 ways to chose them.
i.e. If we have A and B then you can have AB and BA. This is nothing but 2!

If r = 3 then we have ABC,ACB,BCA,BAC,CAB,CBA there are 6 ways. This is nothing but 3!

If we generalize this for r we will get r!

Hence to compensate for r! over counting we divide by it.

In real life there are lots of problems involving Combinations.

Imagine you have an account in Facebook. If you have 99 friends in your network(including you it will be 100). If everyone is connected to everyone else(you cannot connect to yourself). How many connections will there be in total?

Believe me this is a combination problem. I have rewritten the problem to match the example problem

In how many ways can a 2 person committee be chosen from a group of 100 people where the order in which we chose the 2 people doesn’t matter.

C(100,2) = 100! / 2! * (100 - 2)!
C(100,2) = 100! / 2! * 98!
C(100,2) = 100 * 99 / 2
C(100,2) = 9900 / 2

C(100,2) = 4950 connections

Combinations = Permutations – Order