A223911 -id:A223911 - cp's OEIS frontend

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

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

Offset: 1

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

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

A218695 Square array A(h,k) = (2^h-1)A(h,k-1) + Sum_{i=1..h-1} binomial(h,h-i)2^i*A(i,k-1), with A(1,k) = A(h,1) = 1; read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 7, 1, 1, 25, 25, 1, 1, 79, 265, 79, 1, 1, 241, 2161, 2161, 241, 1, 1, 727, 16081, 41503, 16081, 727, 1, 1, 2185, 115465, 693601, 693601, 115465, 2185, 1, 1, 6559, 816985, 10924399, 24997921, 10924399, 816985, 6559, 1

Offset: 1

M. F. Hasler, Nov 04 2012

This symmetric table is defined in the Kreweras papers, used also in A223911. Its upper or lower triangular part equals A183109, which might provide a simpler formula.
Number of h X k binary matrices with no zero rows or columns. - Andrew Howroyd, Mar 29 2023
A(h,k) is the number of coverings of [h] by tuples (A_1,...,A_k) in P([h])^k with nonempty A_j, with P(.) denoting the power set. For the disjoint case see A019538. For tuples with "nonempty" omitted see A092477 and A329943 (amendment by Manfred Boergens, Jun 24 2024). - Manfred Boergens, May 26 2024

			Array A(h,k) begins:
=====================================================
h\k | 1   2      3        4         5           6 ...
----+------------------------------------------------
  1 | 1   1      1        1         1           1 ...
  2 | 1   7     25       79       241         727 ...
  3 | 1  25    265     2161     16081      115465 ...
  4 | 1  79   2161    41503    693601    10924399 ...
  5 | 1 241  16081   693601  24997921   831719761 ...
  6 | 1 727 115465 10924399 831719761 57366997447 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)
G. Kreweras, Dénombrements systématiques de relations binaires externes, Math. Sci. Humaines 26 (1969) 5-15.
G. Kreweras, Dénombrement des ordres étagés, Discrete Math., 53 (1985), 147-149.

Columns 1..3 are A000012, A058481, A058482.
Main diagonal is A048291.
Cf. A019538, A056152 (unlabeled case), A052332, A092477, A183109, A223911, A329943.

c(h,k)={(h<2 || k<2) & return(1); sum(i=1,h-1,binomial(h,h-i)*2^i*c(i,k-1))+(2^h-1)*c(h,k-1)}
/* For better performance when h and k are large, insert the following memoization code before "sum(...)": cM=='cM & cM=matrix(h,k); my(s=matsize(cM));
s[1] >= h & s[2] >= k & cM[h,k] & return(cM[h,k]);
s[1]

A(m, n) = sum(k=0, m, (-1)^(m-k) * binomial(m, k) * (2^k-1)^n ) \\ Andrew Howroyd, Mar 29 2023

From Andrew Howroyd, Mar 29 2023: (Start)
A(h, k) = Sum_{i=0..h} (-1)^(h-i) * binomial(h, i) * (2^i-1)^k.
A052332(n) = Sum_{i=1..n-1} binomial(n,i)*A(i, n-i) for n > 0. (End)

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

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

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

Views

Author

Keywords

Comments

References

Links

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A218695 Square array A(h,k) = (2^h-1)*A(h,k-1) + Sum_{i=1..h-1} binomial(h,h-i)*2^i*A(i,k-1), with A(1,k) = A(h,1) = 1; read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

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

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

A218695 Square array A(h,k) = (2^h-1)A(h,k-1) + Sum_{i=1..h-1} binomial(h,h-i)2^i*A(i,k-1), with A(1,k) = A(h,1) = 1; read by antidiagonals.