THE AVERAGE NUMBER OF LINEAR EXTENSIONS OF A PARTIAL ORDER

Authors
BRIGHTWELL G PROMEL HJ STEGER A
Citation
G. Brightwell et al., THE AVERAGE NUMBER OF LINEAR EXTENSIONS OF A PARTIAL ORDER, J COMB TH A, 73(2), 1996, pp. 193-206
Citations number
8
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES A
ISSN journal
00973165 → ACNP
Volume
73
Issue
2
Year of publication
1996
Pages
193 - 206
Database
ISI
SICI code
0097-3165(1996)73:2<193:TANOLE>2.0.ZU;2-6
Abstract
Kleitman and Rothschild (Trans. Amer. Math. Sec. 205 (1975), 205-220) gave an asymptotic formula for the number of partial orders with groun d-set [n]. We give a shorter proof of their result and extend it to co unt the number of pairs (P, <), where P is a partial order on [n] and < is a linear extension of P. This gives us an asymptotic Formula for (a) the average number of linear extensions of an n-element partial or der and (b) the number of suborders of an n-element linear order. (C) 1996 Academic Press, Inc.