Recurrence on partial orders

329 Views Asked by At

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?

1

There are 1 best solutions below

0
On

No recurrence is known that would allow you to take just the numbers $P_1,\ldots,P_{18}$ and calculate $P_{19}$.

There are recursive techniques for counting partial orders (see Brinkmann & McKay 2002), but they work by actually listing possible partial orders of a certain size, then trying out the possibilities where another element can be placed.

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.

P.S. It may be useful to note that MSE has several questions about the number of partial orders. Searching MSE for A001035 gives 7 results at the moment.