A342447 -id:A342447 - cp's OEIS frontend

A376894 Stationary differences in A342447: a(n) = A342447(2k-n+1,k)-A342447(2k-n,k) which does not depend on k if k>= 2n-2 (for n>0).

1, 3, 14, 61, 273, 1228, 5631, 26141, 123261, 589251, 2855815, 14021038, 69707192

Offset: 1

Rico Zöllner and Konrad Handrich, Oct 22 2024

Number of unlabeled posets A342447(j,k) with j points, without isolated points, with k arcs in the Hasse diagramm missing n points to achieve saturation of the poset i.e. j=2k-n+1.
A342447 is the number of unlabeled posets of j points with k arcs in the Hasse diagram.
A342447(j,k)-A342447(j-1,k) = 0 if j > 2k.
For k >= 2n-2, A342447(2k-n+1,k)-A342447(2k-n,k) does not depend on k.
Therefore we define: a(n) = A342447(2k-n+1,k)-A342447(2k-n,k).
A342447(2k-n,k) = A022016(k) - a(1)-...-a(n) for k >= 2n-2, n>0
Proof will soon be submitted to JOIS.

			See the table of A342447
 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 ;
 ...
The differences between row j and j-1 of column k (convergence indicated by | |):
 0 ;
 0 ;
 0 |1| ;
 0  0 |3| ;
 0  0 |1| 8    2 ;
 0  0  0 |3|  27    12     5 ;
 0  0  0 |1| |14|   93    87      45    12   ... ;
 0  0  0  0   |3|   51   368     537   475   ... ;
 0  0  0  0   |1|  |14|  210    1515  3335   ... ;
 0  0  0  0    0    |3|  |61|    857  6691   ... ;
 0  0  0  0    0    |1|  |14|    258  3683   ... ;
 0  0  0  0    0     0    |3|    |61| 1127   ... ;
 0  0  0  0    0     0    |1|    |14| |273|  ... ;
a(n) = A342447(2k-n+1,k)-A342447(2k-n,k) for n>=1
e.g. for n = 2 -> k = 2n-2 = 2
a(2) = A342447(3,2) - A342447(2,2) = 3 - 0 = 3
for n = 3 -> k >= 2n-2 = 6
a(3) = A342447(10,6) - A342447(9,6) = 745 - 731 = 14

R. P. Stanley, Enumerative Combinatorics I, 2nd. ed.

Cf. A000112, A022016.

Differences of A342447.

a(8)-a(13) from Konrad Handrich, Jan 07 2025

A000112 Number of partially ordered sets ("posets") with n unlabeled elements.

Original entry on oeis.org

1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, 2567284, 46749427, 1104891746, 33823827452, 1338193159771, 68275077901156, 4483130665195087

Offset: 0

N. J. A. Sloane

Also number of fixed effects ANOVA models with n factors, which may be both crossed and nested.

			R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, page 98, Fig. 3-1 (or 2nd. ed., Fig. 3.1, p. 243) shows the unlabeled posets with <= 4 points.
From _Gus Wiseman_, Aug 14 2019: (Start)
Also the number of unlabeled T_0 topologies with n points. For example, non-isomorphic representatives of the a(4) = 16 topologies are:
  {}{1}{12}{123}{1234}
  {}{1}{2}{12}{123}{1234}
  {}{1}{12}{13}{123}{1234}
  {}{1}{12}{123}{124}{1234}
  {}{1}{2}{12}{13}{123}{1234}
  {}{1}{2}{12}{123}{124}{1234}
  {}{1}{12}{13}{123}{124}{1234}
  {}{1}{2}{12}{13}{123}{124}{1234}
  {}{1}{2}{12}{13}{123}{134}{1234}
  {}{1}{2}{3}{12}{13}{23}{123}{1234}
  {}{1}{2}{12}{13}{24}{123}{124}{1234}
  {}{1}{12}{13}{14}{123}{124}{134}{1234}
  {}{1}{2}{3}{12}{13}{23}{123}{124}{1234}
  {}{1}{2}{12}{13}{14}{123}{124}{134}{1234}
  {}{1}{2}{3}{12}{13}{14}{23}{123}{124}{134}{1234}
  {}{1}{2}{3}{4}{12}{13}{14}{23}{24}{34}{123}{124}{134}{234}{1234}
(End)

G. Birkhoff, Lattice Theory, 1961, p. 4.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 60.
E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date.
J. L. Davison, Asymptotic enumeration of partial orders. Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986). Congr. Numer. 53 (1986), 277--286. MR0885256 (88c:06001)
E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961.
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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, pages 96ff; Vol. I, 2nd. ed., Chap. 3, pp. 241ff; Vol. 2, Problem 5.39, p. 88.
For further references concerning the enumeration of topologies and posets see under A001035.

David Wasserman, Table of n, a(n) for n = 0..16
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 unlabeled topologies and transitive relations.
G. Brinkmann and B. D. McKay, Counting unlabeled topologies and transitive relations, J. Integer Sequences, Volume 8, 2005.
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.
Kim Ki-Hang Butler, The number of partially ordered sets, Journal of Combinatorial Theory, Series B 13.3 (1972): 276-289.
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184. [Annotated scan of pages 180 and 183 only]
Kim Ki-Hang Butler and Gaoacs Markowsky. The number of partially ordered sets. II., J. Korean Math. Soc 11 (1974): 7-17.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
C. Chaunier, Letter to N. J. A. Sloane, Jun 22 1993, with several attachments
C. Chaunier and N. Lygeros, The Number of Orders with Thirteen Elements, Order 9:3 (1992) 203-204. [See Chaunier letter]
C. Chaunier and N. Lygeros, Le nombre de posets à isomorphie près ayant 12 éléments Theoretical Computer Science, 123 p. 89-94, 1994.
C. Chaunier and N. Lygeros, Progrès dans l'énumération des posets, C. R. Acad. Sci. Paris 314 série I (1992) 691-694. [See Chaunier letter]
E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date [Annotated scanned copy]
Gábor Czédli, Minimum-sized generating sets of the direct powers of free distributive lattices, arXiv:2309.13783 [math.CO], 2023. See p. 14. See also CUBO, A Mathematical Journal, Vol. 26, no. 2, pp. 217-237, August 2024.
M. Erné and K. Stege, The number of partially ordered (labeled) sets, Preprint, 1989. (Annotated scanned copy)
Uli Fahrenberg, Christian Johansen, Georg Struth, and Ratan Bahadur Thapa, Generating Posets Beyond N, arXiv:1910.06162 [cs.FL], 2019.
S. R. Finch, Transitive relations, topologies and partial orders, June 5, 2003. [Cached copy, with permission of the author]
FindStat - Combinatorial Statistic Finder, Posets
R. Fraisse and N. Lygeros, Petits posets: dénombrement, représentabilité par cercles et compenseurs C. R. Acad. Sci. Paris, 313, I, 417-420, 1991.
E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961. [Annotated scanned copy]
G. Grekos, Letter to N. J. A. Sloane, Oct 31 1994, with attachments
M. Guay-Paquet, A modular relation for the chromatic symmetric functions of (3+1)-free posets, arXiv preprint arXiv:1306.2400 [math.CO], 2013.
Ann Marie Hess, Mixed Models Site
C. Joslyn, E. Hogan, and A. Pogel, Conjugacy and Iteration of Standard Interval Rank in Finite Ordered Sets, arXiv preprint arXiv:1409.6684 [math.CO], 2014.
Dongseok Kim, Young Soo Kwon, and Jaeun Lee, Enumerations of finite topologies associated with a finite graph, arXiv preprint arXiv:1206.0550 [math.CO], 2012.
D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205 (1975) 205-220.
N. Lygeros, Calculs exhaustifs sur les posets d'au plus 7 éléments, SINGULARITE, vol. 2 n4 p. 10-24, avril 1991.
N. Lygeros and P. Zimmermann, Computation of P(14), the number of posets with 14 elements: 1.338.193.159.771
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Bob Proctor, Chapel Hill Poset Atlas
D. Rusin, Further information and references [Broken link]
D. Rusin, Further information and references [Cached copy]
Henry Sharp, Jr., Quasi-orderings and topologies on finite sets, Proceedings of the American Mathematical Society 17.6 (1966): 1344-1349. [Annotated scanned copy]
N. J. A. Sloane, List of sequences related to partial orders, circa 1972
N. J. A. Sloane, Classic Sequences
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.)
Szilárd Szalay, The classification of multipartite quantum correlation, arXiv:1806.04392 [quant-ph], 2018.
N. L. White, Two letters to N. J. A. Sloane, 1970, with hand-drawn enclosure
J. A. Wright, There are 718 6-point topologies, quasiorderings and transgraphs, Preprint, 1970 [Annotated scanned copy]
J. A. Wright, Two related abstracts, 1970 and 1972 [Annotated scanned copies]
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences
Stav Zalel, Covariant Growth Dynamics, arXiv:2302.10582 [gr-qc], 2023.
Index entries for sequences related to posets
Index entries for "core" sequences

Cf. A000798 (labeled topologies), A001035 (labeled posets), A001930 (unlabeled topologies), A006057.
Cf. A079263, A079265, A065066 (refined by maximal elements), A342447 (refined by number of arcs).
Row sums of A263859. Euler transform of A000608.
Cf. A316978, A319559, A326939, A326943, A326944, A326947.

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

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

A342590 T(n,k) is the number of connected posets of n unlabeled elements with k covering relations (n>=1, k>=0). Triangle read by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 0, 0, 0, 8, 2, 0, 0, 0, 0, 27, 12, 5, 0, 0, 0, 0, 0, 91, 87, 45, 12, 3, 0, 0, 0, 0, 0, 0, 350, 532, 475, 201, 71, 14, 7, 0, 0, 0, 0, 0, 0, 0, 1376, 3272, 4298, 3197, 1565, 554, 186, 44, 16, 4, 0, 0, 0, 0, 0, 0, 0, 0, 5743, 19396, 36664, 41706, 31931, 16972

Offset: 1

R. J. Mathar, Mar 16 2021

			The table starts
1: 1
2: 0 1
3: 0 0 3
4: 0 0 0 8 2
5: 0 0 0 0 27 12   5
6: 0 0 0 0 0  91  87   45   12    3
7: 0 0 0 0 0   0 350  532  475  201   71   14   7
8: 0 0 0 0 0   0   0 1376 3272 4298 3197 1565 554 186 44 16 4

R. J. Mathar, Table of T(n,k) for n = 1..10
Index entries for sequences related to posets

Cf. A000608 (row sums), A022017 (column sums), A342447 (not necess. connected), A342588 (labeled).

A342589 T(n,k) is the number of posets of n labeled elements with k covering relations (n>=1, k>=0). Triangle read by rows.

Original entry on oeis.org

1, 1, 2, 1, 6, 12, 1, 12, 60, 128, 18, 1, 20, 180, 880, 2090, 960, 100, 1, 30, 420, 3480, 17550, 47772, 43920, 15000, 1710, 140, 1, 42, 840, 10360, 84630, 452004, 1428868, 2094960, 1465170, 491540, 90594, 10080, 770

Offset: 1

R. J. Mathar, Mar 16 2021

			The triangle starts:
  1: 1
  2: 1 2
  3: 1 6 12
  4: 1 12 60 128 18
  5: 1 20 180 880 2090 960 100
  6: 1 30 420 3480 17550 47772 43920 15000 1710 140
  7: 1 42 840 10360 84630 452004 1428868 2094960 1465170 491540 90594 10080 770

Brendan McKay, Table of T(n,k) for n = 1..13
Index entries for sequences related to posets

Cf. A001035 (row sums), A002378 (k=1), A033486 (k=2?), A342447 (unlabeled), A342588 (connected).

A342472 T(n,k) is the maximum sum of products of adjacent parts in all compositions of n into k parts: triangle read by rows.

Original entry on oeis.org

0, 0, 1, 0, 2, 2, 0, 4, 4, 3, 0, 6, 6, 5, 4, 0, 9, 9, 8, 6, 5, 0, 12, 12, 11, 9, 7, 6, 0, 16, 16, 15, 12, 10, 8, 7, 0, 20, 20, 19, 16, 13, 11, 9, 8, 0, 25, 25, 24, 20, 17, 14, 12, 10, 9, 0, 30, 30, 29, 25, 21, 18, 15, 13, 11, 10, 0, 36, 36, 35, 30, 26, 22, 19, 16, 14, 12, 11, 0, 42, 42, 41

Offset: 1

R. J. Mathar, Mar 13 2021

Denote compositions of n into k parts by n = p_1 +p_2 + .... +p_k, p_i>0. For these compositions let S(n,k,c) = p_1*p_2 +p_2*p_3 +.. +p_{k-1}*p_k. Then T(n,k) = max_c S(n,k,c), where c runs through all A007318(n-1,k-1) compositions.
Background: Let p_i be the number of elements in level i of a poset of n points. Connect all points on level i with all points on level i+1 "maximally" with p_i*p_{i+1} arcs in the Hasse diagram. So T(n,k) is a lower bound on the maximum number of arcs in a Hasse diagram with k levels, and the maximum T(n,k)  (+1 to add the diagrams of n disconnected elements) of a row is a lower bound of the row lengths of A342447.
T(n,2) = A002620(n) has the standard interpretation of maximizing the area p_1*p_2 of a rectangle given the semiperimeter p_1+p_2=n. [S=p_1*p_2=p_1*(n-p_1) is a quadratic function of p_1 with well defined maximum.] - R. J. Mathar, Mar 14 2021
T(n,3) maximizes S = +p_1*p_2+p_2*p_3 = p_1*p_2+p_2*(n-p_1-p_2) = p_2*(n-p_2) which again is a quadratic function of p_2 with well defined maximum. - R. J. Mathar, Mar 14 2021
For k>=4 and odd n-k consider p_1=1, p_2=(n-k+1)/2, p_3=p_2+1, p_4=p_5=..=p_k=1 which gives S= n+(n-k)+[(n-k)^2-5]/4, a lower bound (apparently strict). For k>=4 and even n-k consider p_1=1, p_2=p_3=(n-k+2)/2, p_4=p_5=...=p_k=1 which gives S=n-2+(n-k+2)^2/4, a lower bound (apparently strict). - R. J. Mathar, Mar 14 2021

			For n=6 and k=3 for example 6 = 2+3+1 = 1+3+2 obtain 2*3+3*1 = 9 = T(6,3).
For n=6 and k=4 for example 6 = 1+2+2+1 obtains 1*2+2*2+2*1=8 =T(6,4).
For n=7 and k=4 for example 7 = 1+3+2+1 = 1+2+3+1 obtains 1*2+2*3+3*1 = 11 = T(7,4).
For n=7 and k=5 for example 7 = 1+1+2+2+1 = 1+2+2+1+1 obtains 1*2+2*2+2*1+1*1 = 9 = T(7,5).
The triangle starts with n>=1 and 1<=k<=n as:
  0
  0   1
  0   2   2
  0   4   4   3
  0   6   6   5   4
  0   9   9   8   6   5
  0  12  12  11   9   7   6
  0  16  16  15  12  10   8   7
  0  20  20  19  16  13  11   9   8
  0  25  25  24  20  17  14  12  10   9
  0  30  30  29  25  21  18  15  13  11  10
  0  36  36  35  30  26  22  19  16  14  12  11
  0  42  42  41  36  31  27  23  20  17  15  13  12
  0  49  49  48  42  37  32  28  24  21  18  16  14  13
  0  56  56  55  49  43  38  33  29  25  22  19  17  15  14

Cf. A002620 (columns 2,3,5 ?), A024206 (column 4?), A033638 (column 6?), A290743 (column 7?), A342447.

# Maximum of Sum_i  p_i*p(i+1) over all combinations n=p_1+p_2+..p_k
A342472 := proc(n,k)
    local s,c;
    s := 0 ;
    for c in combinat[composition](n,k) do
        add( c[i]*c[i+1],i=1..nops(c)-1) ;
        s := max(s,%) ;
    end do:
    s ;
end proc:
for n from 1 to 15 do
    for k from 1 to n do
        printf("%3d ",A342472(n,k)) ;
    end do:
    printf("\n") ;
end do:

T(n,n) = n-1; where all p_i=1.
T(n,2) = T(n,3) = A002620(n).
T(n,k) >= 2*n-k+((n-k)^2-5)/4, n-k odd, k>=4. - R. J. Mathar, Mar 14 2021
T(n,k) >= n-2+(n-k+2)^2/4, n-k even, k>=4. - R. J. Mathar, Mar 14 2021

A376633 T(n,k) is the number of nonisomorphic n-element self-dual posets (or partially ordered sets) with k arcs in the Hasse diagram, irregular triangle read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 3, 5, 2, 1, 1, 1, 2, 4, 9, 11, 12, 5, 4, 1, 1, 1, 2, 4, 10, 16, 26, 22, 21, 10, 5, 0, 1, 1, 1, 2, 4, 11, 20, 44, 65, 98, 86, 79, 41, 25, 8, 4, 2, 2, 1, 1, 2, 4, 11, 21, 51, 92, 175, 220, 276, 237, 208, 103, 67, 25, 18, 5, 3, 0, 1, 1, 1, 2, 4, 11, 22, 55, 114, 264, 462, 798, 1015, 1294, 1180, 1035, 676, 477, 243, 149, 57, 36, 13, 8, 2, 4, 1, 1, 1, 2, 4, 11, 22, 56, 121, 303, 614, 1264, 2042, 2348, 3995, 4755, 4272, 3910, 2680, 1977, 1078, 697, 300, 189, 60, 50, 15, 12, 0, 3, 0, 1

Offset: 1

Rico Zöllner and Konrad Handrich, Sep 30 2024

Posets whose Hasse diagram looks the same if it is turned upside down.

The dual poset P* of the poset P is defined by: s ≤ t in P* if and only if t ≤ s in P. If P and P* are isomorphic, then P is called self-dual.

			The table starts:
1 ;
1 1 ;
1 1 1 ;
1 1 2 2 2 ;
1 1 2 3 5 2 1 ;
1 1 2 4 9 11 12 5 4 1 ;
1 1 2 4 10 16 26 22 21 10 5 0 1 ;
1 1 2 4 11 20 44 65 98 86 79 41 25 8 4 2 2 ;
1 1 2 4 11 21 51 92 175 220 276 237 208 103 67 25 18 5 3 0 1 ;
1 1 2 4 11 22 55 114 264 462 798 1015 1294 1180 1035 676 477 243 149 57 36 13 8 2 4 1;
...

R. P. Stanley, Enumerative Combinatorics I, 2nd. ed., pp. 277.

Cf. A000112, A022016, A022017, A342447.

Row sums: A133983.

cp's OEIS Frontend

A376894 Stationary differences in A342447: a(n) = A342447(2k-n+1,k)-A342447(2k-n,k) which does not depend on k if k>= 2n-2 (for n>0).

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Extensions

A000112 Number of partially ordered sets ("posets") with n unlabeled elements.

Views

Author

Keywords

Comments

Examples

References

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

A342590 T(n,k) is the number of connected posets of n unlabeled elements with k covering relations (n>=1, k>=0). Triangle read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

A342589 T(n,k) is the number of posets of n labeled elements with k covering relations (n>=1, k>=0). Triangle read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

A342472 T(n,k) is the maximum sum of products of adjacent parts in all compositions of n into k parts: triangle read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A376633 T(n,k) is the number of nonisomorphic n-element self-dual posets (or partially ordered sets) with k arcs in the Hasse diagram, irregular triangle read by rows.

Views

Author

Keywords

Comments

Examples

References

Crossrefs