MAT344H1Y– Problem Set 6 Introduction to Combinatorics
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MAT344H1Y– Problem Set 6
Introduction to Combinatorics
Due: July 2, 11PM
Complete the following exercises from the textbook in § 7 but do not submit them for credit: . 1-25, 27. Look at 26 as well and give it a think.
Complete the following problems for credit. You must link to the problems on Gradescope. Answer all questions with full and complete explanations. The textbook is a good guide for what standard we are expecting of your explanations. Some questions may not be graded closely so that others may be focused on more closely in grading.
1. Given points A = (x1 ,y1 ),B = (x2 ,y2 ) ∈ Z2 , we say A ⪯ B if x1 ≤ x2 and y1 ≤ y2 . We have that if A ⪯ B and B ⪯ A that A = B, and we will write A ≺ B if A ⪯ B but A 
B . We have that if A ≺ B and B ≺ C then A ≺ C, but given any two distinct A and B it need not be the case that either A ≺ B or B ≺ A (the set of all B so that A ≺ B is all the points “above and to the right”of A). This sort of relation is called a partial order.
We say that a lattice path avoids P ∈ Z2 if it does not traverse along P, and we’ll say that it goes through P if it does traverse along P .
(a) Suppose that A = (x1 ,y1 ), B = (x2 ,y2 ), C = (x3 ,y3 ) are points in Z2 . Show that there
are no lattice paths from A to C that go through B unless A ≺ B ≺ C . Give a formula for the number of such lattice paths in that case.
(b) Show that if P1 , . . . ,Pn are n points in Z2 , then the number of lattice paths from A to B
that go through P1 , . . . ,Pn is 0 unless (up to relabelling the order of P1 , . . . ,Pn ) we have A ≺ P1 ≺ ... ≺ Pn ≺ B . Give a formula for the number of such lattice paths in that case.
(c) Use the inclusion exclusion principle for calculating how many lattice paths there are from (0, 0) to (10, 10) that avoid the points (0, 5), (5, 0), (0, 10), (5, 5), (10, 0), (5, 10), and (10, 5). (Hint: it would be very difficult to try to deal with all subsets of a 7 point set, so you should think about which of these subsets contribute 0 to the sum).
2. Suppose that P1 , . . . ,Pn are some propositions that may be true or untrue for elements of a set
X . Recall that for i ∈ [n] and I ⊆ [n], we write:
Ai = {x ∈ X : Pi (x) is true}
AI = {x ∈ X : Pi (x) is true for all i ∈ I}
(by convention A∅ = X, and we have Ai = A{i} as shorthand). The inclusion-exclusion principle gives a formula for the number of elements, x, for which Pi (x) is not true for all i ∈ [n] (alternatively, it gives the size of n
Ai , the complement of the set of elements for which all propositions are false). We will now seek a more refined formula. For a subset I ⊆ [n], define the set:
BI = {x ∈ X : Pi (x) is true for i ∈ I, and Pj (x) is false for j \∈ I}
(a) Explain why:
工 |BI | = |X|
I⊆[n]
(b) Draw a Venn diagram with 3 circles and label each of the 8 subsets BI for I ⊆ [3].
(c) Use the principle of inclusion-exclusion to show that:
|BI | = 工 (−1)|J/I||AJ |
J⊆[n]
I⊆J
(here the notation J/I means J/I = {j ∈ J : j \∈ I})
(d) Refer to exercise 1 in chapter 7 of the textbook. We will call a student a picky eater if they don’t like any of the flavours. We will call them a moderately picky eater if they like exactly one of the flavours. Calculate how many picky eaters there are and how many moderately picky eaters there are.
2023-07-01