# Number of reflexive relations on the set {1,2,…,n}

I am solving questions of a bachelors exam and was unable to solve this question and i am looking for help!!

Find Number of reflexive relations on the set {1,2,...,n}.

I know that R is called reflexive if for every a $$\in$$R a R a. But when I used it here 1 got that there would be only 1 reflexive relation ie each element goes to itself but that's wrong according to answers.

I don't have any idea on how too approach the question .

• Saying that $a\,R\,a$ for all $a$ doesn't preclude $a\, R \,b$ for some $b\neq a$. – lulu Nov 13 '20 at 15:43
• Suppose the set is $\{1,2\}$ then $\{(1,1),(2,2),(1,2)\}$ is also reflexive, you are forgetting other elements. – PNDas Nov 13 '20 at 15:43
As the set $$S=\{1,2,\ldots, n\}$$ has $$n$$ elements, the set of all pairs of elements in $$S$$ (i.e. $$S\times S$$) has $$n^2$$ elements.
Out of those, $$n$$ pairs are of the form $$(x,x)$$ for $$x\in S$$. Those pairs must belong to a reflexive relation $$R$$. As for the remaining $$n^2-n$$ pairs, each of them may or may not belong to the relation $$R$$, so the number of potential candidates for $$R$$ is $$2^{n^2-n}$$.
But you can have whatever relation you want for $$aRb$$ with $$a\neq b.$$ Show that there are $$2\binom{n}{2}$$ of them. And either they are there or not. Giving a total of $$2^{2\binom{n}{2}}.$$