Permutations & Combinations

As you may have already noticed, finding patterns in the possible ways events can occur is very useful in helping us count the number of desirable events in our sample space. Two of the easiest methods for doing this are with permutations (when order matters) and combinations (when order doesn't matter).

Permutations

An ordered arrangement of $r$ objects from a set, $A$, of $n$ objects (where $0<r\leq n$) is called an $r$-element permutation of $A$. You can also think of this as a permutation of $A$'s elements taken $r$ at a time. The number of $r$-element permutations of an $n$-object set is denoted by the following formula: $_nP_r =\frac{n!}{(n-r)!}$

Note: We define $0!$ to be $1$; otherwise, $_nP_n$ would be $\frac{n!}{0}$ (when $r=n$).

permutations = 3 * 2 * 1 = 3! = 6

-> written as n! $numpy.math.factorial(n)$

- of a subset

k-permutations = 8 * 7 * 6 = 3366

select k elements out of a pool of n objects

​$n * (n-1) * ... * (n - k + 1)\newline P_k^n=\frac{n!}{(n-k)!}$

from numpy.math import factorial as fact

def permutation(n, k):
    return fact(n) / fact(n-k)

- with replacement

Now the number of possible outcomes is 3 * 3 * 3.

Generalizing this to n, this means that the number of permutations with replacenent when having n distinct objects is equal to n^j where j is the number of “draws”.

Combinations

An unordered arrangement of $r$ objects from a set, $A$, of $n$ objects (where $r \leq n$) is called an $r$-element combination of $A$. You can also think of this as a combination of $A$'s elements taken $r$ at a time.

Because the only difference between permutations and combinations is that combinations are unordered, we can easily find the number of $r$-element combinations by dividing out the permutations ($r!$): $_nC_r=\frac{_nP_r}{r!}=\frac{n!}{r! * (n-r)!}$

When we talk about combinations, we're talking about the number of subsets of size $r$ that can be made from a set of size $n$. In fact, $_nC_r$ is often referred to as "$n$ choose $r$", because it's counting the number of $r$-element combinations that can be chosen from a set of $n$ elements. In notation, $_nC_R$ is typically written as $\binom{n}{r}$.

In general, combinations answer the question: "How many ways can we create a subset k out of n objects?". The subset is not ordered.

$\binom{n}{k}=\frac{P_k^n}{k!} = \frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{(n-k)!k!}$

def combination(n, k):
  return fact(n) / (fact(n-k)*fact(k))

Bernoulli Distribution

We define a binomial process to be a binomial experiment meeting the following conditions:

• The number of successes is k.

• The total number of trials is n.

• The probability of success of 1 trial is p.

• The probability of failure of 1 trial q, where q = 1 - p.

• b(n, k, p) is the binomial probability, meaning the probability of having exactly successes out of n trials.

The binomial random variable is the number of successes, k, out of n trials.

The binomial distribution is the probability distribution for the binomial random variable, given by the following probability mass function:

$b(n, k, p) = \binom nk * p^k * q^{(n-k)}$

def bernoulli(n, k, p):
    return combination(n, k) * p**k * (1-p)**(n-k)