A293499 Number of unlabeled hereditary semiorders on n points.

1, 2, 5, 14, 42, 132, 428, 1415, 4730, 15901, 53593, 180809, 610157, 2058962, 6947145, 23437854, 79067006, 266717300, 899693960, 3034814143, 10236853534, 34530252629, 116475001757, 392885252033

Offset: 1

Author

Mitchel T. Keller, Oct 10 2017

Keywords

• nonn

Comments

A semiorder (poset avoiding the subposets 2+2 and 1+3, or an interval order having a representation in which all intervals have the same length) is hereditary if every initial subsequence of the ascent sequence associated to the semiorder by the bijection of Bousquet-Mélou et al. corresponds to a semiorder.

References

• M. T. Keller and S. J. Young, Hereditary semiorders and enumeration of semiorders by dimension. Preprint (2017).

Links

• M. Bousquet-Mélou, A. Claesson, M. Dukes, and S. Kitaev, (2+2)-free posets, ascent sequences and pattern avoiding permutations, J. Combin. Theory Ser. A 117, 7 (2010), 884-909.
• Mitchel T. Keller, Stephen J. Young, Hereditary Semiorders and Enumeration of Semiorders by Dimension, arXiv:1801.00501 [math.CO], (2018)
• Index entries for linear recurrences with constant coefficients, signature (8,-23,29,-14,1).

Crossrefs

Cf. A022493.

Programs

Mathematica

CoefficientList[ Series[(-1 +6x -12x^2 +9x^3 -x^4)/(-1 +8x -23x^2 +29x^3 -14x^4 +x^5), {x, 0, 26}], x] (* or *)
LinearRecurrence[{8, -23, 29, -14, 1}, {1, 2, 5, 14, 42}, 27] (* Robert G. Wilson v, Jan 07 2018 *)

Formula

G.f.: -x*(1 - 6*x + 12*x^2 - 9*x^3 + x^4) / ( (x-1)*(x^4 - 13*x^3 + 16*x^2 - 7*x + 1) ).