math 5

Weekly Summary, Week 4, Chapter 5, Discrete Mathematics Name:

Due on Sunday, September 23, by midnight.

Type your answers under the questions given below, or, print out this sheet, use pen or pencil to fill it out, and email a scan or photo of it to the instructor.

1) Give a recursive definition (similar to example 5.8) for the relation R containing the ordered pairs:

(0, 2), (3, 8), (6, 32), (9, 128), …

2) Let A = {1, 2, 3} and B = {1, 2, 3, 4, 5, 6}. How many one(to(one functions f : A ( B have the property that f (2) = 2 ?

3) Is it true or false that (A ( B) ( (A ( C) = A ( (B ( C) for any sets A, B, C ? If the answer is false, give specific sets A, B, C which provide a counterexample.

4) Let A and B be sets with |A| = 12 and |B| = 15. Set up, but do no simplify, a formula for the number of functions from A to B.

5) Let A and B be sets with |A| = 12 and |B| = 15. Set up, but do no simplify, a formula for the number of one(to-one functions from A to B.

6) Let A and B be sets with |A| = 12 and |B| = 15. Without using the formula, give the exact number of onto functions from A to B. [Hint: Use the meaning of "onto function" to get the easy answer.]

7) Consider the number 510,510 which factors into prime factors as 2(3)(5)(7)(11)(13)(17). In how many ways can 510,510 be factored into 4 factors, all greater than 1?

[Note: this is an application of the formula for Stirling numbers of the second kind, as per example 5.28. To avoid doing the actual calculation use the table on page 264.]