The number of Orders with Fourteen Elements

N. Lygeros




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.

rP_n,rrP_n,rrP_n,r
013015'093'556'839603'461'298'437
113120'075'844'431612'493'875'402
233225'908'418'088621'770'675'277
373332'478'923'331631'239'039'207
4193439'592'931'22464854'569'812
5473546'979'502'00465560'970'065
61333654'307'727'00766389'321'463
73553761'211'924'72867257'162'269
81'0203867'323'642'50468167'425'100
92'9213972'305'442'19469107'425'128
108'6324075'882'802'7027067'918'114
1125'4864177'869'195'9517142'302'121
1275'3664278'181'684'1877225'947'267
13217'9904376'844'939'8597315'667'333
14613'7014473'984'081'629749'307'819
151'659'7964569'807'866'652755'436'986
164'290'6624664'585'100'397763'120'222
1710'541'9684758'617'924'003771'757'459
1824'574'8104852'215'061'89378970'342
1954'282'9744945'668'403'31279524'242
20113'695'0155039'234'427'09180276'596
21226'043'6065133'122'134'98081142'020
22427'434'0855227'486'947'1858270'684
23770'364'7085322'430'638'4978333'907
241'326'574'9925418'005'406'9848415'527
252'187'816'2965514'221'396'017856'724
263'463'953'2055611'055'548'408862'701
275'276'878'418578'461'181'25587978
287'750'426'625586'376'703'31288309
2910'995'675'430594'733'381'2328978
9013
911

More information can be found on the Web at:
http://www.lygeros.org/Math/poset.html

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.







free counters


Opus