# How do you compute the number of reflexive relation?

Given a set with $n$ elements

I know that there is $2^{n^2}$ relations, because there are $n$ rows and $n$ columns and it is either $1$ or $0$ in each case, but I don't know how to compute the number of reflexive relation. I am very dumb. Can someone help me go through the thought process?

-

A relation is reflexive if and only if every entry on the main diagonal of its matrix is $1$; that’s the only restriction. Fill in $1$’s on the diagonal, and you can put either $0$ or $1$ freely into every other entry in the matrix and have the matrix of a reflexive relation. Thus, the number of reflexive relations on a set of $n$ elements is $2^m$, where $m$ is the number of entries that are not on the diagonal. There are $n^2$ entries altogether, and $n$ of them are on the diagonal, so how many are not on the diagonal? And then how many reflexive relations are there?

-
it's 2^(n^2-n)? – George Nov 22 '12 at 3:48
@George: It is indeed. – Brian M. Scott Nov 22 '12 at 3:51
I'm confused on why it's $2^{n^2-n}$. If there are $2^n$ elements on the diagonal that make it reflexive then why is the final answer the entries that are not on the diagonal? – stumped Apr 20 at 17:02
@stumped: There are $n$ elements on the diagonal, and since we want a reflexive relation, all of them have to be $1$: we have no choice about them. Each of the other $n^2-n$ entries, however, can be either $0$ or $1$ without affecting the reflexivity of the relation. Thus, in building the matrix we have a $2$-way choice for each of those $n^2-n$ entries and no choice at all for the other $n$ entries; there are $2^{n^2-n}$ different ways to make those choices and hence $2^{n^2-n}$ different reflexive relations. – Brian M. Scott Apr 20 at 21:22

Strange way you have to count the number of relations...A relation on a set $\,A\,$ is just a subset of the cartesian product $\,A\times A\,$, and if $\,|A|=n\Longrightarrow |A\times A|=n^2\Longrightarrow\,$ the number of subsets of $\,A\times A\,$ , i.e. $\,|P(A\times A)|\,$ , is $\,2^{|A\times A|}=2^{n^2}\,$...

Now, you need to count all the subsets of $\,A\times A\,$ that contain the diagonal $\,\Delta_A:=\{(a,a)\in A\times A\}\,$ , so...can you take it form here?

-