MarbleMice.com

Repost from old site.
Having a basic understanding of permutations and combinations can be a very useful for programmers as it lets you quickly determine whether an easy to program brute force method will work within a reasonable time or that you need to spend time developing better algorithms to account for the large number of possible situations. These decisions are very problem specific so I will not be addressing them here. What I want to try to do in this article is arm you with knowledge and understanding of permutations and combinations so you can make informed decisions when you need to or at the very least know whether your brute force method will finish today or next year.

Permutations
Basically with permutations we ask the question given a set of items how many different ways can we order them. Permutations take the position into account when looking for a unique ordering; each unique ordering is called a permutation.

Let say we have 3 different characters, a,b and c. What is the total number of possible permutations. The answer is 6 ‘abc’, ‘acb’, ‘cab’, ‘bac’, ‘bca’, ‘cba’. That is fairly simple to figure out but what happens if we use the whole alphabet? To work this out we have to calculate the factorial of the number of items being considered, in our case we need to work out the factorial of 26. We write factorial of a number using an exclamation mark as an abbreviation. Thus

That is pretty easy to comprehend as in the first position we can place any of the 26 characters. In the second position we can only place 25 as we have used one in the previous position. So we have 26 multiplied by the 25 of the second position and so on to get the total number of permutations.

As you can the number of permutations gets large very quickly.
Lets take all the letters and put them into 2 classes or groups, one for the vowels and the other for the consonants. A class can only appear once for any given position. How do we work out the number of possible permutation. The formula for this is

Where n is the total number of items and the numbered n’s are the number of items in each class. You can rationalise this formula in your head by observing that grouping of items into classes remove possible combinations and the bigger the groups the proportionately more possible permutations are removed. Taking our 3 letter example and say grouping ‘a’ and ‘b’ into one class and ‘c’ into another we find that the valid combinations are ‘abc’, ‘acb’ and ‘cba’.

Often with permutation you want to take a few elements from a set and work out all the possible permutation you can get with this given number of items. The answer depend on whether you allow the same item to be place at different position in you permutation. For instance is ‘aa’ a valid permutation generated by taking two items from out 3 character example. If so then calculating the number of permutation is easy, each position can have n different items place in them, n being the number of items. If we assume we are taking k items for each permutation then the total number of permutations is

By not allowing repeated items in a permutation we limit the number of permutations slightly. You have to take the factorial of n but only go down to n-k+1 as you are limiting the number of items you are taking, thus we get

If you expand out the formula on the right you will see it is the same as the formula on the left once terms start to cancel.

Combinations
Combinations differ from permutations by ignoring the positions that the characters appear in the sequence, ‘cab’, ‘abc’ and so on are all the same combination. This greatly reduced the number of possible combinations. If you have 3 letter and ask the question how many different combinations are there then the answer is one. But if you have 5 letters and ask the question how many different 3 letter combination can be generated we have to work it out. The first thing to decide is whether or not to you allow repeated items e.g. Given the five letter a,b,c,d,e is ‘aaa’ a valid 3 letter combinations. If repeated combinations are not allowed then the number of combinations can be written as

While the left hand side of this equation is the one we would use for calculations the right hand side helps use understand where it comes from. First of we work out the number of permutations and then divide by k factorial to reduce this number to account for the fact that position does not matter for combinations. As we are taking k items from the set it is reasonable to expect that you will need to divide by k factorial to remove all the invalid permutations and leave only the valid combinations.Working through a couple of simple case where k=1,2 an 3 really helps you see why it is a factorial instead of something else.

For combinations where we are able to repeat given items in a given combination the total is given by

I have to admit this is the one formula I have not yet figured out the reasoning behind this equation. I should really hit the books and figure it out, although my math books just seem to quote the formula… If any reader cares to shed some light on this otherwise I may have to take a trip down google lane.

Conclusion
This article has first discussed why a computer programmer should be interest in understanding permutations and combinations and presented the key formula for both Permutations and Combinations. I hope you have found it useful and interesting. Should you have any comments or have spotted any errors then please contact me via the contact page.