Mathematics 357 – Combinatorics Midterm Examination 2 – April 7, 2017

Directions

Do any combination of parts of the following problems in the blue exam book. (The exam will be scored out of 100 points, but you have the possibility of accumulating up to 110 points if you do all the parts.) Explain your reasoning fully and do not place any work on the exam sheet. Relax, and read each question carefully before starting to work!

I. A) (5) What is the definition of the Stirling number of the second kind, S(n, k), in terms

of distribution problems? B) (15) State and prove the recurrence relation for the S(n, k). C) (5) Determine the Stirling number S(6, 2).

II. For all parts of this question, express the number of distributions in terms of partition numbers, Stirling numbers, binomial coefficients, etc. You do not need to evaluate any of these to a single number. A) (5) How many ways are there to distribute 10 identical unmarked pads of paper into

4 piles, with no restrictions on the sizes of the piles? B) (5) How many ways are there if the piles of pads are supposed to go to 4 numbered

tables and at least one pad goes to each table? C) (5) How many ways are there if the pads have 10 different colors of paper but we’re

back in the situation of part A (i.e. just 4 piles, not the 4 numbered tables)? D) (5) What changes in part C) if every table gets at least one pad?

III. (15) 100 pencils are divided into four lots of sizes x_{1}, x_{2}, x_{3}, x_{4}, each a multiple of 5, and placed in 4 classrooms. Room 1 receives at least 20 pencils, room 2 receives no more than 40 pencils, room 3 receives between 15 and 25 pencils, and room 4 receives a number of pencils that is a multiple of 10. How many different vectors (x_{1}, x_{2}, x_{3}, x_{4}) of numbers of pencils satisfy these conditions? Set up an appropriate generating function and explain how you would use it to answer this question.

IV. (15) For each n ≥ 1, let T_{n} be the number of ways of arranging n “triominoes” (like dominoes, but 3 × 1) in a 3 × n tray with no overlapping. Find a recurrence relation of order 3 for the T_{n} sequence and the initial values T_{1}, T_{2}. (Don’t try to solve the recurrence.)

V. A) (20) A sequence R_{n} is defined by the recurrence R_{n} = 6R_{n−1} − 8R_{n−2}. Express the

generating function of the sequence R_{n} as a rational function of x if the initial terms are R_{0} = 3, R_{1} = 1 and use it to derive a formula for R_{n} as a function of n. (Partial credit 10 for solution by the “shortcut” method.)

B) (15) Now suppose we wanted to solve R_{n} = 6R_{n−1} − 8R_{n−2} + 2^{n}. What would be the appropriate “good guess” for the particular solution? See table from Beeler on back. Determine the solution of this recurrence with the initial conditions R_{0} = 1, R_{1} = 1.