# How many totally ordered sets can be constructed from a given finite poset?

For a finite poset $S=\{x_1,\cdots,x_n\}$, there are $k$ ordering relations $x_{k_0}>x_{k_1}$ ($k_0\neq k_1$) that generate all the ordering of the poset $S$. Now we want to make $(S,\geq)$ a totally ordered set that respect the $k$ ordering relations by adding new relations compatible with the $k$ existing ones. How many ways to do that exist?

Edited: What if we know all the orderings of the poset (as opposed to just the generators)? Also a formula is more appropriate than an algorithm here.

Example: $S={a,b,c,d}$. There are 2 relations $a>b$, $b>d$ that generate all relations of the poset. In order to make $S$ a totally ordered set there are 4 ways which is determined by where to put $c$ in this example.

Another idea to think about this is...how many ways we have to order $n$ elements when some elements must be before others while any pair of adjacent elements unrestricted by ordering relations commute. Then how many ways can we order the $n$ elements?

• I think, if in your example you were instead given the relations $a>b$ and $a>d$, there would be 8 ways. So its impossible to say from $n$ and $k$ alone. – Achilles Aug 6 '15 at 21:40
• I know...perhaps I should add a stronger condition, namely all the orderings that have to be respected is known.. – Ying Zhou Aug 6 '15 at 21:44

Your second question, counting the number of linear (total) ordering extensions of a given partially ordered set, is #P-hard, meaning that probably no fast (polynomial time) algorithm exists to do it, in terms of the input size (which is $O(\log^2 n)$ if you have $n$ elements to order). However there are some heuristic approaches available online in software form to do this, you can look up "enumerating linear extensions of posets." Your first question is ill-posed as pointed out by a comment, because the number of elements and the number of ordering relations does not determine the number of total linear ordering extensions, even if you assume your initial set of ordering relations is in minimal presentation, i.e. no relations are redundant.