The number of partial orders of finite set.

Question

My question is about the number of partial orders of finite set. For example, if $S=\{a, b\}$, then there are 4 partial orders $\{ (a, a), (b, b) \}$, $\{ (a, a), (a, b), (b, b) \}$, $\{ (a, a), (b, a), (b, b) \}$, $\{ (a, a), (a, b), (b, a), (b, b) \}$. Then, how many are there partial orders if $|S|=n$?

I tried to count for the case $|S|=3$, $\{ (a, a), (b, b), (c, c) \}$, $\{ (a, a), (b, b), (c, c), (a, b) \}$, $\{ (a, a), (b, b), (c, c), (a, b), (b, c), (a, c) \}$, and so on. But it is too inefficient and does not give any insight.

If this is a difficult question, then I want to just know the case of $|S|=3$.

Answer 1

In the usual terminology, a partial order is required be antisymmetric: if $x\le y$ and $y\le x$, then $x=y$. Thus there are only three partial orders on a two-element set; your fourth example in not antisymmetric.

Apparently, you want to count the more general quasi-orders aka preorders, i.e., reflexive transitive relations. (On a finite set, there is a one-to-one correspondence between quasi-orders and topologies.)

The number of quasi-orders (or equivalently, the number of topologies) on an $n$-element set is sequence A000798 at the OEIS. There are $29$ quasi-orders on a $3$-element set.

Answer 2

Each finite pos (partially ordered set) has to have at least one minimal element.

Consider 3-set $\ X:=\{a\ b\ c\}.\ $ First, let $a$ be the unique minimal element. There are exactly three different partial orders in $\{b\ c\}.\ $ The same when $\ b\ $ or $\ c\ $ is the only minimal element in $\ X.\ $ Each of those partial orders in a 2-element set extends uniquely over the third element that is minimal. Every two of these partial orders in $\ X\ $ are different. Thus, there are exactly $9=3\cdot 3\ $ partial orders in $\ X\ $ that have exactly one minimal element.

Now, let $\ a\ $ and $\ b\ $ be the only minimal elements in $\ X\ $ (so that $\ c\ $ is not minimal). We have exactly three partial orders like this in $\ X.\ $ If the lonely non-minimal element is $\ b\ $ or $\ a\ $, each time we get 3 different partial orders, and all of such $\ 3\cdot 3=9\ $ partial orders are different. Thus, so far, we have 9+9=18 different partial orders.

Finally, there is exactly one partial order such that all elements of $\ X\ $ are minimal. This gives us finally the answer 1+18=19.

THEOREM There are exactly $\ 19\ $ different partial orders in any fixed 3-set.