A222864 Triangle T(n,k) of strongly graded (3+1)-free partially ordered sets (posets) on n labeled vertices with height k.

1, 1, 2, 1, 6, 6, 1, 50, 36, 24, 1, 510, 510, 240, 120, 1, 7682, 7380, 4800, 1800, 720, 1, 161406, 141246, 91560, 47040, 15120, 5040, 1, 4747010, 3444756, 2162664, 1134000, 493920, 141120, 40320, 1, 194342910, 110729310, 61286400, 32253480, 14605920, 5594400

Offset

1,3

Comments

Here "strongly graded" means that every maximal chain has the same length. Alternate terminology includes "graded" (e.g., in Stanley 2011) and "tiered" (as in A006860). A poset is said to be (3+1)-free if it does not contain four elements a, b, c, d such that a < b < c and d is incomparable to the other three.

Links

Joel B. Lewis, Rows n = 1..20 of triangle, flattened

J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, J. Combin. Theory Ser. A 120 (2013), no. 6, 1305-1327.

Formula

G.f. is given in the Lewis-Zhang paper.

Example

For n = 3, there is 1 strongly graded poset of height 1 (the antichain), 6 strongly graded posets of height 2, and 6 strongly graded posets of height 3 (the chains), and all of these are (3+1)-free. Thus, the third row of the triangle is 1, 6, 6.

Crossrefs

For row-sums (strongly graded (3+1)-free posets with n labeled vertices, disregarding height), see A222863. For weakly graded (3+1)-free posets, see A222865. For all strongly graded posets, see A006860. For all (3+1)-free posets, see A079145.

Sequence in context: A090582 A079641 A364506 * A232433 A271881 A182729

Adjacent sequences: A222861 A222862 A222863 * A222865 A222866 A222867

Keyword

nonn,tabl

Author

Joel B. Lewis, Mar 07 2013

Status

approved