Counting III Today we'll briefly review some facts you dervied in recitation on Friday and then turn to some applications of counting. 1 The Bookkeeper Rule In recitation you learned that the number of ways to rearrange the letters in the wore BOOKKEEPER is:

1 Independent Events Suppose that we flip two fair coins simultaneously on opposite sides of room. Intu- itively, the way one coin lands does not affect the way the other coin lands. The mathe- matical concept that captures this intuition is called independence. In particular, events A and B are independent if and only if:

Notes for recitation 5 1 Well-ordering principle Every non-empty set of natural numbers has a minimum element Do you believe this statement? Seems obvious, right? Well, it is. But dont fail to realize how tight it is. Crucially, it talks about a non-empty set -otherwise, it would clearly be false. And it also talks about natural

1 Graphs and Trees The following two definitions of a tree are equivalent Definition 1: A tree is an acyclic graph of n vertices that has n-1 edges Definition 2: A tree is a connected graph such that Vu, v E V, there is a unique path connecting u to u. In general, when we want to show the equivalence of two definitions, we must show

1 Bipartite Graphs Graphs that are 2-colorable are important enough to merit a special name; they are called bipartite graphs. Suppose that G is bipartite. Then we can color every vertex in G ei ther black or white so that adjacent vertices get different colors. Then we can put all the

An explorer is trying to reach the Holy Grail, which she believes is located in a desert shrine d days walk from the nearest oasis. In the desert heat, the explorer must drink continuously. She can carry at most 1 gallon of water, which is enough for 1 day. However, she is free to create water caches out in the desert. For example, if the shrine were 2/3 of day's walk into the desert, then she could recover

Notes for Recitation 13 Basic Counting Notions bijection or bijective function is function:x→ such that every element of the codomain is related to exactly one element of the domain. Here is an example of a bijection:

Notes for Recitation 14 Counting Rules Rule 1(Generalized Product Rule). Let be a set of length-k sequences. If there are: n1 possible first entries, n2 possible second entries for each first entry, n3 possible third entries for each combination of first and second entries, etc. then:

This is a good approach to questions of the form, What is the probability that ntuition will mislead you, but this formal approach gives the right answer every time 1. Find the sample space. ( Use a tree diagram. 2. Define events of interest. Mark leaves corresponding to these events 3. Determine outcome probabilities (a) Assign edge probabilities

Problem 1. Suppose that you flip three fair mutually independent coins. Define the fol- lowing events: Let be the event that the first coin is heads. · Let be the event that the second coin is heads. · Let be the event that the third coin is heads