The number of Orders with Fourteen Elements

Abstract. The number of non-isomorphic posets on 14 elements is P_14 = 1’338’193’459’771. This extends our previous result P_13 = 33’823’827’452 which constituted the greatest known value. A table enumerates the posets according to their number of relations.

Mathematics Subjects Classifications (1991). Primary 06-04; secondary 06A07, 05C30.

Key words. Unlabeled, partial orders, computer, enumeration.

Introduction

Here we consider only pariwise non-isomorphic posets and note P_n (resp. P_n,r) the number of those having n elements (and r relations).

0 <= n <= 6, P_n = 1; 1; 2; 5; 16; 63; 318

P_7 =	2’045	(1972)	J. Wright
P_8 =	16’999	(1977)	S. K. Das
P_9 =	183’231	(1984)	R. H. Mohring
P_10 =	2’567’284	(1990)	J. C. Culberson, G. J. E. Rawlins
P_11 =	46’749’427	(1990)	J. C. Culberson, G. J. E. Rawlins
P_12 =	1’104’891’746	(1991)	C. Chaunier, N. Lygeros
P_13 =	33’823’827’452	(1992)	C. Chaunier, N. Lygeros
P_14 =	1’338’193’159’771	(2000)	N. Lygeros, P. Zimmermann

Results

The last value extends [1], follows [6], [7] – origins of this work – and [2], [3] – where our initial algorithm is describred. The following table gives the precise results.

r	P_n,r	r	P_n,r	r	P_n,r
0	1	30	15’093’556’839	60	3’461’298’437
1	1	31	20’075’844’431	61	2’493’875’402
2	3	32	25’908’418’088	62	1’770’675’277
3	7	33	32’478’923’331	63	1’239’039’207
4	19	34	39’592’931’224	64	854’569’812
5	47	35	46’979’502’004	65	560’970’065
6	133	36	54’307’727’007	66	389’321’463
7	355	37	61’211’924’728	67	257’162’269
8	1’020	38	67’323’642’504	68	167’425’100
9	2’921	39	72’305’442’194	69	107’425’128
10	8’632	40	75’882’802’702	70	67’918’114
11	25’486	41	77’869’195’951	71	42’302’121
12	75’366	42	78’181’684’187	72	25’947’267
13	217’990	43	76’844’939’859	73	15’667’333
14	613’701	44	73’984’081’629	74	9’307’819
15	1’659’796	45	69’807’866’652	75	5’436’986
16	4’290’662	46	64’585’100’397	76	3’120’222
17	10’541’968	47	58’617’924’003	77	1’757’459
18	24’574’810	48	52’215’061’893	78	970’342
19	54’282’974	49	45’668’403’312	79	524’242
20	113’695’015	50	39’234’427’091	80	276’596
21	226’043’606	51	33’122’134’980	81	142’020
22	427’434’085	52	27’486’947’185	82	70’684
23	770’364’708	53	22’430’638’497	83	33’907
24	1’326’574’992	54	18’005’406’984	84	15’527
25	2’187’816’296	55	14’221’396’017	85	6’724
26	3’463’953’205	56	11’055’548’408	86	2’701
27	5’276’878’418	57	8’461’181’255	87	978
28	7’750’426’625	58	6’376’703’312	88	309
29	10’995’675’430	59	4’733’381’232	89	78
				90	13
				91	1

More information can be found on the Web at:
https://lygeros.org/poset/

These results confirm R. Fraïssé’s conjecture on unimodality. The values for 0 <= r <= 6 agree with J. C. Culberson and G. J. E. Rawlin's [4], and the values for 78 <= r <= 91 are confirmed by M. Erné's formulae.

Acknowledgement

This result would not have been possible without the help of Robert Erra, Bernard Landreau, John Lygeros, Jon Kierkegaard, Ilias Kotsireas, Joël Marchand, Michel Mizony, Thomas Papanikolaou, and Robert Piche.

References

1. C. Chaunier and N. Lygeros (1992) The number of orders with thirteen elements. Order, vol. 9, 203-204.
2. C. Chaunier and N. Lygeros (1992) Progrès dans l’énumération des poset, C. R. Acad. Sci. Paris, t. 314, série I, 691-694.
3. C. Chaunier and N. Lygeros (1994) Le nombre de posets à isomorphie près ayant 12 éléments. Theoretical Computer Science, n. 123, 89-94.
4. J. C. Culberson and G. J. E. Rawlins (1991) New results from an algorithm for counting posets, Order, vol. 7, 361-374.
5. M. Erné (1992) The number of partially ordered sets with more points than unrelated pairs, Discrete Math. 105, n. 1-3, 49-60.
6. R. Fraïssé and N. Lygeros (1991) Petits posets : dénombrement, représentabilité par cercles et compenseurs. C. R. Acad. Sci. Paris, t. 313, série I, 417-420.
7. N. Lygeros (1991) Calculs exhaustifs sur les posets d’au plus 7 éléments, Singularité, vol. 2, n. 4, 10-24.

173 - The number of Orders with Fourteen Elements

N. Lygeros

SECTIONS