A001833 -id:A001833 - cp's OEIS frontend

A001831 Number of labeled graded partially ordered sets with n elements of height at most 1.

1, 1, 3, 13, 87, 841, 11643, 227893, 6285807, 243593041, 13262556723, 1014466283293, 109128015915207, 16521353903210521, 3524056001906654763, 1059868947134489801413, 449831067019305308555487, 269568708630308018001547681, 228228540531327778410439620963

Offset: 0

N. J. A. Sloane

Labeled posets where for all a,b,c in the set, do not have a

Number of labeled digraphs with n vertices with no directed path of length 2. Number of n X n {0,1} matrices A such that A^2 = 0. - Michael Somos, Jul 28 2013

Number of relations on n labeled nodes that are simultaneously transitive and antitransitive. - Peter Kagey, Feb 14 2021

			1 + x + 3*x^2 + 13*x^3 + 87*x^4 + 841*x^5 + 11643*x^6 + 227893*x^7 + ...

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).

T. D. Noe, Table of n, a(n) for n = 0..50
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19.
A. Motzek and R. Möller, Exploiting Innocuousness in Bayesian Networks, Preprint, Australasian Joint Conference on Artificial Intelligence AI 2015: Advances in Artificial Intelligence, pp. 411-423.
Zvi Rosen and Yan X. Zhang, Convex Neural Codes in Dimension 1, arXiv:1702.06907 [math.CO], 2017. Mentions this sequence.
Index entries for sequences related to posets

Cf. A002031, A047863, A052332, A001833, A048194.
Row sums of A052296.
Cf. variants: A135753, A135754.

A001831 := proc(n)
    add(binomial(n,k)*(2^k-1)^(n-k),k=0..n) ;
end proc:
seq(A001831(n),n=0..10) ; # R. J. Mathar, Mar 08 2021

Join[{1}, Table[Sum[Binomial[n,k](2^k-1)^(n-k),{k,n}],{n,20}]] (* Harvey P. Dale, Jan 05 2012 *)

{a(n)=n!*polcoeff(sum(k=0,n,exp((2^k-1)*x)*x^k/k!),n)} \\ Paul D. Hanna, Nov 27 2007

{a(n)=polcoeff(sum(k=0, n, x^k/(1-(2^k-1)*x +x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Sep 15 2009

a(n) = Sum((-1)^k*C(n, k)*A047863(k), k=0..n).
a(n) = Sum_{k=0..n} binomial(n, k)*(2^k-1)^(n-k). - Vladeta Jovovic, Apr 04 2003
E.g.f.: Sum_{n>=0} exp((2^n-1)*x) * x^n/n!. - Paul D. Hanna, Nov 27 2007 [correction made by Paul D. Hanna, Mar 08 2021]
O.g.f.: Sum_{n>=0} x^n/(1 - (2^n - 1)*x)^(n+1) = Sum_{n>=0} a(n)*x^n. - Paul D. Hanna, Sep 15 2009
a(n) ~ c * 2^(n^2/4 + n + 1/2) / sqrt(Pi*n), where c = JacobiTheta3(0,1/2) = EllipticTheta[3, 0, 1/2] = 2.1289368272118771586694585485449... if n is even, and c = JacobiTheta2(0,1/2) = EllipticTheta[2, 0, 1/2] = 2.1289312505130275585916134025753... if n is odd. - Vaclav Kotesovec, Mar 10 2014

More terms, formula and comments from Christian G. Bower, Dec 15 1999
Last 4 terms corrected by Vladeta Jovovic, Apr 04 2003
Comments corrected by Joel B. Lewis, Mar 28 2011

A361912 The number of unlabeled graded posets with n elements.

Original entry on oeis.org

1, 1, 2, 4, 10, 28, 93, 354, 1621, 9110, 64801, 595976, 7204091, 115561423, 2473540433, 70853213144, 2720354016419, 140170631441858, 9702605436760235, 903309202327818566, 113234129823368903523, 19137461395401601912043, 4366007821745938984134203

Offset: 0

Martin Rubey, Mar 29 2023

nonn

A partially ordered set is graded if all maximal chains have the same length. This is called tiered by some authors.

Andrew Howroyd, Table of n, a(n) for n = 0..40

Row sums of A361957.

Cf. A000112, A223911 (labeled), A001833, A361920, A361959 (connected).

\\ See PARI link in A361957 for program code.
A361912seq(20) \\ Andrew Howroyd, Apr 03 2023

sum(1 for P in posets(n) if P.is_graded())

Terms a(8) and beyond from Andrew Howroyd, Mar 30 2023

A361920 Number of unlabeled ranked posets with n elements.

Original entry on oeis.org

1, 1, 2, 5, 16, 61, 280, 1501, 9394, 68647, 591570, 6108298, 77162708, 1219779207, 24648006828, 647865966973, 22437052221282, 1032905858402302, 63591727342096158, 5258562027225785955, 586001891321599337103, 88241281449605821921186, 17996565026907866304071630

Offset: 0

Martin Rubey, Mar 29 2023

nonn

A partially ordered set is ranked if there is a function from the poset elements to the integers such that the function value of a covering element is precisely one larger than the function value of the covered element. This is called graded by some authors.

			For n=5, A000112(n) - a(n) = 63 - 61 = 2 because we have 2 posets with 5 elements that are not ranked: a<b<c<d  a<e<d  and  a<c<e  a<d  b<d  b<e where < means "is covered by". - _Geoffrey Critzer_, Oct 29 2023

Andrew Howroyd, Table of n, a(n) for n = 0..40

Row sums of A361953.

Cf. A000112, A001833 (labeled), A223911, A361912, A361955.

\\ See PARI link in A361953 for program code.
A361920seq(20) \\ Andrew Howroyd, Apr 01 2023

sum(1 for P in posets(n) if P.is_ranked())

Terms a(8) and beyond from Andrew Howroyd, Mar 31 2023

A361951 Triangle read by rows: T(n,k) is the number of labeled weakly graded (ranked) posets with n elements and rank k.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 12, 6, 0, 1, 86, 108, 24, 0, 1, 840, 2190, 840, 120, 0, 1, 11642, 55620, 31800, 6840, 720, 0, 1, 227892, 1858206, 1428000, 384720, 60480, 5040, 0, 1, 6285806, 82938828, 80529624, 24509520, 4626720, 584640, 40320

Offset: 0

Andrew Howroyd, Mar 31 2023

Here weakly 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.

T(n,k) corresponds to a(k,n) = b(k,n) - b(k-1,n) in the Klarner reference. Figure 2 shows the posets of row n=4.

			Triangle begins:
  1;
  0, 1;
  0, 1,      2;
  0, 1,     12,       6;
  0, 1,     86,     108,      24;
  0, 1,    840,    2190,     840,    120;
  0, 1,  11642,   55620,   31800,   6840,   720;
  0, 1, 227892, 1858206, 1428000, 384720, 60480, 5040;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50).
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19.
Wikipedia, Graded poset.

Row sums are A001833.
Column k=2 is A055531.
Partial row sums include A000007, A000012, A001831, A001832.
Main diagonal is A000142.
The unlabeled version is A361953.
Cf. A342587, A361950.

\\ Here C(n) gives columns of A361950 as vector of e.g.f.'s.
S(M)={matrix(#M, #M, i, j, sum(k=0,  i-j, 2^((j-1)*k)*M[i-j+1,k+1])/(j-1)! )}
C(n,m=n)={my(M=matrix(n+1, n+1), c=vector(m+1), A=O(x*x^n)); M[1, 1]=1; c[1]=1+A; for(h=1, m, M=S(M); c[h+1]=sum(i=0, n, vecsum(M[i+1, ])*x^i, A)); c}
T(n)={my(c=C(n), b=vector(n+1, h, c[h]/c[max(h-1,1)])); Mat(vector(n+1, h, Col(serlaplace(b[h]-if(h>1, b[h-1])), -n-1)))}
{ my(A=T(7)); for(n=1, #A, print(A[n, 1..n])) }

E.g.f. of column k >=2: C(k,x)/C(k-1,x) - C(k-1,x)/C(k-2,x) where C(k,x) is the e.g.f. of column k of A361950.

A006860 Erroneous version of A223911: Tiered orders on n nodes.

Original entry on oeis.org

1, 3, 13, 111, 1381, 25623, 678133, 26269735, 1447451707, 114973020921, 13034306495563

Offset: 1

Simon Plouffe

dead

WARNING: The currently listed value of a(8) is inconsistent with the result from Kreweras and Klarner quoted below, as pointed out by Michel Marcus. - M. F. Hasler, Nov 03 2012
A corrected version of this sequence is A223911. - Joerg Arndt, Mar 29 2013
Graded posets, i.e., those in which every maximal chain has the same length. (The terminology "graded" is also used to refer to a weaker notion; see A001833.)
Kreweras observed and Klarner proved that a(n) is congruent to 1 (resp. 3) modulo 6 when n is odd (resp. even). - Michel Marcus, Nov 03 2012
Using the formulas in the paper from Klarner (cf. PARI code), I get 1, 3, 13, 85, 801, 10231, 168253, 3437673, 85162465, 2511412651, 86805640461, 3469622549053, ... - M. F. Hasler, Nov 07 2012
The values currently in the sequence through 25623 are certainly correct (I've enumerated these posets by brute force and other methods). (...) Klarner's eq.(2) contains a typo: instead of f(m_1, m_h) it should be f(m_1, m_2).  (The point here is that the Hasse diagram of each of these posets decomposes as a bunch of bipartite graphs layered on top of each other; there are f(m_1, m_2) ways to choose the bipartite graph between the first two ranks of vertices, then f(m_2, m_3) ways to choose the bipartite graph between the second and third ranks of vertices, etc.)  (...).  When I implement Klarner's eqs.(1) and (2) (corrected) I get the following sequence: 1, 3, 13, 111, 1381, 25623, 678133, 26169951, 1447456261, 114973232583, ... Now we get the right terms up as far as I personally have experience (...) and they agree with Kreweras (and the current OEIS sequence) until a(8), at which point there is disagreement. - Joel B. Lewis, Mar 06 2013; private communication to M. F. Hasler

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

D. Klarner, The number of tiered posets modulo six, Discrete Math., 62 (1986), 295-297.
G. Kreweras, Dénombrement des ordres étagés, Discrete Math., 53 (1985), 147-149.

ee(n)={my(f(m,n)=sum(k=0,m,(-1)^(m-k)*binomial(m,k)*(2^k-1)^n), C(n,m)=n!/prod(i=1,#m,m[i]!), t(h,n)=my(s=0); forvec(m=vector(h,i,[if(iM. F. Hasler, Nov 07 2012

Error in a(8) pointed out by Michel Marcus, Nov 03 2012

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

Original entry on oeis.org

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

Offset: 0

Joel B. Lewis, Mar 07 2013

nonn

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.

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

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.

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 *)

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.

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

Original entry on oeis.org

1, 1, 2, 1, 12, 6, 1, 86, 84, 24, 1, 840, 1110, 480, 120, 1, 11642, 16620, 9120, 3240, 720, 1, 227892, 300846, 185640, 82320, 25200, 5040, 1, 6285806, 6810804, 4299624, 2142000, 816480, 221760, 40320, 1, 243593040, 199239270, 117205200, 60890760, 26157600

Offset: 1

Joel B. Lewis, Mar 07 2013

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 elements a, b, c, d such that a < b < c and d is incomparable to the other three.

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 (weakly graded (3+1)-free posets with n labeled vertices, disregarding height), see A222865. For strongly graded (3+1)-free posets, see A222863. For all weakly graded posets, see A001833. For all (3+1)-free posets, see A079145.

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

A228551 Number of connected labeled graded posets on n vertices.

Original entry on oeis.org

1, 1, 2, 12, 146, 2820, 79682, 3109932, 163268786, 11373086100, 1049057429762, 128748967088412, 21220651011079346, 4747770003765805380, 1456585782002699624642, 6390825031791150383749864

Offset: 0

Daniele P. Morelli, Aug 25 2013

nonn

Here 'graded' is to be intended as in A001833.

David A. Klarner, The number of graded partially ordered sets, Journal of Combinatorial Theory, vol.6, no.1, pp.12-19, (January-1969).

Cf. A001833.

E.g.f.: 1 + log(F(x)), where F(x) is the e.g.f. of A001833.

A174122 Partial sums of A001831.

Original entry on oeis.org

1, 2, 5, 18, 105, 946, 12589, 240482, 6526289, 250119330, 13512676053, 1027978959346, 110155994874553, 16631509898085074, 3540687511804739837, 1063409634646294541250, 450894476653951603096737

Offset: 0

Jonathan Vos Post, Mar 08 2010

nonn

Partial sums of number of labeled graded partially ordered sets with n elements. The subsequence of primes in this partial sum begins: 2, 5, 12589.

Cf. A001831, A002031, A047863, A052332, A001833, A048194, A052296, A135753, A135754.

a(n) = SUM[i=0..n] A001831(i) = SUM[i=0..n] SUM[j=0..i] ((-1)^j*C(n,j)*A047863(j)).

Showing 1-9 of 9 results.

cp's OEIS Frontend

A001831 Number of labeled graded partially ordered sets with n elements of height at most 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A361912 The number of unlabeled graded posets with n elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Sage

Extensions

A361920 Number of unlabeled ranked posets with n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Sage

Extensions

A361951 Triangle read by rows: T(n,k) is the number of labeled weakly graded (ranked) posets with n elements and rank k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A006860 Erroneous version of A223911: Tiered orders on n nodes.

Views

Author

Keywords

Comments

References

Links

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A228551 Number of connected labeled graded posets on n vertices.