Math 184A, Winter 2017, Prof. Tesler Homework #3, Due Wednesday February 1, 2017 Chapter 5# 6, 8, 12*, 26, 27; and the problems below, H-3 through H-8 (see both pages). *Note: On Chapter 5# 12, your answer should be in terms of the function p(n); you don’t need to know an explicit formula for p(n) to do this. Problem H-3. A “Simplex” lock has n buttons numbered 1,...,n. The combination XXXXXXXXXXmeans to press 3 and 5 together, then 4 and 2 together, then 1. The combination Ø means don’t push anything; just open it. Each group of buttons pushed must consist of at least one button. Buttons may not be used more than once, and it is not necessary to use all of the buttons. (a) How many combinations are there with a standard 5 button Simplex lock? (b) How many combinations are there with a standard 5 button Simplex lock if there are at most 3 groups of buttons pushed? (c) In (c)–(e), we’ll change the rules. Each part is separate; e.g., don’t combine the new rules on (c) and (d), just do them separately. How many combinations are there with a 5 button Simplex lock if all buttons must be used? (E.g., 35-2 is an invalid combination since 1 and 4 are not used.) (d) How many combinations are there on a 5 button lock with at most 3 pushes, if we only allow one button to be pushed at a time and do not allow buttons to be reused? (e) If the rules are changed so that each push has one or more buttons and you can reuse buttons (e.g., XXXXXXXXXXis considered valid), how many combinations would be possible on a 5 button lock using exactly 3 groups of pushes? How about on an n button lock using exactly k groups of pushes? Problem H-4. (a) Compute the Stirling numbers of the 2nd kind S(6, k) for 0 = k = 6, and the Bell number B(6). (b) How many set partitions of [15] have type (6, 2, 2, 1, 1, 1, 1, 1) (meaning one block of size 6, two blocks of size 2, and five blocks of size 1)? (c) Verify equation (5.2) on page 97 for the case n = 4. In other words, plug in n = 4, explicitly compute both sides of the equation as functions of x, and simplify to show they’re equal. Problem H-5. (a) Determine p(6) (number of integer partitions of 6). (b) Determine pk(6) (number of integer partitions of 6 into exactly k parts) for all values of k. (c) Match up the partitions of 6 that are conjugates. Identify any that are self-conjugate. (d) Determine the number of strict integer compositions of 6. (e) Determine the number of strict integer compositions of 6 into exactly k parts for all values of k. Problem H-6. (a) How many surjective (onto) functions f : [6] ? [3] are there? (b) How many injective (one-to-one) functions f : [3] ? [6] are there? Problem H-7. This is based on Chapter 8.1. However, you should already be able to do this problem using Taylor series from Math 20B and 20D. (a) Let an = n2 for integers n = 0. The generating function of an is f(x) = X8 n=0 an xn = X8 n=0 n2 xn . Derive an explicit formula for it as follows: • Start with the geometric series 1 1 - x = X8 n=0 xn for |x| < 1. • Differentiate both sides with respect to x. • Multiply both sides by x. • Differentiate again. • Multiply by x again. • Simplify the result, if needed. (b) Use the above result to compute X8 n=0 n2 3n . Problem H-8. Compute the coefficient of x2 in each of these (expanded as a polynomial or as a Taylor series centered at 0): (a) (3 + x + x2)(1 + 4x + x2)(1 + x + 5x2) (b) x(1 - x XXXXXXXXXXx)5 (c) (1 + x)(1 - 3x)/(1 - 10x)