# How many relations are there on the set $\{a, b, c, d\}$ that contain the pair $(a, a)$?

The number of relations between sets can be calculated using $2^{mn}$ where $m$ and $n$ represent the number of members in each set, thus total is $2^{16}$ .

Now how do I go ahead calculate only those that contains $(a, a)$ There are $4 \cdot 4=16$ pairs of one element from $A$ and one from other $A$.

Now if we always include a $(a, a)$ , so there will be $2^{16-1}$=$2^{15}$ relations.

This is what I think but I am confused. Please help me solve this sum.

• Yes, $2^{15}$ is correct. – Adriano Apr 30 '17 at 3:30

You are correct. The point of $2^{mn}$ formula is that there are $mn$ ordered pairs that might or might not be part of the relation. As you have two choices repeated $mn$ times there are $2^{mn}$ choices. When we say $(a,a)$ is required to be in the relation, one of those choices is already made, so there are $mn-1$ more to make. Thus there are $2^{mn-1}=2^{15}$ relations that include $(a,a)$
Since there are no conditions at all that the relation is required to satisfy, the presence of any particular pair $(x,y)$ in the relation can be varied independently of any other such pair. In particular, a relation selected (uniformly) at random among all relations has a probability $\frac12$ to contain the pair $(a,a)$. This is just another way to say that the subset of relations with that property has half the size of the full set.