A222864 -id:A222864 - cp's OEIS frontend

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

1, 1, 3, 13, 111, 1381, 22383, 461413, 12163791, 420626821, 19880808303, 1337330559973, 130909732781391, 18649561895661061, 3830195104867879023, 1124247654215697637093, 469367653568553278229711, 278046313987470874905216901, 233462156432002170491075384943

Offset: 0

Joel B. Lewis, Mar 07 2013

nonn

Here "strongly graded" means that every maximal chain has the same length. Alternate terminology includes "graded" (e.g., in Stanley 2012) 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.

R. P. Stanley, Enumerative Combinatorics, Volume 1. Cambridge University Press. 2nd edition, 2012. http://math.mit.edu/~rstan/ec/ec1/

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.

For strongly graded (3+1)-free posets by height, see A222864. For weakly graded (3+1)-free posets, see A222865. For all strongly graded posets, see A006860. For all (3+1)-free posets, see A079145.

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

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

A361956 Triangle read by rows: T(n,k) is the number of labeled tiered posets with n elements and height k.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 6, 6, 0, 1, 50, 36, 24, 0, 1, 510, 510, 240, 120, 0, 1, 7682, 10620, 4800, 1800, 720, 0, 1, 161406, 312606, 136920, 47040, 15120, 5040, 0, 1, 4747010, 13439076, 5630184, 1678320, 493920, 141120, 40320, 0, 1, 194342910, 821218110, 319384800, 83963880, 21137760, 5594400, 1451520, 362880

Offset: 0

Andrew Howroyd, Apr 02 2023

A tiered poset is a partially ordered set in which every maximal chain has the same length.

			Triangle begins:
  1;
  0, 1;
  0, 1,      2;
  0, 1,      6,      6;
  0, 1,     50,     36,     24;
  0, 1,    510,    510,    240,   120;
  0, 1,   7682,  10620,   4800,  1800,   720;
  0, 1, 161406, 312606, 136920, 47040, 15120, 5040;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50).

Row sums are A223911.
Column k=2 is A052332.
Main diagonal is A000142.
The unlabeled version is A361957.
Cf. A222864, A361951.

S(M)={my(N=matrix(#M-1, #M-1, i, j, sum(k=1, i-j+1, (2^j-1)^k*M[i-j+1, k])/j!)); for(i=1, #N, for(j=1, i, N[i,j] -= sum(k=1, j-1, N[i-k, j-k]/k!))); N}
C(n)={my(M=matrix(n+1,n+1), R=M); M[1,1]=R[1,1]=1; for(h=1, n, M=S(M); for(i=h, n, R[i+1,h+1] = i!*vecsum(M[i-h+1,]))); R}
{ my(A=C(7)); for(i=1, #A, print(A[i, 1..i])) }

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula