A006860 -id:A006860 - cp's OEIS frontend

A223911 Number of tiered orders on n nodes (corrected version of A006860).

1, 1, 3, 13, 111, 1381, 25623, 678133, 26169951, 1447456261, 114973232583, 13034314621813, 2103826463800911, 481932523110975301, 156356753093586913143, 71729530379673590609653, 46471511649877647638694591, 42487759521494442057018000901, 54781291469300608901184153800103

Offset: 0

Joerg Arndt, Mar 29 2013, using information provided by Joel B. Lewis, M. F. Hasler and Michel Marcus in A006860

nonn

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..100 (terms n = 1..22 from Joerg Arndt)
D. Klarner, The number of tiered posets modulo six, Discrete Math., 62 (1986), 295-297.

Row sums of A361956.

Cf. A218695, A361912 (unlabeled version).

f:= (i, j)-> add((-1)^(i-k)*binomial(i, k) *(2^k-1)^j, k=0..i):
b:= proc(n, i) option remember;
      `if`(n=0, 1, add(b(n-j, j)/j!*f(i, j), j=1..n))
    end:
a:= n-> n!*b(n, 1):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 23 2013

f[i_, j_] := Sum[(-1)^(i-k)*Binomial[i, k]*(2^k-1)^j, {k, 0, i}]; b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, j]/j!*f[i, j], {j, 1, n}]]; a[n_] := n!*b[n, 1]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Apr 08 2015, after Alois P. Heinz *)

f(m,n) = sum(k=0, m, (-1)^(m-k) * binomial(m,k) * (2^k-1)^n );
mn(n,V,m) = n! / prod(k=1, m, V[k]! ); /* multinomial of V[1..m] */
A223911(n)=
{
    my(m=n, C=vector(n,j,1), z, t, ret);
    while ( 1,  /* for all compositions C[1..m] of n */
        t = mn(n,C,m) * prod(j=1, m-1, f(C[j],C[j+1]) );
        ret += t;
        if ( m<=1, break() ); /* last composition? */
        /* create next composition: */
        C[m-1] += 1;
        z = C[m];
        C[m] = 1;
        m += z - 2;
    );
    return(ret);
}

\\ here f(m,n) is A218695.
f(m,n) = {sum(k=0, m, (-1)^(m-k) * binomial(m, k) * (2^k-1)^n )}
seq(n)={my(N=matrix(n,n,i,j, f(i,j)), T=vector(n), v=vector(n+1)); v[1]=1; for(r=1, n, T[r]=vector(r, k, (r==k) + binomial(r,k)*sum(i=1, r-k, T[r-k][i]*N[i,k])); v[1+r]=vecsum(T[r])); v} \\ Andrew Howroyd, Mar 29 2023

a(n) = sum(all composition C of n, M(C) * prod(j=1..m-1, f(C[j]*C[j+1]) ) ) where m is the number of parts of the current composition P, f(i,j) = sum(k=0..i, (-1)^(i-k) * binomial(i,k) * (2^k-1)^j ), and M(C) is the multinomial coefficient n!/prod(j=1..m, C[j]! ); see Pari code.
Klarner incorrectly gives prod(j=1..m-1, f(C[j]*C[m]) ) in the formula for a(n).
Conjecture: a(n) ~ c * 2^(n^2/4 + 3*n/2) / sqrt(n), where c = EllipticTheta[3, 0, 1/2^(1/4)] / (sqrt(Pi) * 2^(1/4)) = 2.020039... (based on the numerical analysis of 600 terms). - Vaclav Kotesovec, Apr 10 2015

Added a(0) = 1 by Alois P. Heinz, Jul 23 2013

A001833 Number of labeled graded partially ordered sets with n elements.

Original entry on oeis.org

1, 1, 3, 19, 219, 3991, 106623, 3964339, 199515459, 13399883551, 1197639892983, 143076298623259, 23053861370437659, 5062745845287855271, 1530139311543346178223, 641441466132460086890179, 375107113287994040621904819, 307244526491924695346004951151, 353511145615118063468292270299943

Offset: 0

N. J. A. Sloane

nonn

Here "graded" means that there exists a rank function rk from the poset to the integers such that whenever v covers w in the poset, we have rk(v) = rk(w) + 1. Note that this notion of grading is weaker than in sequence A006860, which counts posets in which all maximal chains have the same length.

			The poset on {a, b, c, d, e} defined by the relations a < b < c and d < e is counted by this sequence. (For example, one associated rank function is rk(a) = rk(d) = 0, rk(b) = rk(e) = 1 and rk(c) = 2.) However, the poset defined by the relations a < b < c and a < d < e < c is not graded and so not counted by this sequence.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..100
David A. Klarner, The number of graded partially ordered sets, Journal of Combinatorial Theory, vol.6, no.1, pp.12-19, (January-1969).
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
Index entries for sequences related to posets

Row sums of A361951.
Graded posets with no chain of length 3 are counted by A001831.
Cf. A223911, A228551, A361920 (unlabeled version).

\\ C(n) is defined in A361951.
seq(n)={my(c=C(n)); Vec(serlaplace(c[n+1]/c[n]))} \\ Andrew Howroyd, Mar 31 2023

Corrected and edited by Joel B. Lewis, Mar 28 2011
a(7)-a(15) from Daniele P. Morelli, Aug 25 2013
a(16)-a(18) from Sean A. Irvine, Sep 25 2015

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

Original entry on oeis.org

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.

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

Original entry on oeis.org

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

Joel B. Lewis, Mar 07 2013

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.

			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.

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.

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.

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

cp's OEIS Frontend

A223911 Number of tiered orders on n nodes (corrected version of A006860).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A001833 Number of labeled graded partially ordered sets with n elements.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula