Take the 2-minute tour ×

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.

share|improve this question

marked as duplicate by Isaac Solomon, Per Manne, Martin Sleziak, Norbert, Noah Snyder Nov 22 '12 at 9:00


1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
I didn't really understand anything. –  George Nov 22 '12 at 5:29
Is there a way to get to n(n+1)/2 just by counting? –  George Nov 22 '12 at 5:30
I thought I did this, in two different ways. We are counting the number of places in an $n\times n$ matrix that are on the main diagonal or below. In the first row there is $1$ such place. In the second row there are $2$. In the third row there are $3$. And so on. In the last row there are $n$. So the number of places is $1+2+\cdots+n$. By the usual formula for the sum of an arithmetic progression, this is $n(n+1)/2$. Or else if you prefer I can phrase things in terms of binomial coefficients. –  André Nicolas Nov 22 '12 at 5:36
ah ok i had problem with the terminology used –  George Nov 22 '12 at 5:37
