reflexive and antisymetric relation

Question

Let $A = \{1,2,3,4,\ldots ,n\}$

A). How many relations on $A$ are both reflexive and antisymmetric and contain the ordered pair $(1,2)$ ?

Ans. for this I believe it is either $3^{(n^2-n-1)/2}$ or $3^{(n^2-n-2)/2}$

Is the first one correct ?

B). If $R$ is a total order on A what is $|R|$?

Could use a hint on how to go about this one.

Answer 1

Corrected version. (The original version mistakenly counted reflexive, symmetric relations.)

There are $n^2$ possible ordered pairs. When building a reflexive, antisymmetric relation you must choose the $n$ of them of the form $\langle k,k\rangle$. The remaining $n^2-n=n(n-1)$ ordered pairs come in $\binom{n}2=\frac{n(n-1)}2$ pairs of the form $\{\langle k,\ell\rangle,\langle \ell,k\rangle\}$, where $k\ne\ell$. Antisymmetry prohibits you from taking both members of any of these pairs, but you may take either member alone, and you may take neither. Thus, you have $\binom{n}2$ three-way choices to make. Finally, you’re required to choose $\langle 1,2\rangle$ and hence also $\langle 2,1\rangle$, so in the end you must make $\binom{n}2-1$: for each pair $\{k,\ell\}$ with $k\ne\ell$ except the pair $\{1,2\}$, you must choose whether the relation includes $\langle k,\ell\rangle$ but not $\langle\ell,k\rangle$, $\langle\ell,k\rangle$ but not $\langle k,\ell\rangle$, or neither of these ordered pairs. That’s $\binom{n}2-1$ three-way choices, so they can be made in a total of

$$3^{\binom{n}2-1}=3^{\frac12(n^2-n)-1}=3^{\frac12(n^2-n-2)}$$

ways, and your second expression is correct.

For (B), note that every total order on $A$ is going to ‘look like’ some permutation of the usual order. It will have a first element, which will be in the relation $R$ to every element of $A$ (or to every other element of $A$ if your definition of total order makes it irreflexive); this is exactly the position that $1$ occupies in the usual order on $A$. It will have a second element, which will be related by $R$ to the other elements of $A$ exactly as $2$ is related by $\le$ to the other elements of $A$. And so on. So $|R|$ will be exactly the same as the cardinality of the usual order $\le$, which isn’t too hard to calculate.

Answer 2

HINT for the first problem:

Since $R$ has to be reflexive, it must contain the pair $(k,k)$ for $1\leq k \leq n$. Now how many pairs of (unordered) numbers can you choose from $n$ numbers. Clearly, it is $n(n-1)/2$. For each of these pairs except $(1,2)$, you have two choices, whether to put it in the relation or not. Now calculate.