A000112 -id:A000112 - cp's OEIS frontend

A342447 T(n,e) is the number of unlabeled posets of n>=0 points with e>=0 arcs in the Hasse diagram, irregular triangle read by rows.

1, 1, 1, 1, 1, 1, 3, 1, 1, 4, 8, 2, 1, 1, 4, 11, 29, 12, 5, 1, 1, 4, 12, 43, 105, 92, 45, 12, 3, 1, 1, 4, 12, 46, 156, 460, 582, 487, 204, 71, 14, 7, 1, 1, 4, 12, 47, 170, 670, 2097, 3822, 4514, 3271, 1579, 561, 186, 44, 16, 4, 1, 1, 4, 12, 47, 173, 731, 2954, 10513, 24584, 40182

Offset: 0

R. J. Mathar, Mar 12 2021

Maximal e for a given n (i.e., the length of the n-th row minus 1) is A002620(n), see Mathematics StackExchange. - Andrey Zabolotskiy, Mar 12 2021

			The table starts
1 ;
1 ;
1 1 ;
1 1 3 ;
1 1 4  8  2 ;
1 1 4 11 29  12   5 ;
1 1 4 12 43 105  92   45   12    3 ;
1 1 4 12 46 156 460  582  487  204   71   14   7 ;
1 1 4 12 47 170 670 2097 3822 4514 3271 1579 561 186 44 16 4 ;
...
T(4,0) = 1: the 4-point poset with no relations, 4 isolated points in the Hasse diagram.
T(4,1) = 1: the 4-point poset with one relation, the Hasse diagram has one vertical line and 2 isolated points.
T(4,2) = 4: the 4 posets contributing to A022016(4) = 4, extended by additional isolated point when the number of points is less than 4.
T(4,3) = 8: the 8 posets contributing to A022017(3).
T(4,4) = 2: the "dagaz rune" poset {1<3, 2<3, 1<4, 2<4}
  o o
  |X|
  o o
and the "diamond" poset {1<2, 1<3, 2<4, 3<4}
    o
   / \
  o   o
   \ /
    o

R. J. Mathar, Table of T(n,e) for n<=10
Brendan McKay, Digraphs, posets tables at the bottom of the page.
R. J. Mathar, Poset Illustrations
Mathematics StackExchange, Maximum number of comparisons required to define a partial ordering, 2021.

Cf. A000112 (row sums), A263864, A022016 (convergents down rows), A002620, A342472 (lower bound row length), A342590 (connected), A342589 (labeled), A376633 (self-dual).

T(n,0) = T(n,1) = 1.

T(n,e) = A022016(e) for n >= 2e.

T(0,0) = 1 prepended and "conjecture" removed from A022016 formula. Andrey Zabolotskiy, Mar 12 2021

A263864 Triangle read by rows: T(n,k) (n>=1, k>=1) is the number of posets with n elements whose Hasse diagram has k connected components.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 10, 4, 1, 1, 44, 13, 4, 1, 1, 238, 60, 14, 4, 1, 1, 1650, 312, 63, 14, 4, 1, 1, 14512, 2075, 328, 64, 14, 4, 1, 1, 163341, 17316, 2159, 331, 64, 14, 4, 1, 1, 2360719, 186173, 17801, 2175, 332, 64, 14, 4, 1, 1, 43944974, 2594568, 189406, 17885, 2178, 332, 64, 14, 4, 1, 1, 1055019099, 47041877

Offset: 1

Christian Stump, Oct 28 2015

Multiset transformation of A000608.

			Triangle begins:
   1;
   1,  1;
   3,  1,  1;
  10,  4,  1,  1;
  44, 13,  4,  1,  1;
  ...

Alois P. Heinz, Rows n = 1..16, flattened
FindStat - Combinatorial Statistic Finder, The number of connected components of the Hasse diagram for the poset.
Salah Uddin Mohammad, Md. Shah Noor, and Md. Rashed Talukder, An Exact Enumeration of the Unlabeled Disconnected Posets, J. Int. Seq., Vol. 25 (2022), Article 22.5.4.
Wikipedia, Hasse diagram
Index entries for sequences related to posets

Cf. A000112 (row sums), A000608 (k=1).

More terms from R. J. Mathar, Jul 12 2020

A263859 Triangle read by rows: T(n,k) (n>=1, k>=0) is the number of posets with n elements and rank k (or depth k+1).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 8, 6, 1, 1, 20, 31, 10, 1, 1, 55, 162, 84, 15, 1, 1, 163, 940, 734, 185, 21, 1, 1, 556, 6372, 7305, 2380, 356, 28, 1, 1, 2222, 52336, 86683, 35070, 6259, 623, 36, 1, 1, 10765, 534741, 1261371, 619489, 125597, 14258, 1016, 45, 1

Offset: 1

Christian Stump, Oct 28 2015

Row sums give A000112, n >= 1.

The rank of a poset is the number of cover relations in a maximal chain.

			Triangle begins:
1,
1,1,
1,3,1,
1,8,6,1,
1,20,31,10,1,
1,55,162,84,15,1,
1,163,940,734,185,21,1,
1,556,6372,7305,2380,356,28,1,
1,2222,52336,86683,35070,6259,623,36,1,
1,10765,534741,1261371,619489,125597,14258,1016,45,1,
...

R. J. Mathar, Table of n, a(n) for n = 1..136
G. Brinkmann and B. D. McKay, Posets on up to 16 Points [On Brendan McKay's home page]
G. Brinkmann and B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179.
FindStat - Combinatorial Statistic Finder, The rank of the poset.
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Cf. A000112 (row sums), A342500 (connected).

More terms from Brinkmann-McKay (2002) added by N. J. A. Sloane, Mar 18 2017

A022016 Number of partially ordered sets with no isolated points and with n "lines": pairs (a,b) where a < b and there is no c with a < c < b. The lines form the minimal basis for the partial ordering.

Original entry on oeis.org

1, 1, 4, 12, 47, 174, 749, 3291, 15675, 78104, 411042, 2261961, 13009112, 77860234

Offset: 0

Franklin T. Adams-Watters, Mar 30 2002

The points are unlabeled.

			See Sloane's link.

See A000112 for references and links about partially ordered sets.

N. J. A. Sloane, Illustration of initial terms of A022016 and A022017.

Cf. A000112, A022017, A342447.

a(6)-a(13) from Rico Zöllner and Konrad Handrich, Nov 19 2024

A022017 Number of connected partially ordered sets with n "lines": pairs (a,b) where a < b and there is no c with a < c < b. The lines form the minimal basis for the partial ordering.

Original entry on oeis.org

1, 3, 8, 29, 103, 442, 1953, 9502, 48533, 262634, 1485764, 8777397, 53869119

Offset: 1

Franklin T. Adams-Watters, Mar 30 2002

The points are unlabeled.

			See Sloane's link.

See A000112 for references and links about partially ordered sets.

N. J. A. Sloane, Illustration of initial terms of A022016 and A022017.
Index entries for sequences related to posets

Cf. A000112, A000608, A022016. Column sums of A342590.

a(6)-a(9) from A342590. - R. J. Mathar, Mar 21 2021

a(10)-a(13) from Rico Zöllner and Konrad Handrich, Nov 19 2024

A079146 Number of unlabeled semitransitive orders on n elements: (1+3)-free posets.

Original entry on oeis.org

1, 2, 5, 15, 49, 173, 639, 2469, 9997, 43109, 205092, 1153646, 8523086, 91156133, 1446766659, 32998508358, 1047766596136, 45632564217917, 2711308588849394, 219364550983697100, 24151476334929009951, 3618445112608409433287

Offset: 1

Detlef Pauly (dettodet(AT)yahoo.de), Dec 27 2002

nonn

M. Guay-Paquet, A modular relation for the chromatic symmetric functions of (3+1)-free posets, arXiv preprint arXiv:1306.2400 [math.CO], 2013.
M. Guay-Paquet, A. H. Morales, E. Rowland, Structure and enumeration of (3+1)-free posets (extended abstract), arXiv:1212.5356 [math.CO], 2012.

Cf. A079145 (labeled semitransitive orders), A000112.

nmax = 23; co = Coefficient; ex = Exponent;
b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i<1, {}, Flatten[Table[Function[ {p}, p + j x^i] /@ b[n - i j, i - 1], {j, 0, n/i}]]]];
g[n_, k_] := g[n, k] = Sum[Sum[2^Sum[Sum[GCD[i, j] co[s, x, i] co[t, x, j], {j, 1, ex[t, x]}], {i, 1, ex[s, x]}]/Product[i^co[s, x, i]*co[s, x, i]!, {i, 1, ex[s, x]}]/Product[i^co[t, x, i] co[t, x, i]!, {i, 1, ex[t, x]}], {t, b[n + k, n + k]}], {s, b[n, n]}];
A[n_, k_] := g[Min[n, k], Abs[n - k]];
A[d_] := Sum[A[n, d - n], {n, 0, d}];
B[x_] = Sum[A[n] x^n, {n, 0, nmax}];
S[, ] = 0; Do[S[c_, t_] = Series[1 + (c/(1 + c)) S[c, t]^2 + t S[c, t]^3, {c, 0, nmax}, {t, 0, nmax}] // Normal, {nmax}];
T[x_] = 1 - S[x/(1 - x), 1 - 2x - 1/B[x]];
Rest[CoefficientList[-T[x] + O[x]^nmax, x]] (* Jean-François Alcover, Aug 11 2018, after Alois P. Heinz *)

G.f.: S(x/(1-x), T(x)), where S(x, y) is the g.f. for A221494 and T(x) is the g.f. for A221492. [Mathieu Guay-Paquet, Jan 18 2013]

More terms from Mathieu Guay-Paquet, Jan 18 2013

A079265 Number of antisymmetric transitive binary relations on n unlabeled points.

Original entry on oeis.org

1, 2, 7, 32, 192, 1490, 15067, 198296, 3398105, 75734592, 2191591226, 82178300654, 3984499220967, 249298391641352, 20089200308020179, 2081351202770089728

Offset: 0

N. J. A. Sloane, Feb 16 2003

Also, number of unconstrained mixed models with n factors.

A. Hess and H. Iyer, Enumeration of mixed linear models and SAS macro for computation of confidence intervals for variance components, presented at Applied Statistics in Agriculture Conference at Kansas State University 2001.

R. Bayon, N. Lygeros and J.-S. Sereni, New progress in enumeration of mixed models, Applied Mathematics E-Notes, 5 (2005), 60-65.
R. Bayon, N. Lygeros and J.-S. Sereni, Nouveaux progrès dans l'énumération des modèles mixtes, in Knowledge discovery and discrete mathematics : JIM'2003, INRIA, Université de Metz, France, 2003, pp. 243-246.
Gunnar Brinkmann and Brendan D. McKay, Counting unlabelled topologies and transitive relations.
Gunnar Brinkmann and Brendan D. McKay, Counting Unlabelled Topologies and Transitive Relations, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.1.
R. Fraïssé and N. Lygeros, Petits posets: dénombrement, représentabilité par cercles et "compenseurs", C. R. Acad. Sci. Paris, Vol. 313, series I, pp. 417-420, 1991.
Ann Marie Hess, Mixed Models Site
G. Pfeiffer, Counting Transitive Relations, preprint, 2004.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

Cf. A000112 (partial orders), A091073 (transitive relations), A001930 (quasi-orders), A085628 (labeled antisymmetric transitive relations).

Cf. A079263, A006126, A006602, A006896-A006898.

a(10)-a(12) and new description from Goetz Pfeiffer (goetz.pfeiffer(AT)nuigalway.ie), Jan 21 2004

a(13)-a(15) from Brinkmann's and McKay's paper by Vladeta Jovovic, Jan 04 2006

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

A091073 Number of transitive relations on n unlabeled points.

Original entry on oeis.org

1, 2, 8, 39, 242, 1895, 19051, 246895, 4145108, 90325655, 2555630036, 93810648902, 4461086120602, 274339212258846, 21775814889230580, 2226876304576948549

Offset: 0

Goetz Pfeiffer (goetz.pfeiffer(AT)nuigalway.ie), Jan 21 2004

a(13)-a(15) are from Brinkmann's and McKay's paper. - Vladeta Jovovic, Jan 07 2006

Gunnar Brinkmann and Brendan D. McKay, Counting unlabelled topologies and transitive relations.
Gunnar Brinkmann and Brendan D. McKay, Counting Unlabelled Topologies and Transitive Relations, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.1.
G. Pfeiffer, Counting Transitive Relations, preprint, 2004.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

Cf. A079265 (antisymmetric transitive relations), A001930 (reflexive transitive relations), A000112 (partial orders), A006905 (labeled transitive relations).

More terms from Vladeta Jovovic, Jan 07 2006

cp's OEIS Frontend

A342447 T(n,e) is the number of unlabeled posets of n>=0 points with e>=0 arcs in the Hasse diagram, irregular triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A263864 Triangle read by rows: T(n,k) (n>=1, k>=1) is the number of posets with n elements whose Hasse diagram has k connected components.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A263859 Triangle read by rows: T(n,k) (n>=1, k>=0) is the number of posets with n elements and rank k (or depth k+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A022016 Number of partially ordered sets with no isolated points and with n "lines": pairs (a,b) where a < b and there is no c with a < c < b. The lines form the minimal basis for the partial ordering.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A022017 Number of connected partially ordered sets with n "lines": pairs (a,b) where a < b and there is no c with a < c < b. The lines form the minimal basis for the partial ordering.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A079146 Number of unlabeled semitransitive orders on n elements: (1+3)-free posets.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A079265 Number of antisymmetric transitive binary relations on n unlabeled points.

Views

Author

Keywords

Comments

References

Links

Crossrefs

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.