Possible Duplicate:
How Many Symmetric Relations on a Finite Set?
I know the answer is $2^\frac{n\space(n+1)}{2}$, but where the $\frac{n(n+1)}{2}$ comes from?
I am trying to think of an intuitive way to get to that expression, but I just can't.
Possible Duplicate:
How Many Symmetric Relations on a Finite Set?
I know the answer is $2^\frac{n\space(n+1)}{2}$, but where the $\frac{n(n+1)}{2}$ comes from?
I am trying to think of an intuitive way to get to that expression, but I just can't.
Order the elements of our domain in some arbitrary way.
For any $x\lt y$ we are free to decide whether $xRy$ holds. Once we have decided this, whether $yRx$ holds is determined.
And for any $x$ in our domain, we are free to decide whether the relation $xRx$ holds.
There are $\frac{n(n-1)}{2}$ ordered pairs $(x,y)$ with $x\lt y$. Add to this the $n$ possible values of $x$. The sum is $\frac{n(n+1)}{2}$. So there are $\frac{n(n+1)}{2}$ places where we can make a yes/no choice. Thus the number of symmetric binary relations is $2^{\frac{n(n+1)}{2}}$.
In terms of the matrix of $0$'s and $1$'s that describes the relation, we can decide arbitrarily on the main diagonal ($n$ places). That leaves $\frac{n^2-n}{2}$ places in the matrix. We can also decide arbitrarily the entries of the matrix below the main diagonal. And $n+\frac{n^2-n}{2}=\frac{n(n+1)}{2}$.