permutation on relations

Question

Let $A = \{1, 2, 3, 4\}$. Call a binary relation on $A$ interesting if it is symmetric or it does not contain the pair $(1, 4)$. How to calculate the number of interesting binary relations on $A$. My approach was

1. no of relation that does not contain $(1,4)$ is $2^{16}-2^{15}$
2. no of relation that are symmteric is $\dfrac{2^{4\cdot 4+4}}2 = 2^{10}$ total no of function are 1+2

Is my approach correct?

Answer 1

Your counts for groups 1 and 2 are correct, but your strategy gets the wrong answer, because some of the relations are symmetric and also do not contain $(1,4)$, and if you simply add groups 1 and 2 you will have counted these twice.

To get this right, you need to count a third group: the set of permutations that are symmetric and also do not contain $(1,4)$, and then the correct count of interesting relations will be group 1 plus group 2 minus group 3, by the inclusion-exclusion principle.