Permuations and Combinations

---

Permutations are key to probabilities. A permutation is simply arranging items in a given set S without regard to order. If we had a deck with 3 cards in it numbered from 1 to 3, a total of 6 permutations exists: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2] and [3,2,1].

So with a general understanding of what a permutation is, the goal now is to develop a more abstract idea so that the number of permutations can be found quickly given n items.

If a deck has n cards in it, how many ways are there to remove all n cards? When drawing the first card there are n different possibilities of what that card would be. The second card that is drawn only has (n-1) possibilities. This continues until no cards are left. So the number of ways that all cards from the deck can be drawn is (n)(n-1)(n-2)...(1). This is know as the factorial.

(n)(n-1)(n-2)...(1) = n!

Now suppose that instead of only taking one item at a time, 2 items are taken at a time. With a deck of 4 cards numbered 1 to 4 this means that the permutations of way in which the cards can be drawn are: [[1,2],[3,4]], [[2,1],[3,4]], [[1,2],[4,3]], [[2,1],[4,3]], [[1,3],[2,4]], [[3,1],[2,4]], [[1,3],[4,2]], [[3,1],[4,2]], [[1,4],[2,3]], [[4,1],[2,3]], [[1,4],[3,2]], and [[4,1],[3,2]].

So if there is a deck with n cards and k cards are drawn at a time, how many permutations are there? The solution takes the following form:

# The number of permutations of n items taken k at a time.
permutations(n,k) = n! / (n - k)!

Notice that this is equivalent to:

permutations(n,k) = (n)(n-1)...(n-k+1)

This form of the solution will be much more efficienct when it come to implementing a function in Erlang because instead of calculating 2 factorials and then dividing, it will only do a partial factorial.

Combinations

Permutations and combinations are similar except that a combination are not concerned with order. A permutation has k! duplicate combinations, so the solution is to simply divide the number of permutations by k!.

combinations(n,k) = n! / (k! (n - k)!)
                  = (n)(n-1)...(n-k+1) / k!

This ends the description of permutations and combinations. I am sure that some things are not clear, as I am working though a book on probability and statistics and just trying to explain it so that I can better grasp the subject. If there are any questions or things that could be clearer, please leave a note in the comments section.

Implementation in Erlang

%% waratuman_math.erl
-module(waratuman_math).
-export([factorial/1, partial_factorial/2]).
 
factorial(N) ->
    partial_factorial(N, 1).
 
 %% A generalization of factorial. Instead of multipling a number
 %% n times all numbers down to 1 it is multiplied by all numbers
 %% down to k, including k. Both n and k are postivie integers.
 %% partial_factorial(N,K) -> (N) * (N-1) * ... * (N-K).
 partial_factorial(N, K) ->
     partial_factorial(N, K, 1).
  
 partial_factorial(N, K, Accumulator) when N < K ->
     Accumulator;
 partial_factorial(N, K, Accumulator) ->
     partial_factorial(N-1, K, N*Accumulator).

%% waratuman_probability.erl
-module(waratuman_probability).
-import(waratuman_math, [factorial/1, partial_factorial/2]).
-export([permutations/1, permutations/2, combinations/2]).
    
permutations(N) ->
    factorial(N).
permutations(N, N) ->
    factorial(N);
permutations(N, K) ->
    partial_factorial(N, N-K+1).
 
combinations(N, N) ->
    1;
combinations(N, K) when (N - K) > K ->
    partial_factorial(N, N-K+1) / factorial(K);
combinations(N, K) ->
    partial_factorial(N, K+1) / factorial(N-K).