Let A = {1,2,..,n}.

What is the number of antisymmetric relationships on the set A?

The answer is apparently 2^n * 3^((n^2-n)/2), but I don't know the proof.

Thanks

Printable View

- Feb 23rd 2011, 04:13 AMdurrrrrrrrNumber of antisymmetric relationships
Let A = {1,2,..,n}.

What is the number of antisymmetric relationships on the set A?

The answer is apparently 2^n * 3^((n^2-n)/2), but I don't know the proof.

Thanks - Feb 23rd 2011, 04:54 AMemakarov
If you represent an antisymmetric relation as a matrix, this matrix, call it A, can have either 0 or 1 on the diagonal. Let A[i, j] denote the element of A in row i and column j. If i <> j, then one or both of A[i, j] and A[j, i] must be 0, so there are three possibilities for the pair of locations (i, j) and (j, i).