A222865 Weakly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

1, 1, 3, 19, 195, 2551, 41343, 826939, 20616795, 658486351, 28264985223, 1725711709459, 155998194920835, 21019550046219271, 4162663551546902223, 1192847436856343300779, 489879387071459457083115, 286844271719979335180726911, 238844671940165660117456403543

Offset

0,3

Comments

Here "weakly graded" means that there is a rank function rk from the vertices to the integers such that whenever x covers y we have rk(x) = rk(y) + 1. Alternate terminology includes "graded" and "ranked." A poset is said to be (3+1)-free if it does not contain four vertices a, b, c, d such that a < b < c and d is incomparable to the other three.

Links

Table of n, a(n) for n=0..18.

J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, To appear, J. Combinatorial Theory, Series A.

Formula

G.f. is W(e^x, Psi(x)) where W(x, y) = (1 - x)y/x + (2x^3 + (x^3 - 2x^2)y)/(2x^2 + x + (x^2 - 2x - 1)y) and Psi(x) is the GF for A047863.

Mathematica

m = maxExponent = 19;
Psi[x_] = Sum[E^(2^n x) x^n/n!, {n, 0, m}] + O[x]^m;
W[x_, y_] = (1-x)y/x + (2x^3 + (x^3 - 2x^2)y)/(2x^2 + x + (x^2-2x-1) y);
CoefficientList[W[E^x, Psi[x]] + O[x]^m, x] Range[0, m-1]! (* Jean-François Alcover, Dec 11 2018 *)

Crossrefs

For weakly graded (3+1)-free posets by height, see A222866. For strongly graded (3+1)-free posets, see A222863. For all weakly graded posets, see A001833. For all (3+1)-free posets, see A079145.

Sequence in context: A001517 A080893 A028854 * A108292 A053554 A048172

Adjacent sequences: A222862 A222863 A222864 * A222866 A222867 A222868

Keyword

nonn

Author

Joel B. Lewis, Mar 07 2013

Status

approved