• University of Michigan

• EECS 203

 Chapter 2.3 Let f1 and f2 be functions from A to R. (f1 + f2 )(x) = f1 (x) + f2 (x), (f1 f2 )(x) = f1 (x)f2 (x). One­to­one/ injunction, f (a) = f (b) implies that a = b for all a and b in the domain of f. ∀a∀b(f (a) = f (b) → a = b). Universe of  discourse is the domain of the function. |A| ≤ |B|.   Onto/surjection, the inverse of the function is valid on the domain.  ∀y∃x(f (x) = y) x is the domain of y is the codomain. |A| >= |B|.   Chapter 2.4 A recurrence relation for the sequence {an } is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0 , a1 , . . . ,  an−1 , The Fibonacci sequence, f0 , f1 , f2 , . . . , is defined by the initial conditions f0 = 0, f1 = 1, and the recurrence  relation fn = fn−1 + fn−2   Chapter 2.5 If A and B are countable sets, then A ∪ B is also countable. SCHRÖDERBERNSTEIN THEOREM If A and B are sets with |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. Chapter 5.1 MATHEMATICAL  INDUCTION BASIS STEP: We verify that P (1) is true. INDUCTIVE STEP: We show that the conditional statement P (k) → P (k + 1) is true for all positive integers k. STRONG INDUCTION BASIS STEP: We verify that the proposition P (1) is  true.INDUCTIVE STEP: We show that the conditional statement [P (1) ∧ P (2) ∧ ∙ ∙ ∙ ∧ P (k)] → P (k + 1) is true for all  positive integers k. (P(k+1)) is true if P(j) is true for 1  n^m Counting One­to­One Functions How  many one­to­one functions are there from a set with m elements to one with n elements? n(n − 1)(n − 2) ∙ ∙ ∙ (n − m + 1).  When m > n there are no one­to­one functions Counting Subsets of a Finite Set  A1 ×A2 ×∙∙∙×Am|=|A1 |∙|A2 |∙ ∙∙∙ ∙|Am|.  THE SUM RULE If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1 ways is  the same as any of the set of n2 ways, then there are n1 +n2 ways to do the task. |A1 ∪A2 ∪∙∙∙∪Am| = |A1 | + |A2 | + ∙∙∙ + | Am| when Ai ∩Aj = for all i, j. THE SUBTRACTION RULE If a task can be done in either n1 ways or n2 ways, then the  number of ways to do the task is n1 + n2 minus the number of ways to do the task that are common to the two different  ways. |A1 ∪A2 | = |A1 |+|A2 |−|A1 ∩A2 |.THE DIVISION RULE There are n/d ways to do a task if it can be done using a  procedure that can be carried out in n ways, and for every way w, exactly d of the n ways correspond to way w. Chapter  6.2 Amax >= N pigeons/ K holes. Every sequence of n2 + 1 distinct real numbers contains a subsequence of length n + 1  that is either strictly increasing or strictly decreasing. Chapter 6.3 A permutation order matters, combination doesn’t,  C(n,r) = n! / r!(n­r)! . The number of ways to choose six cookies is the number of 6­combinations of a set with four  elements. From Theorem 2 this equals C(4 + 6 − 1, 6) = C(9, 6) Chapter 7.2 If S is a finite nonempty sample space of  equally likely outcomes, and E is an event, that is, a subset of S, then the probability of E is p(E) =|E|/|S|. Let E1 and E2  be events in the sample space S. Then p