Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Module Code: MATH314301
Take home exam for Combinatorics School of Mathematics
Exam information: There are 4 pages to this exam. Answer all questions.
All questions are worth equal marks. This is an open book exam. Always explain your answers,
but keep your explanation brief. For each question your final answer must be consistent with
the calculation or explana- tion. Otherwise you will get no marks for the final answer, even if it is correct.
The work that you submit must be your own work. You must not ask others to help you to complete your
assessments. If we have reason to believe that work you have submitted does not represent your own
understanding, we will take this very seriously, investigating it and following the University’s established
procedures relating to academic malpractice. You must hand in your work using Gradescope.
Turn the page over Module Code: MATH314301 1. (a) How many ways are there to distribute
4 indistinguishable apples and 6 indistin- guishable bananas into 4 distinct lunch boxes in such a way that each lunch
box contains at least two pieces of fruit? Hint. This somewhat similar to Question 4 of Workshop 1 (but note that,
unlike the books, the bananas are indistinguishable). You should first list the types of distributions of the apples.
These are the partitions of 4. For each type you deter- mine then how many ways there are to distribute the apples and then how many ways there are to distribute the bananas. (b) Let O be a set of k (distinct) objects and let B be a set of n (distinct) boxes. Show by giving a 1-1 correspondence that the number of ways of distributing the objects from O into the boxes from B is the same as the number of functions from O to B. Express this number in terms of k and n. (c) Lemma 1.23 from the notes states: The number of solutions to e1 + · · ·+ en = k where the ei are nonnegative integers is ( n+k−1 n−1 ) = ( n+k−1 k ) . Give an alternative proof to the proof from the notes as follows. Step 1. Show that the solutions (e1, . . . , en) above are in 1-1 correspondence with the solutions to f1 + · · ·+ fn = n+ k, where the fi are integers ≥ 1. Step 2. Show that the solutions (f1, . . . , fn) from Step 1 are in 1-1 correspondence with the (n− 1)-element subsets of {1, 2, . . . , n+ k − 1}. Step 3. Show that Lemma 1.23 follows from Step 1 and Step 2. Hint. For Step 2 use the map (f1, . . . , fn) 7→ {s1, . . . , sn−1} where the si are given by si = f1 + f2 + · · ·+ fi. 2. (a) Explain in your own words why the coefficient of xn in the Euler product ∞∏ k=1 1 1− xk = ∞∏ k=1 (1 + xk + x2k + x3k + · · · ) is equal to the number of partitions of n. (b) Explain which partitions of n are counted by the coefficient of xn in 1 1− x ∗ (1 + x 2 + x4) ∗ 1 1− x3 . (c) Explain what the Stirling number S(7, 5) means in terms of partitions of a set and what it means in terms of surjective functions. (d) Compute the Stirling number S(7, 5) and explain your answer. Note. There are at least three different possible methods, one reasoning with partitions directly, and others using results from the notes. Page 2 of 4 Turn the page over Module Code: MATH314301 3. (a) Consider the following problem. We are given a set O of objects and a set C of containers and we want to distribute all objects from O into the containers from C. However, not any container can contain any object: for each object y ∈ O there is a set Cy ⊆ C of containers in which y can be put. Furthermore, we want no container to contain more than r objects, where r is an integer ≥ 1. i. In Workshop 4 Question 1(b) the following m-version of Hall’s Theorem was stated. Let A1, . . . , An be finite subsets of a set X and let m be an integer ≥ 1. Then (A1, . . . , An) has a system of representatives in which each element occurs at most m times if and only if m|⋃i∈J Ai| ≥ |J | for all J ⊆ {1, . . . , n}. Use this result to deduce a condition in terms of O, the Cy and r only such that the objects from O can be distributed into the containers from C with the given restrictions if and only if the condition holds. Explain carefully what each of the quantities X,Aj,m, n in the theorem correspond to in this problem. ii. The m-version of Proposition 6.5 from the notes is obtained by replacing k by m ∗ k in condition (b). Deduce from this result a condition in terms of O, the Cy and r only such that the objects from O can be distributed into the containers from C with the given restrictions if the condition holds. Show that this condition is satisfied for r = 2 in an explicit example of your own devising with 2 ≤ |C| < |O| ≤ 4. (b) i. Illustrate the application of Proposition 6.5 in the proof of Proposition 7.4 in the notes with an explicit example where n = 3 or 4. ii. A permutation pi of {1, . . . , n} is called cyclic if, for some m ≥ 1 and an m-subset S = {a1, . . . , am} of {1, . . . , n}, we have pi(ai) = ai+1 for i ∈ {1, . . . ,m − 1}, pi(am) = a1 and pi(x) = x for x /∈ S. Now take n = 4. Let a, b, c, d ∈ {1, 2, 3, 4} be distinct. Explain how many Latin squares of order 4 there are whose first row is (a, b, c, d) and whose second row is obtained from the first by applying a cyclic permutation. Hint. Note that in our situation we must have m = n = 4 for the cyclic permutation (Why?). Page 3 of 4 Turn the page over Module Code: MATH314301 4. (a) Let X = {1, . . . , 7}. i.
What is the maximal size of an intersecting family of subsets of X? Give one
explicit example of an intersecting family F of maximal size such that for each x ∈ X
there is an A ∈ F such that x /∈ A. Explain why your example satisfies these criteria. ii.
What is the maximal size of an Sperner family of subsets of X? Give one explicit example of a
Sperner family of maximal size (you don’t have to write it out completely). (b) A town has 7000 inhabitants.
Within each week each inhabitant visits each su- permarket in the town at most once.
During a particular week the town has had more than 21000 supermarket visits by its inhabitants and each supermarket had at most 3000 visits.
Explain why at least one inhabitant must have visited at least 4 supermarkets and why the town must have at least 8 supermarkets.
(c) Let G = (V,E) be a complete graph with a red-blue edge colouring. For v ∈ V let X(v) be the set of vertices connected to v
with a red edge and let Y (v) be the set of vertices connected to v with a blue edge. Show that, when |V | is odd,
there must be a v ∈ V with |X(v)| and |Y (v)| even. Page 4 of 4 End.