A160371 The minimum size of a poset having n linear extensions.
0, 2, 3, 4, 4, 3, 5, 4, 5, 5, 5, 4, 6, 5, 5, 5, 7, 5, 6, 5, 6, 6, 6, 4, 5, 6, 6, 6, 7, 5, 7, 6, 6, 7, 6, 6, 6, 6, 7, 5, 7, 6, 7, 6, 6, 7, 7, 6, 7, 7, 7, 6, 7, 6, 7, 7, 6, 7, 8, 5, 6, 7, 7, 6, 7, 6, 7, 7, 7, 6, 7, 6, 7, 7, 6, 6, 7, 7, 7, 6, 7, 7, 8, 6, 8, 7, 7, 7, 8, 6, 7, 7, 7, 7, 7, 6, 8, 7, 7, 7, 7, 7
Offset: 1
Keywords
Examples
a(5) = 4 because the poset with two minimal elements, two maximal elements, and three covering relations between them ["N" shaped] has exactly 5 linear extensions and 4 elements. No smaller poset has 5 linear extensions.
Links
- François Labelle, Table of n, a(n) for n = 1..1000
- Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, arXiv:2308.10214 [math.CO], 2023. See p. 12.
- Swee Hong Chan and Igor Pak, Linear extensions and continued fractions, arXiv:2401.09723 [math.CO], 2024.
- Bridget E. Tenner, Optimizing linear extensions, arXiv:0905.1688 [math.CO], 2009; SIAM J. Discr. Math. 23 (2009) 1450-1454.
Formula
a(n) <= 2*sqrt(n).
Extensions
a(13)-a(102) from François Labelle, Jan 28 2017