Number of reflexive relations defined on a set A with n elements

Problem:

If a set $A$ has $n$ elements in it, how many reflexive relations can be defined on it?

My solution

Is the answer

summation of (n^2 - n)C(i) for i=0 to n^2 -n

$$\sum_{i=0}^{n^2-n} C(n^2-n,i) = \sum_{i=0}^{n^2-n} \binom{n^2-n}i$$

How?
well if i make a matrix $n\times n$ now the diagonal elements have to be selected,out of remaining $n^2-n$ any number of elements can be selected.

Solution 1:

Your idea is fine. For each place $(i,j)$ in the matrix that is not on the diagonal, say YES or NO depending on whether you want $R(i,j)$ to hold or not to hold. There are $2^{n^2-n}$ different ways of doing this.

Note that one can get that answer from yours. For in general, by the Binomial Theorem, $$(1+x)^m=\sum_{i=0}^m \binom{m}{i}x^i.$$ Put $m=n^2-n$ and $x=1$. On the right we get your expression, and on the left we get $2^{n^2-n}$.