Cardinality of set of strict linear orders on a finite set

Question

Let $A$ be a finite set, and let $\mathcal{P}$ be the set of all strict linear orders on $A$ (by strict linear order I mean a binary relation on $A$ that is asymmetric, total, transitive (and hence irreflexive)). What is the cardinality of $\mathcal{P}$

I was trying to approach the question as follows: Suppose $A$ has cardinality $n$. There are $n\cdot n= n^2$ possible ordered pairs. However, we need to get rid of any pairs of the form $(a,a)$, so we subtract $n$. Hence there are $n^2-n$ order pairs. But once we know $(a,b)$, we know $(b,a)$ is not in the relation from asymmetry, so we must divide by 2. Hence, there are $\frac{n^2-n}{2}$ pairs that need to be determined.

I thought I could then just answer the question "how many $\frac{n^2-n}{2}$ digit numbers are there where each digit is either $0$ or $1$ (zero and one correspond to either related or not related).

However, I realized that this does not account for transitivity, and I do not know how to take transitivity into account.

(One way in which transitivity is troubling me is that, if $(a,b)$ is in the relation, then whether I need to consider if $a$ and $c$ are related depends on whether $b$ and $c$ are related)

Answer 1

Each permutation represents the sort of linear order you are seeking.

Answer 2

Here's a direct way to prove that the number is $n!$.

For the empty set ($n=0$) there obviously only exists one order, as there are no elements to order. Now $0!=1$, therefore the assumption is true for the empty set.

Now assume we've already proved that for $n$ elements, there are $n!$ strict linear orders. Now how many orders can we find for a set of $n+1$ elements?

Select $n$ of the elements. Clearly every order of on the $n+1$ elements will induce also an order on those $n$ elements; moreover, if the induced order was different, then the original order must have been different, too. Now by assumption, there are $n!$ ways to order them.

Now we put back element $n+1$. No matter how the $n$ other elements are ordered, there are always $n+1$ positions where you can insert the additional element: Before the first element, or after the $4n$-th element for any $n$. Each of those of course leads to a different order, and it is obvious that all orders are covered that way.

Therefore the set of $n+1$ elements has exactly $n!(n+1)=(n+1)!$ different strict linear order.

Thus by induction a set of $n$ elements always has $n!$ strict linear orders.