Combinations

Combinations can be thought of as a layer on top of permutations. They are employed to solve problems of counting how many selections can be made from a particular group. For example, say I wanted to draw 5 marbles from a bag of 15, how many combinations of marbles could I draw?

To answer this question we have to count how many ways we can draw all 15 marbles and then divide that by the number of ways we can draw 10 marbles. This can be written mathematically as:

n!/(n-r)!

so that is

15! / (15-5)!

=

15! / 10!

=

15*14*13*12*11

= 360,360 ways to draw 5 marbles from the bag of 15.

Permutations

We are going to take a break from proofs today to look at some methods of counting in math. Today we will cover Permutations.

A permutation is simply how many possible arrangements there are of any elements in a set. For example, let say we have a set with A,B,C,D in it. How many ways can we order ABCD?

ABCD, ADCB, ACDB, BADB,...and so on. Well, instead of listing every combination out we can use a permutation to count them. A permutation is defined by n factorial (n!)

n! = n(n-1)!
so for example 5!= 5 * 4 * 3 * 2 * 1

And for the ABCD problem we need to take 4! which is 4*3*2*1 = 24

So there are 24 possible permutations.

An interesting facet with permutations is that the numbers tend to rise quite quickly:
5!=120
6!=720
7!=5040
8!=40,320
9!=362,880
10!= 3,362,800

So if we tried to order ABCDEFGHIJ we would get over 3 million permutations!