Combinatorics: Permutation

This is the first of my series of post on combinatorics, a fascinating field that is used to model many real life scenarios. In my opinion, combinatorics attempts to model real life situations more so than many other topics in mathematics.

I will start with the most basic of concepts and move onto more advanced topics as we progress.

A permutation represents the number of different ordering of elements in a row. For example, the set of elements {a,b,c} has the following six permutations:

abc, acb, bac, bca, cab, cba

As you can see, there are six possible ways to order the set {a, b, c} but is there a mathematical formula to model this process? One can imagine that having to count each possible permutation could become a laborious task. Well in order to model this behavior, consider the following example:

Because we have three positions, each position can be thought of as having a certain number of choices. Position 1 can be occupied by three different choices (the full set), while position 2 can be occupied by only two different choices (full set – element at position one), and position 3 only has one choice.

3 * 2 * 1 = 6

Because of the multiplication rule, we can get the total number of different orderings of elements by just multiplying terms. So the formula for permutation is just n-factorial which makes sense because this expression models the exact process of placing terms until there is only one more term to place. 

n! = n \cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot \ldots \cdot 3 \cdot 2 \cdot 1

The above process of finding the number of permutations works if we want to permute an entire set, but what if we want to find the number of 2-permutations in a set of three. This would represent the number of different ways the entire set can be grouped together in sets of two. If we were to find the number of 2-permutations of our original set {a, b, c} it would look as follows:

ab, ba, ac, ca, bc, cb

Once again we come to the number six which is kind of interesting if you think about it. The number of different ways to arrange three terms in a set of three is identical to the number of ways to order two terms. This type of permutation is called an r-permutation and it represents the number of ways a set of r elements can be arranged from a greater set of n elements where 1 \leq r \leq n Can you take a minute to think about the last restriction we placed on r? Well obviously r cannot be a fraction (no fractions of elements), and it has to be less than n, you can’t have a set of n+1 elements if there are only at most n elements in a set.

The formula for r-permutations is as follows:

P(n,r) = r-permutations = \frac {n!}{(n-r)!}

This formula can be easily understood if you envision a row if terms getting ready to be multiplied together in order to get the full permutation and then dividing out the number of terms that will leave only the first r terms. In the next post I will give more examples and talk less about theory.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s