login
Smallest positive integer that cannot be obtained as the number of linear extensions of a poset of size n.
1

%I #14 Jan 25 2024 11:44:11

%S 2,2,3,4,7,13,17,59,253,979

%N Smallest positive integer that cannot be obtained as the number of linear extensions of a poset of size n.

%C a(n) is the smallest positive integer such that A160371(a(n)) > n.

%H Swee Hong Chan and Igor Pak, <a href="https://arxiv.org/abs/2308.10214">Computational complexity of counting coincidences</a>, arXiv:2308.10214 [math.CO], 2023. See p. 12.

%H Swee Hong Chan and Igor Pak, <a href="https://arxiv.org/abs/2401.09723">Linear extensions and continued fractions</a>, arXiv:2401.09723 [math.CO], 2024.

%e a(8) = 253, so the number 253 cannot be obtained as the number of linear extensions of a poset of size 8, but every integer from 1 to 252 can.

%Y Cf. A160371.

%K nonn,hard,more

%O 0,1

%A _François Labelle_, Jan 28 2017