7
$\begingroup$

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.

  • 0
    These questions are similar to this one: http://math.stackexchange.com/questions/12139/number-of-relations-that-are-both-symmetric-and-reflexive and http://math.stackexchange.com/questions/15108/how-many-symmetric-relations-on-a-finite-set2011-12-03

1 Answers 1

6

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

  • 0
    yeah.. thanks.. :)2011-12-03