Sample space: the set $S$ of all possible outcomes for a random experiment (an experiment where the outcome depends on random chance)
An event is a set of outcomes
If a sample space $S$ has $n$ outcomes with equal probability, then an event $E$ consisting of $m$ outcomes has probability $P(E)=\frac{m}{n}$
Canonical random experiment
- "A box contains $n$ distinct objects; $k$ objects are randomly selected from the box, one at a time."
- Four variations:
  - Ordered with and without replacement (permutations)
  - Unordered with and without replacement (combination)

Permutations¶

Variation 1¶

Ordered, no replacement
Box has 3 objects numbered 1, 2, and 3. Pick objects one at a time. How many different outcomes are there?
- $3! = 3\cdot 2 \cdot 1 = 6$
Same experiment except the box has 5 objects. You only pick 3. How many outcomes are there?
- $5 \cdot 4 \cdot 3 = 60$
The number of permutations of $n$ objects is $n \cdot (n-1) \cdot \cdot \cdot 2 \cdot 1 = n!$
The number of $k$-permutations from a set of $n$ is $\(\large P_{n,k}=\frac{n!}{(n-k)!}$\)

Unordered, without replacement
Consider a box with objects 1, 2, 3, 4. How many ways are there to form groups of 3, if the order does not matter?
- $\large \frac{4!}{3!}=\frac{24}{6}=4$
The number of distinct $k$-combinations or subsets of $k$ objects from a set of $n$ objects is $$ \large C_{n,k}=\frac{n!}{k!(n-k)!}$$

Unordered, with replacement
A doughnut shop has 5 different kinds of donuts. How many unique ways are there to select 12 doughnuts? $\(\large C_{(n+k-1),k}=C_{(5+12-1),12}=C_{16,12}=1820$\)