Counting - 4
Binomial Coefficients
The quantity $C(n,k)$, which gives the number of $k$-combinations of a set of size $n$, is called a binomial coefficient.
It is also written as:
\[{n\choose k}=\frac{n!}{(n-k)!k!}\]This notation is preferred.
Binomial Theorem
For every natural number $n$:
\[(a+b)^n=\sum^n_{k=0}{n\choose k}a^kb^{n-k}\]This is the sum of a generic binomial expansion.
Pascal’s Triangle
The choose notation directly relates to pascals triangle. For a generic expansion the row is the power and the value is the coefficient of the related position in the expansion.
Binomial Coefficient Identity
\[{n+1\choose r+1}={n\choose r}+{n\choose r+1}\]Proof:
- ${n+1\choose r+1}$ is the number of ways to choose a subset of size $r+1$ form a st of size $n+1$.
- Suppose the set is $\{x_1,x_2,\ldots,x_{n+1}\}$.
- How many subsets include $x_{x+1}$? We just choose a size-$r$ subset from $\{x_1,x_2,\ldots,x_{n+1}\}$, so there are $n\choose r+1$ ways to do it.
- These outcomes are disjoint, so the total number of subsets is the sum of $n\choose r$ and $n\choose r+1$.
Counting and Probabilities
Counting also helps us to answer questions like:
- What are the odds of winning the National Lottery?
- What payoffs should you expect?
- What is more likely in poker, full house or 4-of-a-kind?