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 .

Waiting for your reply!

  • $\begingroup$ Saying that $a\,R\,a$ for all $a$ doesn't preclude $a\, R \,b$ for some $b\neq a$. $\endgroup$ – lulu Nov 13 '20 at 15:43
  • $\begingroup$ Suppose the set is $\{1,2\}$ then $\{(1,1),(2,2),(1,2)\}$ is also reflexive, you are forgetting other elements. $\endgroup$ – 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}}.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.