Week 3 homework
Exercise 7.1, problem 10a
The total number of pairs we can either include or not is 4^2-4=16. Any reflexive relation is a subset of this set of 12 elements; we know there are 2^12 such subsets.
Problem 10b
The number of decisions we can make for any symmetric relation is 4+ (16-4)/2=4+6=10.
The number of possible symmetric relations is 210.
Exercise 7.2, Problem 15a
a) Draw the digraph G1 (V1, E1) where V1 {a, b, c, d, e, f } and E1 {(a, b), (a, d), (b, c), (b, e), (d, b),
(d, e), (e, c), (e, f), (f, d)}.

Exercise 7.3, Problem 1
Draw the Hasse diagram for the poset ⊆, where{1, 2, 3, 4}.
(1,1)<(1,2)<(1,3)<(1,4)<(2,1)<(2,2)<...<(4,3)<(4,4 ). o------o------o------o------o------o--- ... ---o------o (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) ... (4,3) (4,4)

3
1
2
4
3
1
2
4

Problem 6a . For A {a, b, c, d, e}, the Hasse diagram for the poset
(A, R) is shown in Fig. 7.23. (a) Determine the relation matrix for R. a b c d e a 1 1 1 0 0 b 1 1 0 1 0 c 1 0 1 1 0 d 0 1 1 1 0 e 1 0 0 0 1
Exercise 7.4, Problem 1a
Determine whether each of the following collections of sets is a partition for the given set A. If the collection is not a partition, explain why it fails to be.
a) A {1, 2, 3, 4, 5, 6, 7, 8}; A1 {4, 5, 6}, A2 {1, 8}, A3 {2, 3, 7}.
The Question A is a partition.
Problem 2a
There are only three ways, corresponding to the partition A_1 = {1,2,8}, A_2 = {3,4}, A_3 = {5,6,7}, the partition A_1 = {1,2}, A_2 = {3,4,8}, A_3 = {5,6,7}, and the partition A_1 = {1,2}, A_2 = {3,4}, A_3 = {5,6,7,8}. The point is that the given requirements almost completely determine the sets A_1 and A_2 and A_3; we just need to choose which set 8 goes into, and there are three different choices we can make in doing that.
Exercise 8.1, Problem 4
A = members that bring hot dog B= members that bring fried chicken C = members that bring salads D = members that bring desserts n(A) = 21 n(B) = 35 n(C) = 28 n(D) =32 n(A∩B) = 13 ; n(A∩C)=10; n(A∩D) = 9; n(B∩C) = 12 ; n(B∩D)=17 ; n(C∩D)=14; n(A∩B∩C)=4 ; n(A∩B∩D)=4; n (A∩C∩D)=5;n(B∩C∩D)=7 ;n(A∩B∩C∩D)= 2
a) 7
b) Zero
c) 17
Problem 12
C (n,r)= n!/r!(n-r)! =12! /9! (12-9)! = 220 220 entries = Troy has 220 ways to select nine marbles from a bag of twelve.
Exercise 8.2, Problem 4
a) We need to find the number of sequences with exactly 4 distinct numbers. There are (7 choose 4) ways of choosing four numbers, say a_1, a_2, a_3, a_4 from the numbers 1 through 7. Now we need to find the number of sequences that contain the selected numbers a_1, a_2, a_3, a_4 each at least once, but contain no other numbers.
There are 4^10 sequences that contain no other numbers besides a_1, a_2, a_3, a_4. Now we restrict our attention to these 4^10 sequences only.
Out of these 4^10 sequences, the number of sequences that are *missing* at least one of a_1, a_2, a_3, a_4, by the inclusion-exclusion principle, is sum of numbers of sequences missing a_i's taken one at a time - sum of numbers of sequences missing a_i's taken two at a time + sum of numbers of sequences missing a_i's taken three at a time - sum of numbers of sequences missing a_i's taken four at a time = (4 choose 1)*3^10 - (4 choose 2)*2^10 + (4 choose 3)*1^10 - (4 choose 4)*0^10. So the number of sequences that contain the selected numbers a_1, a_2, a_3, a_4 each at least once, but contain no other numbers, is 4^10 - (4 choose 1)*3^10 + (4 choose 2)*2^10 - (4 choose 3)*1^10 + (4 choose 4)*0^10. Therefore, the overall number of sequences with exactly 4 distinct numbers (i.e. the number of functions satisfying |f(A)| = 4) is (7 choose 4) * [4^10 - (4 choose 1)*3^10 + (4 choose 2)*2^10 - (4 choose 3)*1^10 + (4 choose 4)*0^10] = 35*(1048576 - 4(59049) + 6(1024) - 4(1) + 0) = 28648200. b) We need to find the number of sequences with at most 4 distinct numbers. The number of sequences with exactly 1 distinct number is clearly 7. Using similar reasoning as in part a), we find that the numbers of sequences with exactly 2, 3 distinct numbers, respectively, are (7 choose 2) * [2^10 - (2 choose 1)*1^10 + (2 choose 2)*0^10] = 21462, and (7 choose 3) * [3^10 - (3 choose 1)*2^10 + (3 choose 2)*1^10 - (3 choose 3)*0^10] = 1959300. From part a) the numbers of sequences with exactly 4 distinct numbers is 28648200. Therefore, the overall number of sequences with at most 4 distinct numbers (i.e. the number of functions satisfying |f(A)| <= 4) is 7 + 21462 + 1959300 + 28648200 = 30628969.