Number of relations on a set with n elements

Question

Let $A$ be a set with $n$ elements.

How many (1)symmetric, (2)anti-symmetric and (3)asymmetric relations are there on $A$ ?

(4)How many linear relations are there ?

Here's what I did:

1. For symmetric, for every $n$ there are $n$ options, multiply all of them and remove all the duplicates we'll get $n^n-n$

2. For antisymmetric, there can only be relations of one kind: $(x,x)$ so we'll get $n$ relations.

3. For asymmetric, I start to run into trouble because for every relation there are fewer possible relations. I think there are $(n-1)+(n-2)+...+(n-n+1)+(n-n)$ relations.

4. About linear relations, I think it's $n^n$.

Is it correct ?

Thanks.

Answer 1

1. Symmetric relations: you have to decide if the members of the couple $(x,y)$ are in relation. There are $\binom{n}{2} + n$ such couples, up to order. So there are $2^{\binom{n}{2} + n}$ symmetric relations.

2. Antisymmetric relations: You can decide if $x$ is in relation with itself for any $x$ ; that gives $2^n$ choices. Then for any couple $(x,y)$ with $x \neq y$, you have to decide if $x \mathcal{R} y$ or $y \mathcal{R} x$ or there is no relation between $x$ and $y$. This gives $3$ possibilites the $\binom{n}{2}$ such couples. The total of antisymmetric relations is thus $2^n \times 3^{\binom{n}{2}}$.

3. Asymmetric relations: This time, $x$ cannot be in relation with itself. Then, you have the same choices as above ; so there are $3^{\binom{n}{2}}$ asymmetric relations

4. Linear relations: you just have to decide which of your elements is the smallest, then to decide the smallest among the remaining elements... You get $n!$ such relations

Hope I'm not mistaken.