Number of linear extensions of a finite partially ordered set

Question

Let $N$ be a finite set and $\le$ be a partial order. Can you express the number of linear extensions $L(\le,N)$ of this partial order in terms of $b(k) := \#\{l \in N\ :\ k \le l\}$? My intuition says $$L(\le,N) = \frac{n!}{\prod_{k \in N} \max(b(k)-1,1)}$$ where $n = |N|$, but I'm not quite sure.

Answer 1

Your formula gives the wrong result when $\langle N,\le\rangle$ is a linear order: you get $\frac{n!}{(n-1)!}=n$ instead of $1$. That could be corrected by removing the $-1$ in the denominator to make it simply $$L(\le,N) = \frac{n!}{\prod_{k \in N}b(k)}\;,$$ but this also fails. Let $\langle N,\le\rangle=\langle\wp(\{0,1,2\}),\subseteq\rangle$. Then $b(k)=2^{3-|k|}$ for each $k\in N$, so $$\prod_{k\in N}b(k)=\prod_{S\subseteq\{0,1,2\}}2^{3-|S|}=\prod_{k=0}^32^{k\binom3k}=2^{\sum_{k=0}^3k\binom3k}=2^{12}\;,$$ but $8!=2^7\cdot3^2\cdot5\cdot7$ and therefore isn’t divisible by $2^{12}$.

In fact the problem of counting the linear extensions of a partial order is $\#P$-complete.

Added: I worked too hard: the same problem already arises with $\langle\wp(\{0,1\}),\subseteq\rangle$, for which the formula gives $\frac{4!}{4\cdot2\cdot2\cdot1}=\frac32$. This is at least in the right ballpark, since the correct value is $2$. In my original example the figure given by the formula is $9.84375$, which is way off: I count $48$ linear extensions. And on further investigation I find that even the number of linear extensions of the subset order on an $n$-element set appears not to be known in general.