Thread: Number of relations

Okay. So I really need to understand how to do this problem, because nowhere does it say anything in my text about finding the number of relations. Thanks.

Let A = {1,2,3,4,5} and B = {w,x,y,z}
How many relations that
(i) contain (1,w)?
(ii) do not contain (5,z)
(iii) contain (1,w) but not (5,z)

Originally Posted by jasone

Okay. So I really need to understand how to do this problem, because nowhere does it say anything in my text about finding the number of relations. Thanks.

Let A = {1,2,3,4,5} and B = {w,x,y,z}
How many relations that
(i) contain (1,w)?
(ii) do not contain (5,z)
(iii) contain (1,w) but not (5,z)

are there any restrictions on our relations? do they have to be functions? etc

That's all the question said.

I can see that some of the relations from A to B are the empty set, {(1,w)}, {(1,x)}, {(1,w), (1,x)}, {(2,w), (3,z), (5,x)}, and A x B, for example.

A x B = {(1,w), (1,x), (1,y), (1,z), (2,w), (2,x), (2,y), (2,z), (3,w), ... , (5,y), (5,z)}

But how do I count all of the relations that have (1,w), for instance?

Originally Posted by jasone

That's all the question said.

I can see that some of the relations from A to B are the empty set, {(1,w)}, {(1,x)}, {(1,w), (1,x)}, {(2,w), (3,z), (5,x)}, and A x B, for example.

A x B = {(1,w), (1,x), (1,y), (1,z), (2,w), (2,x), (2,y), (2,z), (3,w), ... , (5,y), (5,z)}

But how do I count all of the relations that have (1,w), for instance?

note that |A x B| = 5(4) = 20

so lets say we want relations with (1,w), how can we find all of them?

well, one is {(1,w)}

then we can make one with (1,w) and 1 of the other elements, then one with (1, w) and 2 of the other elements, then one with (1,w) and 3 of the other elements, ...., and finally one with (1,w) and all of the other 19 elements.

how would you count all of those?

I got the series 1 (being {(1,w)}) + 19 (choices for a 2nd element) + 19C2 (2 other choices) + 19C3 + ... + 19C17 + 19 + 1
So the finite sum (from i=0 to n=19) nCi would get the answer?

Or in other words, 2^19 = 524288. Is that right?

And for part (ii), I tried 1 (being the empty set) + 19 (choices for one element) + 19C2 + ... + 19C17 + 19 + 1 (all 19 elements).

In other words, again, 2^19. Same answer. Is that right?

And for part (iii), 1 + 18 + 18C2 etc for an answer of 2^18.

Did I do all of this correctly?

Originally Posted by jasone

Okay. So I really need to understand how to do this problem, because nowhere does it say anything in my text about finding the number of relations.
Let A = {1,2,3,4,5} and B = {w,x,y,z}, How many relations that
(i) contain (1,w)?
(ii) do not contain (5,z)
(iii) contain (1,w) but not (5,z)

This problem always affords such a wonderful teaching opportunity. I cannot resist.

As already noted, there are a total of possible relations from A to B.
These are often called binary relations. This problem in part shows why.
Any one of the relations either contains the pair (1,w) or it does not. Think binary.
So half of the total number of relations contains the pair and half do not.
Half of is . That answers both (i) & (ii).
Half of the relations containing (1,w) also contain (5,z), half do not.
Again, half of is .
Note that is one fourth of .