Lecture 7 - Notes

January 25, 2016

Binary Trees

How many nodes in a binary tree with height $h$?

$$\begin{align} h + 1 &\le n \newline &\le 1 + 2 + 4 + ... + 2^h \newline &= 2^{h+1} - 1 \end{align}$$

and conversely,

$$\begin{align} n &\le 2^{h+1} - 1 \newline n + 1 &\le 2^{h+1} \newline \lg (n + 1) &\le h+1 \newline \lg (n + 1) - 1 &\le h \newline \left\lceil\lg \left(n + 1\right) - 1\right\rceil &\le h \newline \end{align}$$

Binomial Coefficients

Let $n \choose k$ denote the number of $k$-subsets of an $n$-set. $2$-subsets of the set ${a,b,c,d}$ are

$$\begin{align} \{a,b\} \newline \{a,c\} \newline \{a,d\} \newline \{b,c\} \newline \{b,d\} \newline \{c,d\} \newline \end{align}$$

In this case,

$$\begin{align} \binom{4}{2} &= 6 \newline \binom{4}{1} &= \binom{4}{3} = 4 \newline \end{align}$$

In general,

$$\begin{align} \binom{n}{k} = \binom{n}{n-k} \end{align}$$

the function $f$ that maps ${a_0,a_1,\ldots,a_k}$ to $[n] \setminus {a_0,a_1,\ldots,a_k}$ where $[n] = {1,2,\ldots,n}$, is a bijection. For example

$$\begin{align} f\left(\left\{ n \right\} \right) = \{b,c,d\} \end{align}$$

Claim: Pascals triangle equality, e.g.,

$$\begin{align} \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \end{align}$$

Proof: Classify the $k$-subsets of $[n]$ according to whether they contain $n$ or not. There are $\binom{n-1}{k-1}$ $k$-subsets that contain $n$ and $\binom{n-1}{k}$ $k$-subsets that do not contain $n$.

We can demonstrate this with pascals triangle.

	0	1	2	3	4	5	6
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1

Claim:

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

Shepherd Principal: We can prove this using the Shepherd principal. Suppose we are counting sheep and they really like each other so they have squished together into one blob. Luckily the sheep are standing on a sheet of glass so we can go underneath and count the feet. Divide by four and we have the number of sheep.

So if a set (the sheep) has been divided into equivalence classes (the feet) and each equivalence class has the same number for elements. Then the number of equivalence classes is

$$\begin{align} \frac{\text{Number of Elements}}{\text{Number in Each Class}} \end{align}$$

Proof: There are $n(n-1) \ldots (n-k+1)$ $k$-sequences in an $n$-set. Each $k$-subset corresponds to $k!$ of these. Thus,

$$\begin{align} \binom{n}{k} &= \frac{n(n-1) \ldots (n-k+1)}{k!} \newline &= \frac{n(n-1) \ldots (n-k+1)}{k!} \cdot \frac{(n-k)!}{(n-k)!} \newline &= \frac{n!}{k!(n-k)!}\newline \end{align}$$

Example

How many binary sequences are there with $s$ zeros and $t$ ones? For example, given,

$$\begin{align} 10101110 \end{align}$$

then $s = 3$ and $t = 5$.

Solution

I think the answer is,

$$\begin{align} \binom{s+t}{t} \end{align}$$

Frank Ruskey is hard to follow at best.

Binomial Queues

definition: A binomial queue are a kind of a mergeable heap.