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:
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
If a deck has
n cards in it, how many ways are there
to remove all
n cards? When drawing the first card there
n different possibilities of what that card would
be. The second card that is drawn only has
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:
So if there is a deck with
n cards and
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.
Permutations and combinations are similar except that a combination
are not concerned with order. A permutation has
duplicate combinations, so the solution is to simply divide the number
of permutations by
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).