Question

How many relations are there on a set with n elements that are neither reflexive nor irreflexive

Answer 1

Answer:

$\displaystyle 2^{n^2} - 2^{n^2-n+1}\\= 2^{n^2-n+1}\bigl(2^{n-1}-1\bigr)$

Step-by-step explanation:

Think of the relation as an n×n array of T/F values... T if the corresponding elements (row and column) are related, and F if they are not related.

As there are n² cells and each has two possible values, the total number of relations is $2^{n^2}$.

For a reflexive relation, all the cells along the main diagonal must be set to T.  That's n cells that have been filled so far.  There are then n² - n cells remaining, and these can be filled any way.  So the number of reflexive relations is $2^{n^2-n}$.

For irreflexive relations, the cells on the diagonal must be set to F.  The number of such relations is then the same as for reflexive relations.

The number of relations that are neither reflexive nor irreflexive is then

$\displaystyle 2^{n^2} - 2\times 2^{n^2-n} \\= 2^{n^2} - 2^{n^2-n+1}\\= 2^{n^2-n+1}\bigl(2^{n-1}-1\bigr)$