# 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).
```