# 4 - Binomial coefficients, Newton's Binomial Theorem, combinatorial proofs, Vandermonde's Identity, Pascal's Triangle

**Review theorem**: Let $S$ be an $n$-element set. There are $n!$ permutations of $S$


**1 proof**: Use the product rule. Pick an element from the set and remove it
- Initially, you have $n$ choices
- Then $n-1, n-2...1$
- Number of permutations is $n \times n-1 \times ... \times 1$

## Binomial Coefficients
Let $n \geq 0, k\geq 0$ be integers.
Then $\binom{n}{k}$ is the number of $k$-element subsets of set of size $n$.

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

*Think back to 2507 combinations*

### Useful facts to remember
- $\binom{n}{k} = \binom{n}{n-k}$
- $\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k-1}$ (Pascal's identity)

### Proof: (Combinatorial proof / Counting two ways)

There exist two formulas $f_1, f_2$. We want to show that $f_1=f_2$.
We define a set $A$ and show that $f_1 = |A|=f_2$, prooving that $f_1=f_2$

Let $S$ be a set of size $n$.
Let $A$ be the *ordered* $k$-element subsets of $S$

Ex: unordered set (order doesn't matter $\{a,b\} = \{b,a\}$)
ordered sets (order does matter $\{a,b\} \neq \{b,a\}$)

We figure out the size of $A$, $|A|$ in two ways.

i) Product rule:

1. Chose a k-element subset of S $\binom{n}{k}$
2. Choose an order for this subset ($k!$)

This says that $|A| = \binom{n}{k}k!$

ii) also product rule

for i=1 to k:
    -choose the ith element in the ordered set

$|A|=n \times (n-1) \times (n-2) \times ... \times (n-k+1) = \frac{n!}{(n-k)!}$

**Example**: How many 5-card hands of a 52 card deck are there?

$\binom{52}{5} = \frac{52!}{5!(52-5)!} = 2,598,960$

**Example**: How many bitstrings of length $n$ have exactly $k$ 1s?

-Product Rule:
- choose the locations of the $k$ 1's and write them down
- write 0's everywhere else


$=\binom{n}{k}$

## Newton's binomial theorem
For any number $x,y$ and integers $n \geq 0$

$(x+y)^n= \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k}$

Allows us to expand and multiple and binomial with one formula


### Proof
$(x+y)^n = (x+y)\times(x+y)...(x+y)$ $n$ times
Each time we distribute the terms, we either multiple each term by $x$ or by $y$
So the coefficients, which are binomial coefficients, are simply made up of the number of terms in the sequence ($n$) choose the number of times we multiple by $y$ ($k$)
$=x^n + \binom{n}{1} x^{n-1}y + \binom{n}{2}x^{n-2}y^2 ... \binom{n}{n}y^n$

**Example**: What is the coefficient of $x^{12}y^{13}$ in $(2x+(-5y))^{25}$

$\binom{25}{13}2x^{12}(-5y)^{13} = -\binom{25}{13}\times2^{12}\times5^{13}\times x^{12}\times y^{13}$

The answer is $-\binom{25}{13}\times2^{12}\times5^{13}$

**Theorem**:$\sum_{k=0}^n \binom{n}{k} = 2^n$
**Proof**: $(1+1)^n = \sum_{k=0}^n \binom{n}{k} 1^{n-k}1^k = \sum_{k=0}^n \binom{n}{k} = 2^n$

$2^n$ is the number of subsets of an $n$-element set
If we take the sum of the size of every $k$-element set where $0 \leq k \leq n$ then we get the size of of every subset of the set of size $n$.
See: the sum rule

## More combinatorial proofs
### Theorem: $\binom{n}{k} = \binom{n}{n-k}$

**Proof**: Let $S$ be a set of size $n$. Let $A$ be the set of $k$-element subsets

By definition: $|A| = \binom{n}{k}$

ii) Use the product rule:
- choose $n-k$ elements in $S$ and remove them $\binom{n}{n-k}$
- Return the remaining $k$ elements of $S$

$|A| = \binom{n}{n-k}$
$\binom{n}{k} = \binom{n}{n-k}$

### Theorem: $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$ [Pascal's Identity]


This relates back to back to pascals triangle


The value of any number in the triangle is the sum of the two numbers that are on it's left and right

### Vandermande's Identity

**Theorem**: $\binom{m+n}{r} = \sum_{k=0}^r \binom{m}{k} \binom{n}{r-k}$


###### tags: `COMP2804` `Combinatorics`