Combinatorics Combinatorics - a fancy word for counting For us, determining the size of some set. We define the things we want to count as the elemtns of some set $S$ and we want to determine the size of that set. The product rule If a procedure $P$ has $m$ steps (step 1, step 2...., step $m$), we define the number of ways to execute the $i$th step as $N_i$. Then the number of ways to execute $P$ is $N_1 * N_2 *...*N_m$ The number of ways of doing $N_i$ does not depend on the previous steps.

Lemma: Any planar graph with $n \geq 3$ vertices has at most $m \leq 3n-6$ edges. Corollary: Any $n$-vertex planar graph has $m \leq 3n$ edges. An embedding of a graph is a function $F: V \rightarrow \mathbb{R}$ that plots vertices of a graph to points in a plane $(x, y)$ For our use case Any two edges intersect in at most one point

The probabilistic method For any event $A$, if $Pr(A) > 0$, then $|A| \geq 1$ For any random variable $X$, there exists at least one outcome $\omega$ such that $X(\omega) \geq E(X)$ Example Theorem: For any graph $G = (V,E)$ with $m$ edges, there exists a partition $(A,B)$ of $V$ such that at least $\frac{m}{2}$ edges have one endpoint in $A$ and one endpoint in $B$. We want to design an experiment that creates a random partition of the graph has this property

Collection: Easy/fast/cheap Testing: Difficult/slow/expensive Imagine a population of people $P_1,...,P_n$ and $k$ people are infected. We can combine samples from the infected population and test them for the virus but is slow We also now that we have enough samples for each person and that we can combine multiple people's samples into a single test In these multi-person test's if any of the samples have the virus, the whole thing will come up positive Ex: $k=1$ Let's say $n = 1000000$ and $k=1$

New definition for expected values Lemma: If $X:S \rightarrow {0,1,2,3,...}$ is a non-negative integer-valued random variable, then $E(X) = \sum_{i=1}^\infty Pr(X \geq i)$ Proof: For each $i \in {1,2,3,...}$ Let $P_i = Pr(X=i)$. $Pr(X \geq i)= \sum_{j=i}^\infty Pr(X=i) = P_i + P_{i+1} + P_{i+2} ...$ $\sum_{i=1}^\infty Pr(X \geq i) = P_1 + P_2 + P_3 + ...$ $+ P_2 + P_3 + ...$ $+ P_3 + P_4 + ...$

Quicksort quicksort(a,i,j) //sort the subarray a_i,..,a_j (i <= j) if i < j: p = random element in a_i,...,a_j //the element to partition around k = partition(a,i,j,p) //the index of p quicksort(a,i,k-1) quicksort(a,k+1, j) Compared to Insertion Sort: $\binom{n}{2}$ comparisons at most, average $\frac{\binom{n}{2}}{2}$, $n-1$ at best

From last lecture Linearity of expectation For any two random variables $X$ and $Y$ $E(E + Y) = E(X) + E(Y)$ For any sequence of random variables $X_1,...,X_n$ $E(X_1, ..., X_n) = E(X_1) + ... + E(X_n)$

Random variables A random variable is neither random nor a variable Definition: Let $S$ be a sample space. Then a random variable on $S$ is a function $X:S \rightarrow \mathbb{R}$ Where $S$ is an outcome of an experiment mapped to a real number. Ex: Rolling two dice $S = {(i, j) : i,j \in {1,2,3,4,5,6}}$

Infinite probability spaces Recall: A sample space is a non-empty countable set. Countable: There is a 1:1 relation between the elements of a set and the integers Example: toss a coin until the first head Set of outcomes $S = {H, TH, TTH, TTTH, ....} = {T^nH: n \in \mathbb{N}}$

Combining probability spaces Example: Tossing a coin and rolling a die $S_1 = {H,T} \ Pr(\omega ) = \frac{1}{2}$ $S_2 = {1,2,3,4,5,6} \ Pr(\omega ) = \frac{1}{6}$ $S = S_1 \times S_2 = {H1,H2,H3,H4,H5,H6,T1,T2,T3,T4,T5,T6}$ $Pr(\omega_1 \wedge \omega_2 )= Pr(\omega_1 ) \times Pr(\omega_2 ) = \frac{1}{2} \times \frac{1}{6} = \frac{1}{12}$ Lemma: Let $A_1,...,A_n$ be a sequence of mutually independent events then: $Pr(A_1 \cap A_2 \cap ... \cap A_n) = Pr(A_1) \times Pr(A_2) \times ... \times Pr(A_n)$

Independent events Definition: Two events $A$ and $B$ are independent if $Pr(A \cap B) = Pr(A) * Pr(B)$ Consequence: If $A$ and $B$ are independent and $Pr(B) > 0$ then $Pr(A | B) = \frac{Pr(A\cap B)}{Pr(B)} = \frac{Pr(A)Pr(B)}{Pr(B)} = Pr(A)$ Ex: Rolling two dice $S = {(D_1, D_2): D_1, D_2 \in {1,2,3,4,5,6}}$ $Pr(\omega ) = \frac{1}{|S|} = \frac{1}{36}$ $A = D_2 = 6 = {(1,6),(2,6),(3,6),(4,6),(5,6),(6,6)}$

The O'Reiley triplets problem Three good tennis players, all triplets ${\text{Christine, Patti, Terri}}$ Petti was the best of the three. If Petti plays either of her sisters, then she wins. We don't know which is which but each are wearing different colored clothing. We have enough time to have two of them play a game.

Birthday Paradox If we have some room with 23 people, what is the probability that some pair of people share the same birthday There are $d=365$ days in a year There are $n=23$ people Equally likely that any given person has a birthday on any given day $S = {(b_1, b_2,..., b_n): b_1,...,b_n \in {1,2,3,...,d}}$ $|S| = d^n$

Anonymous broadcasting Scenario: Three friends go on a trip, they bring a bottle of whisky. All three friends go an do their own thing and upon returning realize that someone drank the whisky. It could be a sinister person on the island, or it could be one of the friends. No one wants to outright admit that they stole the whisky Anonymous broadcasting makes use of the XOR operator Say we have three friends $P_1, P_2$ and $P_3$. Each $P_i$ picks a random bit $b_i$ Each $P_i$ whispers $b_i$ to $P_{i+1 \mod 3}$

merge(l1, l2): L = [] while(l1.isNotEmpty() || l2.isNotEmpty()): if l1.isEmpty(): l.append(l2.removeFirst()) elif l2.isEmpty(): l.append(l1.removeFirst()) else: if l1.first() < l2.first(): l.append(l1.removeFirst())

How many ways are there to write n as the sum of twos and ones $F_n =$ # of ways to write $n$ as the sum of ones and twos ${nothing}=0$ 1 way to count 0 with ones and twos For $n \geq 2$ we can either Start with a 1

Recursive functions A function that calls itself until some base case. The definition of the function involves the function itself. Ex: Claim: $f(n) = 3\times 2^{n+1}-3$

The Pigeonhole Principle Let $k \geq 1$ be an integer. If $k + 1$ ($m$) or more objects are placed into $k$ ($n$) holes, then at least one hole contains at least two (ceil($m/n$))objects. If $A$ and $B$ are sets and $|A| > |B|$, then there is no one-to-one function $f:A \rightarrow B$ Simon's Drinking Problem Simon drinks at least one beer everyday In April, which has 30 days, Simon drank exactly 45 beers By the pigeonhole principle we can conclude there is at least 1 day where Simon drank ceil(45/30) beers

Addendum: Additional binomial identity $\binom{2n}{n} = \sum_{k=0}^n\binom{n}{k}^2$ Proof: Use Vandermande's with $m=n$ ($m+n=2n$) and $r=n$ $=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k} = \sum_{k=0}^n\binom{n}{k}^2$ Applications of counting rules Example: How many rearrangements of the string "ROCKY" are there? By the product rule: $5!$

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.