Number of linear extensions of inclusion order

61 Views Asked by At

enter image description here

I think there are 7 orderings that can be added to this Hasse diagram: $\varnothing \subset \{x,y\}, \varnothing \subset \{x,z\}, \varnothing \subset \{y,z\}, \varnothing \subset \{x,y,z\}, \{x\} \subset \{x,y,z\}, \{y\} \subset \{x,y,z\}, \{z\} \subset \{x,y,z\} $.
And there are $2^7-1$ ways to select at least one of those orderings, and add it to original Hasse diagram. So number of linear extensions of this inclusion order is $2^7-1$. Am I right?

1

There are 1 best solutions below

0
On BEST ANSWER

Not much is known in general about the number linear extensions of the inclusion order on $\wp([n]$, where as usual $[n]=\{1,2,\ldots,n\}$. For $n=3$ the number is actually $46$, for $n=4$ it is already $1\,680\,384$, according to OEIS A046873, and it grows very rapidly after that. This paper [PDF] derives upper and lower bounds on the number