The number of labeled partial orders and topologies on 19 points
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
Abstract
We report the exact value of the number of labeled partially ordered sets (equivalently, labeled $T_0$ topologies) on 19 points, P(19) = 646099441937791106493755218560442089979, a 39-digit integer extending OEIS A001035, whose largest previously computed term was P(18) (Brinkmann and McKay).
By the Stirling transform we also obtain the number of labeled topologies on 19 points, A000798(19) = 689054943207246404281592791142107048261.
Our route is the Erné-Stege moment reduction, which expresses P(19) through a few sums of antichain counts over the posets on at most 16 points.
All of these are available from the posets on at most 15 points (whose number is catalogued, and which standard software generates on demand), except a single moment over the 16-point posets.
That moment is obtained not by enumerating the 16-point posets but by inserting a single element into the 15-point ones, with a per-parent kernel that advances the sum at the cost of computing the parent's own antichain count.
The result passes several independent checks, among them the residue predicted by the modular periodicity of A001035 and the recovery from the same sweep of the known count P(16) and the Erné-Stege moments G(16,1) and G(16,2).
We also report the moments G(16,3) and G(16,4), the latter an input to the analogous computation for 20 points.