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,2

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).

Example

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.

Crossrefs

Cf. A263860.

Cf. A281723 for the smallest index n = A281723(m) such that a(n) > m.

Sequence in context: A129456 A030412 A329526 * A059686 A101083 A097935

Adjacent sequences: A160368 A160369 A160370 * A160372 A160373 A160374

Keyword

nonn

Author

Bridget Tenner, May 11 2009

Extensions

a(13)-a(102) from François Labelle, Jan 28 2017

Status

approved