A361951 -id:A361951 - cp's OEIS frontend

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

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

A361950 Array read by antidiagonals: T(n,k) = n! * Sum_{s} 2^(Sum_{i=1..k-1} s(i)*s(i+1))/(Product_{i=1..k} s(i)!) where the sum is over all nonnegative compositions s of n into k parts.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 13, 26, 1, 0, 1, 5, 22, 81, 162, 1, 0, 1, 6, 33, 166, 721, 1442, 1, 0, 1, 7, 46, 287, 1726, 9153, 18306, 1, 0, 1, 8, 61, 450, 3309, 24814, 165313, 330626, 1, 0, 1, 9, 78, 661, 5650, 50975, 494902, 4244481, 8488962, 1, 0

Offset: 0

Andrew Howroyd, Mar 31 2023

T(n,k) corresponds to c(k,n) in the Klarner reference. This is an intermediate step in the computation of the number of labeled weakly graded (ranked) posets. The number of elements in the poset is n and the rank k.

			Array begins:
======================================================
n/k| 0 1      2       3        4        5        6 ...
---+--------------------------------------------------
0  | 1 1      1       1        1        1        1 ...
1  | 0 1      2       3        4        5        6 ...
2  | 0 1      6      13       22       33       46 ...
3  | 0 1     26      81      166      287      450 ...
4  | 0 1    162     721     1726     3309     5650 ...
5  | 0 1   1442    9153    24814    50975    91866 ...
6  | 0 1  18306  165313   494902  1058493  1957066 ...
7  | 0 1 330626 4244481 13729846 29885567 55363650 ...
  ...
T(3,2) = 26: the nonnegative integer compositions of 3 with 2 parts are (0,3), (1,2), (2,1), (3,0). These contribute, respectively 2^0*3!/(0!*3!) = 1, 2^2*3!/(1!*2!) = 12, 2^2*3!/(2!*1!) = 12, 2^0*3!/(0!*3!) = 1, so T(3,2) = 1 + 12 + 12 + 1 = 26.

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals).
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19.

Columns k=0..7 are A000007, A000012, A047863, A000684, A001827, A001828, A001829, A001830.
Rows 0..2 are A000012, A000027, A028872(n+1).
The unlabeled version is A361952.
Cf. A361951.

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}
R(n)={Mat([Col(serlaplace(p)) | p<-C(n)])}
{ my(A=R(6)); for(i=1, #A, print(A[i,])) }

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

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 8, 6, 1, 0, 1, 20, 30, 9, 1, 0, 1, 55, 145, 66, 12, 1, 0, 1, 163, 745, 465, 111, 15, 1, 0, 1, 556, 4245, 3444, 964, 165, 18, 1, 0, 1, 2222, 27880, 28024, 8618, 1652, 228, 21, 1, 0, 1, 10765, 218058, 259974, 83322, 16569, 2556, 300, 24, 1

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.

			Triangle begins:
  1;
  0, 1;
  0, 1,   1;
  0, 1,   3,    1;
  0, 1,   8,    6,    1;
  0, 1,  20,   30,    9,   1;
  0, 1,  55,  145,   66,  12,   1;
  0, 1, 163,  745,  465, 111,  15,  1;
  0, 1, 556, 4245, 3444, 964, 165, 18, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..860 (rows 0..40)
Andrew Howroyd, PARI Program, Apr 2023.
Wikipedia, Graded poset.

Row sums are A361920.
The labeled version is A361951.
Cf. A263859, A361952, A361954 (connected).

\\ See link for program code.
{ my(A=A361953tabl(8)); for(i=1, #A, print(A[i, 1..i])) }

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 g.f. of column k of A361952.

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

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A361950 Array read by antidiagonals: T(n,k) = n! * Sum_{s} 2^(Sum_{i=1..k-1} s(i)*s(i+1))/(Product_{i=1..k} s(i)!) where the sum is over all nonnegative compositions s of n into k parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI