Answer to Question #146306 in Discrete Mathematics for Promise Omiponle

Question

Let S be a set with 6 elements and let a and b be distinct elements of S. How many relations R are there on S such that...
(a) (a, b) ϵ R?
b) (a; b) ∉ S?
(c) no ordered pair in R has a as its first element?
(d) at least one ordered pair in R has a as its first element?
(e) no ordered pair in R has a as its first element or b as its second element?

Answer 1

$\text{Given the set S and } |S|=6 \\ \text{ the number of ordered pair to be found in S is given by} \\ |S\text{x}S|=6^2=36 \\ \text{ Now since a and b are distinct element of S then } a\neq b \\ \text{Then the number of ordered pairs with the same first and second element is 6 }\\ (a) \text{Then the number of relations such that }(a,b)\in R \text{ is }2^{36-6}=2^{30}\\ (b)\text{The number of relations such that } (a,b)\notin R =2^6\\ (c) \text{Since there are 36 ordered pairs then there are 6 ordered pairs that start with a} \\ \text{then number of ordered pairs without a as its first element is 36-6=30} \\ \implies \text{there are }2^{30}\text{ of such relations }\\ (d) \text{Since there are }2^{30} \text{ relations without a as their first element then the number of}\\ \text{ such relations that will have a as their first element is } 2^{36}-2^{30}\\ (e)\text{Since there are 6 ordered pairs with a as their first element and b as their} \\ \text{second element is also 6 then by the principle of inclusion and exclusion we have } \\6+6-1=11 \text{ such ordered pairs then we have } 2^{36-11}=2^{25} \text{ relations without a} \\ \text{ as the first element or b as the second element.}$