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. Find closed-form generating functions for the following sequences. Do not concern yourself with issues of convergence

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:

Notes for Recitation 15 Problem 1. Learning to count takes practice! (a)In how many different ways can Blockbuster arrange 64 copies of 13 conversations about one thing, 96 copies of L'Auberge Espagnole and 1 copy of Matrix Revolutions on a shelf? What if they are to be arranged in 5 shelves?

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:

Guessing a particular solution. Recall that a general linear recurrence has the form: f(n)=a1f(n-1)+a2f(n-2)+…+aaf(n-d)+g(n) As explained in lecture, one step in solving this recurrence is finding a particular solu- tion; i.e., a function f(n)that satisfies the recurrence, but may not be consistent with the boundary conditions. Here's a recipe to help you guess a particular solution:

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

1 Sums and approximations Problem 1. Evaluate the following sums Solution. The formula for the sum of an infinite geometric series with ratio 1 /2

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

1 RSA In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman proposed a highly secure cryp- tosystem(called RSa)based on number theory. Despite decades of attack, no significant weakness has been found (Well, none that you and me would know.)Moreover, RSA has a major advantage over traditional codes: the sender and receiver of an encrypted