0
$\begingroup$

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.

1 Answers 1

2

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}$.

  • 0
    ah ok i had problem with the terminology used2012-11-22