CMSC 250 – Jerry Alan Fails Student: __________________ Due: Tuesday, July 17, 2007 ID #: __________________ HW #11 Due: Tuesday, July 17, 2007 Page 1 of 2 HW #11 You must work alone on your homework, and homework must be written legibly, single-sided on your own lined paper, or typed, with the answers clearly labeled and in the sequential order as assigned. You must write your name and university ID number in the upper right-hand corner of your homework. Staple all pages together and be sure that your name appears on every sheet. 1. (-10 points if wrong) Write your name clearly on each page. Write the time and place of the Final Exam. 2. (20 points) How many permutations of abcde are there in which the first character is a, b, or c and the last character is c, d, or e? 3. (10 points) If n is a positive integer, how many 5-tuples of integers from 1 through n can be formed in which the elements of the 5-tuple are written in decreasing order but are not necessarily distinct? In other words, how many 5-tuples of integers (h, i, j, k, m) are there with n ≥ h ≥ i ≥ j ≥ k ≥ m ≥ 1? 4. (10 points) Assuming that all years have 365 days and all birthdays occur with equal probability, how large must n be so that in any randomly chosen group of n people, the probability that two or more have the same birthday is at least ½? (This is called the birthday problem. Many find the answer surprising.) 5. (10 points) For how many integers from 1 through 99,999 is the sum of their digits equal to 9? 6. (10 points) For each of the following, write the specified term of the expansion. Simplify all coefficients so the denominators do NOT have a factorial. (a) Write (and simplify) the 5th term of the expansion of ()1023 yx + . (b) Write (and simplify) the 10th term of the expansion of ()13yx + . 7. (8 points) Let A = {1,2,3,4,5}, P(A) be the power set of A. Define a function F : P(A) → Z as follows: For all sets X in P(A), ( )=elements ofnumber oddan has if1elements ofnumber even an has if0XXXF Find the following: (a) F({1,3,4}) (b) F({2,3}) (c) F(∅) (d) F({2,3,4,5})CMSC 250 – Jerry Alan Fails Student: __________________ Due: Tuesday, July 17, 2007 ID #: __________________ HW #11 Due: Tuesday, July 17, 2007 Page 2 of 2 HW #11 8. (8 points) Determine the following: (a) How many one-to-one functions are there from a set with three elements to a set with three elements? (b) How many one-to-one functions are there from a set with m elements to a set with n elements, where m ≤ n? (c) How many onto functions are there from a set with three elements to a set with five elements? (d) How many onto functions are there from a set with four elements to a set with three elements? 9. (8 points) Function f is defined below on a set of real numbers. Determine whether or not f is one-to-one and justify your answer. 11)(−+=xxxf , for all real numbers x ≠ 1. 10. (8 points) Let P(A) be the power set of A. Define F : P({a,b,c}) → Z as follows: For all A in P({a,b,c}), F(A) = the number of elements in A. (a) Is F one-to-one? Prove or give a counterexample. (b) Is F onto? Prove or give a counterexample. 11. (8 points) Let S be the set of all strings in a’s and b’s and define C: S → S by C(s) = as, for all s∈S. (C is called concatenation by a on the left.) (a) Is F one-to-one? Prove or give a counterexample. (b) Is F onto? Prove or give a counterexample. 12. (No points will be awarded for this assignment unless this is done) Sign your name to the following honor code statement: “I pledge on my honor that I have not given or received any unauthorized assistance on this
View Full Document
Unlocking...