8
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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/… $\endgroup$
    – Gerry Myerson
    Oct 7, 2021 at 8:32
  • 3
    $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Oct 9, 2021 at 11:31
  • $\begingroup$ 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. $\endgroup$
    – Sarvesh Ravichandran Iyer
    Oct 9, 2021 at 16:44

1 Answer 1

Reset to default
6
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.