Question

May 6, 2019 Directions: Answer each question as completely as possible. Include all of your work and reasoning as partial credit will be given on the basis of incomplete or partially correct answers. Unless otherwise indicated, each question is worth two points 1. Find S(5,3) and P(5,3). Give exact answers for each 2. How many 4 number PIN numbers are possible? How many have at least one repeated digit? 3. Compute how many integer solutions there are for the equation z+++5x4 11, each 4. Give a combinatorial proof of the identity ()-()+) S(n,n-1)-n,n-1) G) 5. Prove a combinatorial proof If n 2 1 and 2 1, then P(nk) Pn-1,k-1)+Pn-k,k). 7. Let d) = 1 and d,.-nd,-1 + 1 for all n I. (This is a recurrence for the number of derangements of in). Solve this recurrence to find a formula for the number of derangements of Inl. (3 points) 8. Find concise OGFs for each of the following questions: a) How many ways are there to make change for a dollar? b) Question 3 above 9. Extract the coefficient of#k from dtz 7- (1 point) 10. Use the principle of inclusion/exclusion to find and prove a general ll. Let n 2 1 and let S be an (n +1)-subset of 12n]. Prove that there exist two numbers in whose sum is 2n +1.

Answer 1

ว่าไ m I 얘 K. mI

3 18 11, ר, 2, tM 2 113 36 13b L\ 1

M7) and 31- 3 21 2, 2,0) 2 put rm