Monday, April 25, 2011

Probabilities

Every so often an understanding of mathematical probability is needed when programming. Let's cover some basics.

Factorials

How many possible ways are there to arrange the 26 letters of the alphabet?
Well, there are 26 possible ways to arrange the first letter, 25 possible ways to arrange the second letter, ... 1 possible ways to arrange the last letter letter.

This is equal to 26 * 25 * 24 * ... * 1. This mathematical sequence is called a factorial. And can be written as 26! The answer to 26! is 403291461126605635584000000 -- wow.

Selections

We are often concerned with particular selections of objects rather than all objects. For example, suppose we have three letters: A, B, C. It is possible to select two letters 6 different ways: AB, BA, AC, CA, BC, CB. When order matters it the selection is a permutation. When order does not matter it is said to be a combination. Hence, for the same three letters (A, B, C) there may be 6 permutations but only 3 combinations: AB, AC, BC.

Combinations
In general, the number of combinations of r objects from n objects is given by:

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

So in our example above, to calculate the number of combinations of 2 letters our of the 3 it would be: 3 C 2 = 3! / (3 - 2)! 2! = 6 / 1 * 2 = 3.

Permutations
In general, the number of permutations of r objects from n objects is given by:

n P r = n! / (n - r)!

So in our example above, to calculate the number of permutations of 2 letters our of the 3 it would be: 3 P 2 = 3! / (3 - 2)! = 6 / 1 = 6.


No comments:

Post a Comment