Counting

Counting is important to probability. Often, we are interested in a non-trivial subset of events.

Observation: If experiment 1 can result in $m$ possible outcomes and experiment 2 can result in $n$ possible outcomes, then there are $mn$ total outcomes for the two experiments taken as a whole.

This principle applies to $r$ experiments.

Definition: There are $n!$ permutations for $n$ objects

Observation: There are $\frac{n!}{n_1!n_2!\dots n_r!}$ permutations of $n$ objects, of which $n_1$ are alike, $n_2$ are alike, $\dots$, $n_r$ are alike.

A common question in counting is how many non-ordered subsets can be selected.

Definition: $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{n!}{(n-r)!r!}$ means $n$ choose $r$ and represents the number of possible combinations of $n$ objects taken $r$ at a time.

Observation: $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$, $1\le r\le n$
This is effectively counting the number of combinations with the first element along with the number of combinations without

Binomial Theorem: $(x+y{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n-k}$
$\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ is often referred to as a binominal coefficient because of its place in the binomial theorem

This can be proved inductively, or by considering the combinations formed by multiplying out $(x+y{)}^n$

Poker!!

Let’s start with unordered hands…

Total: $2598960\to 100\%$

Royal flush: $\underset{\text{suit}}{4}$ $\to 0.000154\%$
Straight flush: $\underset{\text{suit}}{4}\cdot \underset{1-9}{9}=36$ $\to 0.00139\%$
Four of a kind: $\underset{\text{rank}}{13}\cdot \underset{\text{remaining}}{48}=624$ $\to 0.02401\%$
Full house: $\underset{\text{rank}}{13}\cdot \left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot \underset{\text{rank}}{12}\cdot \left(\genfrac{}{}{0ex}{}{4}{2}\right)=3744$ $\to 0.1441\%$
Flush: $\underset{\text{suit}}{4}\cdot \left(\genfrac{}{}{0ex}{}{13}{5}\right)-\underset{\text{straight}}{36}-\underset{\text{royal}}{4}=5108$ $\to 0.1965\%$
Straight: $\underset{1-10}{10}\cdot \underset{\text{suits}}{4^5}-\underset{\text{straight}}{36}-\underset{\text{royal}}{4}=10200$ $\to 0.3925\%$
Three of a kind: $\underset{\text{rank}}{13}\cdot \left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot \underset{\text{remaining}}{\left(\genfrac{}{}{0ex}{}{12}{2}\right)}\cdot \underset{\text{suit}}{4^2}=54912$ $\to 2.1128\%$
Two pair: $\left(\genfrac{}{}{0ex}{}{13}{2}\right)\cdot {\left(\genfrac{}{}{0ex}{}{4}{2}\right)}^2\cdot 11\cdot 4=123552$ $\to 4.7539\%$
Pair: $13\cdot \left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot \left(\genfrac{}{}{0ex}{}{12}{3}\right)\cdot 4^3=1098240$ $\to 42.2569\%$
Highest card: $((\genfrac{}{}{0ex}{}{13}{5})-10)(4^5-4)=1302540$ $\to 50.1177\%$

Derangements

$n$ cards, labeled $1$ to $n$, are shuffled and placed down in some order
What is the probability that no card is in its correct (sorted) location?

Say $A_i$ is the event that card $i$ is in the correct location
We want $P({\bigcap }_{i=1}^n(A_i^c))=1-P({\bigcup }_{i=1}^n{A}_i)$
$=P({\bigcup }_{i=1}^n{A}_i)=\sum _{i=1}^{n}P(A_i)-\sum _{i<j}P(A_i{A}_j)+\sum _{i<j<k}P(A_i{A}_j{A}_k)+\cdots +(-1{)}^{n+1}P(A_1\dots A_n)$
$=\left(\genfrac{}{}{0ex}{}{n}{1}\right)\frac{(n-1)!}{n!}-\left(\genfrac{}{}{0ex}{}{n}{2}\right)\frac{(n-2)!}{n!}+\cdots +(-1{)}^{n+1}(\genfrac{}{}{0ex}{}{n}{n})\frac{(n-n)!}{n!}$
$=\frac{1}{1!}-\frac{1}{2!}+\frac{1}{3!}+\cdots +(-1{)}^{n+1}\frac{1}{n!}$
$=\sum _{i=1}^n(-1{)}^{i+1}\frac{1}{i!}$
As $n\to \infty$ we can look at this as a power series and write it in terms of $e$

$e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\dots$
So the complement of our probability is $1-e^{-1}$, and our solution is $1/e$
Mathemagical!