Thursday, May 23, 2013

permutations and factorials

A permutation is an arrangement of n distinct objects where order matters. For example, if you have a deck with n cards, all the permutations would mean every possible arrangement you could create by shuffling the cards.  For this demonstration, let's use the lowercase letters of the alphabet for our objects.

If we have only one object, there is only one permuation: a

If we have two objects, there are two permuations: ab and ba

Three objects increases the number of permuations to six: abc acb cab bac bca cba

Four objects can be arranged into 24 different permutations.

This number sequence 1, 2, 6, 24, ... is the start of the factorials, which are denoted with an exclamation point.

1! = 1
2! = 2 × 1 = 2
3! = 3 × 2 × 1 = 6
4! = 4 × 3 × 2 × 1 =24
5! = 5 × 4 × 3 × 2 × 1 = 120

Here's why the sequence increases this way. We have the list above of the six permutations of the letters a, b and c. If we add the letter d to the list, let's take a look at any of the three letter permutations, for example cab. It's possible to add in the d to this pattern in four places.

dcab cdab cadb cabd

The d can be put in the first, second, third or fourth position. Since there are six different permutations, we multiply six by four to get twenty four different permutations of four distinct objects.

 The factorials increase very quickly, even faster than exponential growth. 10! = 3,628,800 and if we consider the number of ways to shuffle a standard 52 card deck, 52! is a number with sixty eight digits, 8.0658 × 10^67. A deck with 60 cards would have more different permutations than the current estimate of atoms in the observable universe.

Tomorrow, we'll look at a way to categorize permutations and introduce the numbers in Euler's Triangle.

No comments:

Post a Comment