(1) Elizabeth has six different skirts, five different tops, four different pairs of shoes, two different necklaces and three different bracelets. In how many ways can Elizabeth dress up (Note that shoes come in pairs. So she must choose one pair of shoes from four pairs, not one shoe from eight)? A. 20 B. 1440 C. 24 D. 720 (2) In how many ways can 3 boys and 3 girls sit in a row if the boys and girls are each to sit together? A. 36 B. 48 C. 72 D. 144 (3) A drawer contains 12 red and 12 blue socks, all unmatched. A person takes socks out at random in the dark. How many socks must he take out to be sure that he has at least two blue socks? A. 14 B. 35 C. 18 D. 28 (4) Given that 0 = 1, = + ( 1)1 for 1. What is the value of 4? A. 1 B. 5 C. 4 D. 8 (5) When four coins are tossed simultaneously, in _______ number of the outcomes at most two of the coins will turn up as heads. A. 17 B. 28 C. 43 D. 11 (6) Imagine a test with 20 questions where each question has two possible answers. They are not true/false questions - one or both or neither answer might be correct. Here is an example: Is discrete mathematics fun for mathematics students? for computer science students?

2 How many possible ways to answer all the questions on that test? A. 220 B. 320 C. 420 D. 80 (7) The number of binary strings of length 8 either start with a '1' bit or end with two bits '00' is A. 128 B. 160 C. 64 D. 192 (8) Suppose there are three lists of projects of sizes 3, 5, and 10 respectively. In how many ways can a person choose a project from these three lists of projects. A. 150 B. 25 C. 18 D. 53 (9) Below are the steps for proving that 4|(22 +6) for all positive integer values of by using induction I. 2 02 +6 0 = 0, which is divisible by 4 II. 2 12 +6 1 = 8, which is divisible by 4 III. 2 22 +6 2 = 20, which is divisible by 4 IV. Assume 4|(22 +6) for an arbitrary V. Then prove 4|(2(+ 1)2 +6(+ 1)) Which of the following is correct? A. The sequence of the steps should be I, IV, V. B. The sequence of the steps should be II, IV, V. C. The sequence of the steps should be III, IV, V. D. The sequence of the steps should be IV, I, V. (10) How many ways can 5 prizes be given away to 4 students, if each student is eligible for all the prizes? A. 120 B. 625 C. 256 D. 128 (1) The base case for the inequality 7 > 3, where = 3 is 7 > 1 True False (2) In a party, 3 boys and 3 girls sit in a row. If no two people of the same sex are allowed to sit together, the number of ways is 36.

3 True False (3) Given the set {1, 2, 3, 4, 5}, the next larger combination of {1, 3, 5} is {1, 4, 5}. True False (4) Suppose student ID is in the given format - One alphabet, followed by 7 digits. The total number of IDs in this given format is 26 107 True False (5) The US Senate has 100 members. If the senators consist of 85 men and 15 women, the number of ways in which we can pick a committee of 10 senators consisting of 5 men and 5 women is (855 ) + (155 ). True False 3. (11 points) Find (2), (3), (4) when () is defined recursively by (0) = 1; (1) = 2 (+ 1) = () + 3 (1) 4. (11 points) Give a recursive definition of the sequence {}, = 1, 2, 3, if = 42. 5. (11 points) In a version of the BASIC programming language, the name of a variable is a string of 1 or 2 alphanumeric characters, where uppercase and lowercase letters are not distinguished. Moreover, a variable name must begin with a letter and must be different from the five strings of two characters that are reserved for programming use. How many different variables names are there?

4 6. (9 points) Generate the permutations of the integers 4,5,6 in lexicographic order. 7. (12 points) How many permutations of the letters A B C D E F G H contain (a) the string ED?