Mathematics 357 – Combinatorics Solutions for Midterm Examination 1 February 24, 2017

I. Consider a rectangular 7 × 7 grid L of integer lattice points:

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

A) What is the smallest number n such that if 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. Solution: (This one should “smell like” the Pigeonhole Principle if you’re thinking the right way! Think: “pigeons” = the points in S; “pigeonholes” = the 7 horizontal lines containing points in L. A pigeon goes in a pigeonhole if the point lies on that line.) The smallest such number is 15. By the Generalized Pigeonhole Principle, if we have 15 points, then some horizontal line must contain strictly more than ⌊\frac{15−1}{7}⌋ = 2 points. (A subset of 14 points equally distributed with 2 on each horizontal line shows that |S| = 14 is not large enough.)

B) 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? Solution: By “dividers” or “stars and bars,” the number is \binom{6+6}{6} = \binom{12}{6} = 924.

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) How many of these functions are not surjective (not onto)?

Solution: Since |X| = |Y |, f : X → Y is not surjective if and only it is not injective. There are 5! = 120 injective functions, so 3125 − 5! = 3005 of the functions are not injective and hence not surjective.

B) How many of the functions in part A satisfy |f(X)| = 2?

Solution: The statement |f(X)| means that the range or image of the function consists of just two of the elements of Y. There are \binom{5}{2} = 10 choices for the image as a subset of Y. Then for each image, there are 30 different ways to construct mappings with that image. For instance, if the image is {1, 2}, then

• There are \binom{5}{1} = 5 different functions with one element in X mapping to 1 and four elements in X mapping to 2, or equivalently |f^{−1}({1})| = 1 and |f^{−1}({2})| = 4. The element mapping to 1 can be any one of the 5 elements of X, and then the other four elements in X map to 2.

• Similarly, there \binom{5}{2} = 10 different functions with |f^{−1}(\{1\})| = 2 and |f^{−1}(\{2\})| = 3

• \binom{5}{3} = 10 different functions with |f^{−1}(\{1\})| = 3 and |f^{−1}(\{2\})| = 2

• \binom{5}{4} = 5 different functions with |f^{−1}(\{1\})| = 4 and |f^{−1}(\{2\})| = 1. (Note that we cannot have either |f^{−1}({1})| = 0 or |f^{−1}({1})| = 5 since then we would not be “hitting” one of the elements of {1, 2} in the image.) By the Multiplication and Addition Principles, then the total number is

\binom{5}{2} · (\binom{5}{1} + \binom{5}{2} + \binom{5}{3} + \binom{5}{4}) = 10 · (5 + 10 + 10 + 5) = 300.

III. 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}

Solution: If we choose the cars first, then there are \binom{n}{k} different k-subsets of the n cars on the lot. For each of them, we have 2 choices for the flyer, either the pizzeria flier or the car wash flier. Hence the total number of choices of cars and assignments of fliers is 2^{k}\binom{n}{k} by the Multiplication Principle. On the other hand, if we assign the fliers as we select the cars, then the number of selections where

• all chosen cars get car wash fliers is \binom{n}{0}\binom{n}{k}

• one chosen car gets a pizzeria flier and the other k − 1 chosen get car wash fliers is

\binom{n}{1}\binom{n−1}{k−1}

• two chosen cars get a pizzeria flier and the other k − 2 chosen get car wash fliers is \binom{n}{2}\binom{n−2}{k−2}.

• Similarly, for each ℓ, 0 ≤ ℓ ≤ k, the term

\binom{n}{ℓ}\binom{n − ℓ}{k − ℓ}

represents the number of ways of picking ℓ cars to get pizzeria fliers, and then picking k − ℓ cars from the remaining n − ℓ cars to get the car wash fliers.

By the Addition Principle we have

∑_{ℓ=0}^{k} \binom{n}{ℓ}\binom{n − ℓ}{k − ℓ} = 2^{k}\binom{n}{k}.

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

A) Taking the ordering of the problems on the actual exam into account, how many different possible exams are there? Solution: (Note: The subdivision of the review sheet into parts I,II,III is irrelevant for this part.) The total number of exams (ordered) is

P (15, 8) = 15 · 14 · 13 · 12 · 11 · 10 · 9 · 8 = 259459200.

B) 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?

Solution: We can start by considering the number of ways of writing 8 = a_{1} + a_{2} + a_{3} where 2 ≤ a_{i} ≤ 5 is the number of problems taken from part i = I, II, III. If we write a_{i} = 2 + b_{i}, then 2 = b_{1} + b_{2} + b_{3} and 0 ≤ b_{i} ≤ 3. There are clearly only 6 ways to choose the b_{i}:

(b_{1}, b_{2}, b_{3}) ∈ {(2, 0, 0), (0, 2, 0), (0, 0, 2), (1, 1, 0), (1, 0, 1), (0, 1, 1)}

which correspond to breakdowns of questions between the three parts of the review sheet like this:

{(4, 2, 2), (2, 4, 2), (2, 2, 4), (3, 3, 2), (3, 2, 3), (2, 3, 3)}

Then taking into account the actual questions chosen from each part, we have that the total number of exams is

3 · \binom{5}{4} · \binom{5}{2} · \binom{5}{2} + 3 · \binom{5}{3} · \binom{5}{3} · \binom{5}{2}.

V. A) How many permutations are there in S_{16} with cycle type [4, 4, 3, 3, 2]?

Solution: The number is

\frac{1}{2!} (\frac{P (16, 4)}{4} · \frac{P (12, 4)}{4}) · \frac{1}{2!} (\frac{P (8, 3)}{3} · \frac{P (5, 3)}{3}) · \frac{P (2, 2)}{2}

B) State and prove the recurrence relation for the Stirling numbers of the first kind. Solution: The recurrence is

s(n + 1, k) = n · s(n, k) + s(n, k − 1).

The proof is as follows: s(n + 1, k) counts the number of permutations in S_{n+1} with cycle index k. This collection of permutations is the disjoint union of two subsets: The permutations with cycle index k that satisfy σ(n + 1) = n + 1 and the ones with σ(n + 1) ≠ n + 1. In the first case, (n + 1) will be a cycle of length 1 in the disjoint cycle decomposition. The remainder then consists of k −1 cycles not containing n+1. Hence these permutations are in 1-1 correspondence with the permutations in S_{n} with cycle index k − 1, and that number of such is s(n, k − 1). The permutations of the second type are all formed by inserting n + 1 in one location in a permutation in S_{n} with cycle index k. There are exactly n possible ways to insert the n + 1, so there are n · s(n, k) of these by the Multiplication Principle. The recurrence relation then follows by the Addition Principle.

C) 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). Solution: We have, since s(n, 1) = (n − 1)! and s(3, 2) = 3:

s(6, 2) = 5 · s(5, 2) + s(5, 1)
= 5 · (4 · s(4, 2) + s(4, 1)) + 24
= 20 · (3 · s(3, 2) + s(3, 1)) + 30 + 24
= 60 · 3 + 40 + 30 + 24
= 274.