Mathematics 357 – Combinatorics Midterm Examination 1 February 24, 2017

Directions

Do any combination of parts of the following 5 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. Consider a rectangular 7 × 7 grid L of integer lattice points:

L = {(i, j) : 0 ≤ i ≤ 6, 0 ≤ j ≤ 6} ⊂ R^{2}.

A) (10) What is the smallest number n such that we have S ⊂ L with |S| = n, then some

three points in S must lie on the same horizontal line y = c for some 0 ≤ c ≤ 6. B) (10) How many lattice paths are there from (0, 0) to (6, 6) made up of segments moving

either up one unit or right one unit in the lattice?

II. Let X = {a, b, c, d, e} and Y = {1, 2, 3, 4, 5}. There are 5^{5} = 3125 functions f : X → Y by the Multiplication Principle (5 choices for f(a), 5 choices for f(b), etc.) A) (10) How many of these functions are not surjective (not onto)? B) (10) How many of the functions in part A satisfy |f(X)| = 2?

III. (15) k out of n cars in a lot are selected and each one of those gets an advertising flier for either a pizzeria or a car wash. By counting the ways the selection and distribution of the ads can be done in two ways, give a combinatorial argument establishing:

\binom{n}{0}\binom{n}{k} + \binom{n}{1}\binom{n − 1}{k − 1} + \binom{n}{2}\binom{n − 2}{k − 2} + ⋯ + \binom{n}{k}\binom{n − k}{0} = 2^{k}\binom{n}{k}

IV. A professor makes up a review sheet for an exam including 15 practice questions, grouped into parts I,II,III, each with 5 questions. The actual exam will consist of exactly 8 of the 15 practice questions.

A) (10) Taking the ordering of the problems on the actual exam into account, how many

different possible exams are there? B) (10) How many possible exams are there containing at least two questions from each

part, if we ignore the order in which the problems are listed?

V. A) (10) How many permutations are there in S_{16} with cycle type [4, 4, 3, 3, 2]? B) (15) State and prove the recurrence relation for the Stirling numbers of the first kind. C) (10) Using part B and the base cases for the s(n, 1), s(n, n) (or other methods as

appropriate), compute the Stirling number of the first kind s(6, 2).