# Recurrence on partial orders

Let $$P_n$$ denote the number of partial orders on $$n$$ elements.

A partial order is a relation that is reflexive, anti-symmetric and transitive.

$$P_n$$ is known for $$n; 0\leq n\leq 18$$. See On-line Encyclopedia of Integer Sequences. I have seen other combinatorial sequences which can be computed recursively from previous terms. For example this somewhat related sequence. Is there a way to do this with the number of partial orders?

Can I get $$P_{19}$$ from the available values of $$P_n$$? How?

• I note that there is a meta thread concerning this question, in particular, whether or not it should be deleted: math.meta.stackexchange.com/questions/34175/… Oct 7, 2021 at 8:32
• I think that adding the link to OEIS is very relevant here. It unambiguously implies that this is a difficult open problem. True, this is anything but the most lucid of questions, but the OP seems to be gone. Oct 9, 2021 at 11:31
• Note : Had voted to delete this question prior to the undeletion and edit : agree with both nature of context rewrite as well as reopening as it stands. The question is now open. Oct 9, 2021 at 16:44

No recurrence is known that would allow you to take just the numbers $$P_1,\ldots,P_{18}$$ and calculate $$P_{19}$$.
This does not lead to a simple recurrence on $$P_n$$ because different $$n$$-element partial orders will in general have different numbers of such extensions into $$(n+1)$$-element partial orders. You can observe this already going from $$P_2=3$$ to $$P_3=19$$. One of the 2-element orders extends to seven 3-element orders, but two of them extend to six each, for a total of $$7+6+6=19$$. In a nutshell, you end up applying the rule of sum instead of the rule of product. (There are some nontrivial things for making it faster; see the B&M paper.)
So how to calculate $$P_{19}$$? Either spend perhaps $$100\,000$$ cpu years with the best algorithm currently known, or invent a better one.