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

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 The pulverizer We saw in lecture that the greatest common divisor(GCD)of two numbers can be written as a linear combination of them. That is, no matter which pair of integers a and b we are given, there is always a pair of integer coefficients s and t such that