Counting and Probability

Random process/experiment

When it takes place, one outcome from some set of outcomes is sure to occur, but it is impossible to predict with certainty which outcome that will be.

Sample Space

The set of all possible outcomes of a random process. An event is a subset of the sample space

Probability

Probability Axioms

Let $S$ be a sample space. A probability function $P$ from the set of all events in $S$ to the set of real numbers satisfies the following axioms for all events $A$ and $B$ in $S$,

1. $0\le P(A)\le 1$
2. $P(\varnothing )=0$ and $P(S)=1$
3. If $A$ and $B$ are disjoint events ($A\cap B=\varnothing$), then $P(A\cup B)=P(A)+P(B)$

Probability of union of two events

If $A$ and $B$ are any events in a sample space $S$ then $P(A\cup B)=P(A)+P(B)-P(A\cap B)$

Equally likely probability formula

If $S$ is a finite sample space in which all outcomes are equally likely and $E$ is an event in $S$, then the probability of $E$, denoted $P(E)$ is
$P(E)=\frac{\text{Number of outcomes in }E}{\text{Total number of outcomes in }S}=\frac{|E|}{|S|}$

Probability of complement of event

$P(\bar{A})=1-P(A)$

Expected Value

Suppos the possible outcomes of a probability experiment are real numbers $a_1,a_2,\dots ,a_n$ which occur with probabilities $p_1,p_2,\dots ,p_n$ respectively. The expected value of the experiment is: ${\sum }_{k=1}^n{a}_k{p}_k$

Conditional Probability

Let $A$ and $B$ be events in a sample space $S$ . If $P(A)\ne 0$ then the conditional probability of $B$ given $A$ , denoted $P(B|A)$ is $\frac{P(A\cap B)}{P(A)}$
$P(A\cap B)=P(B|A)\cdot P(A)$
$P(A)=\frac{P(A\cap B)}{P(B|A)}$

Bayes’ Theorem

Suppose that a sample space $S$ is a union of mutually disjoin events $B_1,B_2,\dots ,B_2$ . Suppose $A$ is an event in $S$ and suppose $A$ and all the $B$ have non-zero probabilities. If $k$ is an integer with $1\le k\le n$ then $P(B_k|A)=\frac{P(A|B_k)\cdot P(B_k)}{P(A|B_1)\cdot P(B_1)+P(A|B_2)\cdot P(B_2)+...+P(A|B_n)\cdot P(B_n)}$

Independent Events

For events $A$ and $B$ in sample space $S$ then they are indepent iff $P(A\cap B)=P(A)\cdot P(B)$

Mutually Independent

For events $A$ $B$ and $C$ in a sample space $S$ . They are pairwise independent iff they satisfy conditons 1-3 below. They are mutually independent iff they satisfy all 4 conditions below.

1. $P(A\cap B)=P(A)\cdot P(B)$
2. $P(A\cap C)=P(A)\cdot P(C)$
3. $P(B\cap C)=P(B)\cdot P(C)$
4. $P(A\cap B\cap C)=P(A)\cdot P(B)\cdot P(C)$

Counting

Theorem 9.1.1: If $m$ and $n$ are integers and $m\le n$ then there are $n-m+1$ integers from $m$ to $n$ inclusive.

Permutations

A permutation of a set of objects is an ordering of distinguishable objects in a row (e.g. abc, acb, cba, bac, bca, cab)
Theorem 9.2.2: The number of permutations of a set with $n$ ($n\ge 1$) elements is $n!$
Theorem 9.2.3: If $n$ and $r$ are integers and $1\le r\le n$ then the number of r-permutations of a set of n elements $P(n,r)=n(n-1)(n-2)\dots (n-r+1)$ or $\frac{n!}{(n-r)!}$

r-combination

let $n$ and $r$ be non-negative integers with $r\le n$
An r-combination of a set of $n$ elements is a subset of $r$ of the $n$ elements. $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ or n choose r, or ${}_n{C}_r$ denotes the number of subsets of size r (r-combinations) that can be chosen from a set of n elements.
Theorem 9.5.1: $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{P(n,r)}{r!}=\frac{n!}{r!(n-r)!}$

Pascal’s Formula

Theorem 9.7.1
$\left(\genfrac{}{}{0ex}{}{n+1}{r}\right)=\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)+\left(\genfrac{}{}{0ex}{}{n}{r}\right)$

Possibility trees

e.g. 2 coin tosses
           / \
Coin 1   H     T
        / \   / \
Coin 2 H   T H   T

Multiplication Principle

If an operations consists of $k$ steps and the first step can be performed in $n_1$ ways, second step in $n_2$ ways, $k^{\text{th}}$ step in $n_k$ ways, (regardless of how the other steps were performed), then the entire operation can be performed in $n_1\times n_2\times \dots \times n_k$ ways
e.g. number of 4-digit numeric pins is $10\times 10\times 10\times 10=1000$
e.g. number of 4-digit numeric pins without repeating digits is $10\times 9\times 8\times 7$

Addition Rule

If we have $m$ ways of doing something and $n$ ways of doing another thing and we cannot do both at the same time, then there are $m+n$ ways to choose one of these actions.
Theorem 9.3.1: A finite $A$ equals the union of $k$ distinct mutually disjoint subsets $A_1,A_2,\dots ,A_k$ Then $|A|=|A_1|+|A_2|+\dots +|A_k|$

Difference Rule

Theorem 9.3.2: If $A$ is a finite set and $B\subseteq A$, then $|A\backslash B|=|A|-|B|$

Permutations with Indistinguishable Objects

Suppose a collection consists of $n$ objects of which: $n_1$ are of type 1 and are indistinguishable from each other, …, $n_k$ are of type $k$ and are indistinguishable from each other
The number of distinguishable permutations of the $n$ objects is $\left(\genfrac{}{}{0ex}{}{n}{n_1}\right)\left(\genfrac{}{}{0ex}{}{n-n_1}{n_2}\right)\dots \left(\genfrac{}{}{0ex}{}{n-n_1-n_2-\dots -n_{k-1}}{n_k}\right)=\frac{n!}{n_1!n_2!\dots n_k!}$

Binomial Theorem

For real numbers $a$ and $b$ and non-negative integers $n$
$(a+b{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k}{b}^k$

r-combination with repetition

Also known as a multiset of size $r$
A multiset of size $r$ chosen from a set $X$ of $n$ elements is an unordered selection of elements with repetition allowed. It is written as $[x_{i_1},x_{i_2},\dots ,X_{i_r}]$
Theorem 9.6.1: The number of multisets of size r that can be selected from a set of $n$ elements is $\left(\genfrac{}{}{0ex}{}{r+n-1}{r}\right)$ This equals the number of ways $r$ objects can be selected from $n$ categories of objects with repetitions allowed

Inclusion/Exclusion rule

If $A$, $B$ and $C$ are finite sets, then $|A\cup B|=|A|+|B|-|A\cap B|$
$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

Pigeonhole Principle 2

A function from one finite set to a smaller finite set cannot be injective

Generalised

For any function $f$ from a finite set $X$ with n elements to a finite set $Y$ with $m$ elements and for any positive integer $k$ if $k<n/m$ then there is some $y\in Y$ such that $y$ is the image of at least $k+1$ distinct elements of $X$
Contrapositive: For any funciton $f$ from a finite set $X$ with $n$ elements to a finite set $Y$ with $m$ elements and for any positive integer $k$, if for each $y\in Y,f^{-1}(\{y\})$ has at most $k$ elements, then $X$ has at most $km$ elements. ($n\le km$)

Summary

	Order Matters	Order Doesn’t Matter
Repetition Allowed	$n^k$	$\left(\genfrac{}{}{0ex}{}{k+n-1}{k}\right)$
Repetition not Allowed	$P(n,k)$	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$