Probability Tutorial

By Xah Lee. Date: . Last updated: .

factorial

factorial is a function of integer to integer, written as n!. it is defined by

and we also define:

permutation

permutation is all possible ways to arrange n things (order matters).

for example, we have three numbers 1, 2, 3.

all possible permutation are

the number can be different colored balls, or anything else.

Permutation Formula

The number of possible ways to arrange n things is the factorial n!

Derivation of the Permutation Formula

let's say we have 3 balls numbered 1, 2, 3.

so, the answer is 3*2*1, or n!.

k-Permutation of n things

k-Permutation of n things means, taking k things out of n distinct things, and order matters.

Example, let's say we have 10 balls, numbered 1 to 10. We want to draw 3 balls, and order matters. Example: 9 5 1 is different from 5 9 1. The total count of ways is 10*9*8. Because first we have 10 possibilities, then 9 possibilities because one ball is gone (10-1), then 8 possibilities because another ball is gone (10-2),

k-Permutation formula

k-Permutation of n things, we define a function P(n,k).

p(n,k) := n * (n - 1) * (n - 2) * (n - 3) ...

where there are k factors on the right-hand-side.

can be written as

p(n,k) := n! / (n - k)!

Combination Formula

Combination formula, usually written as

C(n,k)

returns a number that's all possible k things out of n. Order of k doesn't matter. (each of the n thing is distinct. e.g. lottery balls each with a number printed on it)

C(n,k) is defined to be

n!/(k! (n-k)!)

Derivation of the Permutation Formula

Start with permutation, than divide by the permutation of k (because the order of k things doesn't matter) , and divide by the permutation of (n -k) (because these rest of things are not included).

binomial coefficients

binomial is a polynomial of two terms. e.g. (x + y)

the Combination Formula C[n , k] is also the formula for computing the kth coefficient of binomial to the nth power. (consider the coefficient numbering start at 0.)

here are binomial powers: 

(x + 1)^0
(x + 1)^1
(x + 1)^2 = 1 x^2 + 2 x + 1
(x + 1)^3 = 1 x^3 + 3 x^2 + 3 x + 1
(x + 1)^4 = 1 x^4 + 4 x^3 + 6 x^2 + 4 x + 1

in

(x + 1)^n

there are n +1 terms.

so, we can number the coefficient as 0th, 1th, etc to nth.

the kth term is C[n , k]

For example, in (x + 1)^4 = 1 x^4 + 4 x^3 + 6 x^2 + 4 x + 1

the coefficients are

1 4 6 4 1

they corresponds to

C[4,0] C[4,1] C[4,2] C[4,3] C[4,4]

Pascal's Triangle

Pascal's Triangle is created by adding numbers starting with 1 like this 

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

Pascal's Triangle can be used to compute the binomial coefficients.

they correspond this way: 

(x + 1)^0                                            1
(x + 1)^1                                           1 1
(x + 1)^2 = 1 x^2 + 2 x + 1                        1 2 1
(x + 1)^3 = 1 x^3 + 3 x^2 + 3 x + 1               1 3 3 1
(x + 1)^4 = 1 x^4 + 4 x^3 + 6 x^2 + 4 x + 1      1 4 6 4 1

Independent Events, Mutually Exclusive Events

Independence Two events are independent, if the occurrence of one does not affect the probability of occurrence of the other.

Mutually Exclusive. two events are mutually exclusive if they cannot both occur at the same time.

Probability and Statistics