Counting and Probability

Naive Probability

Def. (Naive Definition of Probability)

For a finite sample space $S$ with equally likely outcomes, the probability of an event $A$ is:

$P(A) = \frac{|A|}{|S|} = \frac{\text{Number of outcomes favorable to } A}{\text{Total number of outcomes}}$

Caveats:

• Requires a finite sample space
• Only applies when all outcomes are equally likely

Combinatorics

Def. (Permutation)

A permutation is an arrangement of objects where order matters. The number of ways to arrange $n$ distinct objects is $n! = n \times (n-1) \times \cdots \times 2 \times 1$.

The number of permutations of $k$ objects chosen from $n$ objects is: $P(n,k) = \frac{n!}{(n-k)!}$

Def. (Combination)

A combination is a selection of objects where order does not matter. The number of ways to choose $k$ objects from $n$ objects is:

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

Also read as "$n$ choose $k$".

Counting Principles

Def. (Multiplication Principle)

If there are $n_1$ ways to perform task 1 and $n_2$ ways to perform task 2, then there are $n_1 \times n_2$ ways to perform both tasks in sequence.

More generally, if there are $n_1, n_2, \ldots, n_k$ ways to perform $k$ tasks respectively, there are $n_1 \times n_2 \times \cdots \times n_k$ ways to perform all tasks.

Def. (Addition Principle)

If task 1 can be done in $n_1$ ways and task 2 can be done in $n_2$ ways, and the two tasks cannot be done simultaneously, then there are $n_1 + n_2$ ways to do either task 1 or task 2.

Def. (Multinomial Coefficient)

The multinomial coefficient counts the number of ways to partition $n$ objects into $k$ groups of sizes $n_1, n_2, \ldots, n_k$ where $n_1 + n_2 + \cdots + n_k = n$:

$\binom{n}{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!}$

Special case: When $k=2$, this reduces to the binomial coefficient: $\binom{n}{n_1, n_2} = \binom{n}{n_1}$

More content will be added from lecture materials.