A001035 -id:A001035 - cp's OEIS frontend

A048172 Number of labeled series-parallel graphs with n edges.

1, 3, 19, 195, 2791, 51303, 1152019, 30564075, 935494831, 32447734143, 1257770533339, 53884306900515, 2528224238464471, 128934398091500823, 7101273378743303779, 420078397130637237915, 26563302733186339752511, 1788055775343964413724143, 127652707703771090396080939

Offset: 1

N. J. A. Sloane

Labeled N-free posets. - Detlef Pauly (dettodet(AT)yahoo.de), Dec 27 2002

Ronald C. Read, Graphical enumeration by cycle-index sums: first steps toward a unified treatment, Research Report CORR 91-19, University of Waterloo, Sept 1991.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.39.

Vincenzo Librandi, Table of n, a(n) for n = 1..100
F. Chapoton, F. Hivert, J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013.
Frédéric Fauvet, L. Foissy, D. Manchon, Operads of finite posets, arXiv preprint arXiv:1604.08149 [math.CO], 2016.
S. R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
Vladimir Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244 [math.CO], 2012.
R. P. Stanley, Enumeration of posets generated by disjoint unions and ordinal sums, Proc. Amer. Math. Soc. 45 (1974), 295-299
Index entries for reversions of series
Index entries for sequences related to posets

Cf. A048174, A058349, A058350.

Cf. A000112 (unlabeled posets), A001035 (labeled posets), A003430 (unlabeled analog).

with(gfun):
f := series((ln(1+x)-x^2/(1+x)), x, 21):
egf := seriestoseries(f, 'revogf'):
seriestolist(egf, 'Laplace');

lim = 19; Join[{1}, Drop[ CoefficientList[ InverseSeries[ Series[x + 2*(1 - Cosh[x]) , {x, 0, lim}], y] + InverseSeries[ Series[-Log[1 - x] - x^2/(1 - x),{x, 0, lim}], y], y], 2]*Range[2, lim]!] (* Jean-François Alcover, Sep 21 2011, after g.f. *)
m = 17; Rest[CoefficientList[InverseSeries[Series[Log[1+x]-x^2/(1+x), {x, 0, m}], x], x]*Table[k!,{k, 0, m}]](* Jean-François Alcover, Apr 18 2011 *)

h(n,k):=if n=k then 0 else (-1)^(n-k)*binomial(n-k-1,k-1); a(n):=if n=1 then 1 else -sum((k!/n!*stirling1(n,k)+sum(binomial(k,j)*sum((j)!/(i)!*stirling1(i,j)*h(n-i,k-j),i,j,n-k+j),j,1,k-1)+h(n,k))*a(k),k,1,n-1); /* Vladimir Kruchinin, Sep 08 2010 */

x='x+O('x^55);
s=-log(1-x)-x^2/(1-x);
A048174=Vec(serlaplace(serreverse(s)));
t=x+2*(1-cosh(x));
A058349=Vec(serlaplace(serreverse(t)));
A048172=A048174+A058349;  A048172[1]-=1;
A048172 /* Joerg Arndt, Feb 04 2011 */

a(n) = A058349(n) + A048174(n).
a(n) = A058349(n) + A058350(n) (n>=2).
Reference (by Ronald C. Read) gives generating functions.
E.g.f. is reversion of log(1+x)-x^2/(1+x).
a(n)=if n=1 then 1 else -sum((k!/n!*stirling1(n,k)+sum(binomial(k,j)*sum((j)!/(i)!*stirling1(i,j)*h(n-i,k-j),i,j,n-k+j),j,1,k-1)+h(n,k))*a(k),k,1,n-1), h(n,k)=if n=k then 0 else (-1)^(n-k)*binomial(n-k-1,k-1), n>0. - Vladimir Kruchinin, Sep 08 2010
a(n) ~ sqrt((5+3*sqrt(5))/10) * n^(n-1) / (exp(n) * (2 - sqrt(5) + log((1+sqrt(5))/2))^(n-1/2)). - Vaclav Kotesovec, Feb 25 2014

More terms from Joerg Arndt, Feb 04 2011

A342587 Triangle, read by rows: T(n,k) is the number of labeled order relations on n nodes in which the longest chain has k nodes (n>=1, 1<=k<=n).

Original entry on oeis.org

1, 1, 2, 1, 12, 6, 1, 86, 108, 24, 1, 840, 2310, 960, 120, 1, 11642, 65700, 42960, 9000, 720, 1, 227892, 2583126, 2510760, 712320, 90720, 5040, 1, 6285806, 142259628, 199357704, 71310960, 11481120, 987840, 40320, 1, 243593040, 11012710470, 21774014640, 9501062760, 1781015040

Offset: 1

R. J. Mathar and Brendan McKay, Mar 16 2021

Corrects Comtet's table for k=4 and 5 in row n=8.

			Triangle T(n,k) (with n >= 1 and 1 <= k <= n) begins as follows:
  1;
  1,      2;
  1,     12,       6;
  1,     86,     108,      24;
  1,    840,    2310,     960,    120;
  1,  11642,   65700,   42960,   9000,   720;
  1, 227892, 2583126, 2510760, 712320, 90720, 5040;
  ...

Brendan McKay, Table of T(n,k) for n = 1..13
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 60.

Cf. A000142 (diagonal), A001035 (row sums), A055531 (k=2), A055532 (k=3), A055533 (subdiagonal), A055534 (subdiagonal), A081064, A342501 (connected).

A055512 Lattices with n labeled elements.

Original entry on oeis.org

1, 1, 2, 6, 36, 380, 6390, 157962, 5396888, 243179064, 13938711210, 987858368750, 84613071940452, 8597251494954564, 1020353444641839854, 139627532137612581090, 21788453795572514675760, 3840596246648027262079472, 758435490711709577216754642

Offset: 0

Jobst Heitzig (heitzig(AT)math.uni-hannover.de), Jul 03 2000

Sean A. Irvine, Table of n, a(n) for n = 0..19 (terms 0..18 from David Wasserman)
J. Heitzig and J. Reinhold, Counting finite lattices, preprint no. 298, Institut für Mathematik, Universität Hanover, Germany, 1999.
Sean A. Irvine, Java program (github).
J. Heitzig and J. Reinhold, Counting finite lattices, Algebra univers. 48, 43-53 (2002).
D. J. Kleitman and K. J. Winston, The asymptotic number of lattices, in: Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978), Ann. Discrete Math. 6 (1980), 243-249.
Alan Veliz-Cuba and Reinhard Laubenbacher, Dynamics of semilattice networks with strongly connected dependency graph, Automatica (2019) Vol. 99, 167-174.
Index entries for "core" sequences

Cf. A006966, A001035. Main diagonal of A058159.

A340264 T(n, k) = Sum_{j=0..k} binomial(n, k - j)*Stirling2(n - k + j, j). Triangle read by rows, 0 <= k <= n.

Original entry on oeis.org

1, 0, 2, 0, 1, 4, 0, 1, 6, 8, 0, 1, 11, 24, 16, 0, 1, 20, 70, 80, 32, 0, 1, 37, 195, 340, 240, 64, 0, 1, 70, 539, 1330, 1400, 672, 128, 0, 1, 135, 1498, 5033, 7280, 5152, 1792, 256, 0, 1, 264, 4204, 18816, 35826, 34272, 17472, 4608, 512

Offset: 0

Peter Luschny, Jan 08 2021

A006905(n) = Sum_{k=0..n} A001035(k) * T(n, k). - Michael Somos, Jul 18 2021

T(n, k) is the number of idempotent relations R on [n] containing exactly k strongly connected components such that the following conditional statement holds for all x, y in [n]: If x, y are in distinct strongly connected components of R then (x, y) is not in R. - Geoffrey Critzer, Jan 10 2024

			[0] 1;
[1] 0, 2;
[2] 0, 1,   4;
[3] 0, 1,   6,    8;
[4] 0, 1,  11,   24,    16;
[5] 0, 1,  20,   70,    80,    32;
[6] 0, 1,  37,  195,   340,   240,    64;
[7] 0, 1,  70,  539,  1330,  1400,   672,   128;
[8] 0, 1, 135, 1498,  5033,  7280,  5152,  1792,  256;
[9] 0, 1, 264, 4204, 18816, 35826, 34272, 17472, 4608, 512;

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Štefan Schwarz, On idempotent binary relations on a finite set, Czechoslovak Mathematical Journal, Vol. 20 (1970), No. 4, 696-702.
Eric Weisstein's World of Mathematics, Bell Polynomial.

Sum of row(n) is A000110(n+1).
Sum of row(n) - 2^n is A058681(n).
Alternating sum of row(n) is A109747(n).
Cf. A001035, A006905, A137375, A186081, A121337.

egf := exp(t*(exp(-x) - x - 1));
ser := series(egf, x, 22):
p := n -> coeff(ser, x, n);
seq(seq((-1)^n*n!*coeff(p(n), t, k), k=0..n), n = 0..10);
# Alternative:
T := (n, k) -> add(binomial(n, k - j)*Stirling2(n - k + j, j), j=0..k):
seq(seq(T(n, k), k = 0..n), n=0..9); # Peter Luschny, Feb 09 2021

T[ n_, k_] := Sum[ Binomial[n, k-j] StirlingS2[n-k+j, j], {j, 0 ,k}]; (* Michael Somos, Jul 18 2021 *)

T(n, k) = sum(j=0, k, binomial(n, j)*stirling(n-j, k-j, 2)); /* Michael Somos, Jul 18 2021 */

T(n, k) = (-1)^n * n! * [t^k] [x^n] exp(t*(exp(-x) - x - 1)).

n-th row polynomial R(n,x) = exp(-x)*Sum_{k >= 0} (x + k)^n * x^k/k! = Sum_{k = 0..n} binomial(n,k)*Bell(k,x)*x^(n-k), where Bell(n,x) denotes the n-th Bell polynomial. - Peter Bala, Jan 13 2022

New name from Peter Luschny, Feb 09 2021

A085628 Number of antisymmetric transitive binary relations on n labeled points.

Original entry on oeis.org

1, 2, 12, 152, 3504, 135392, 8321472, 784621952, 110521185024, 22789653765632, 6769730814753792, 2859584874712881152, 1699286839524775931904, 1407801166901961190203392, 1613567168628788544015286272, 2541721059997800475952740401152, 5470980000021882982488097199161344

Offset: 0

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

nonn

Jean-François Alcover, Table of n, a(n) for n = 0..18
G. Pfeiffer, Counting Transitive Relations, preprint, 2004.

Cf. A079265 (unlabeled antisymmetric transitive relations), A001035 (labeled partial orders), A000798 (labeled reflexive transitive relations), A006905 (labeled transitive relations).

A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]];
a[n_] := 2^n A001035[[n + 1]];
a /@ Range[0, 18] (* Jean-François Alcover, Jan 01 2020 *)

a(n) = 2^n * A001035(n) = A000079(n) * A001035(n)

E.g.f.: A(2*x) where A(x) is the e.g.f. for A001035. - Geoffrey Critzer, Jul 28 2014

2 more terms from Charles R Greathouse IV, Aug 31 2006

A003425 n! times number of posets with n elements.

Original entry on oeis.org

1, 1, 6, 114, 5256, 507720, 93616560, 30894489360, 17407086641280, 16152167106391680, 23990233574783750400, 55735096448700749203200, 198720975339675515386598400, 1070118060127292955589511500800, 8585695098723146508385537345689600, 101432601341702692223559539854263552000

Offset: 0

N. J. A. Sloane

nonn

a(n) is the number of nonsingular elements in the semigroup B_n of all binary relations on [n]. A relation A in B_n is nonsingular iff it is regular and row rank(A) = column rank(A) = n. - Geoffrey Critzer, May 22 2022

K. K.-H. Butler, A Moore-Penrose inverse for Boolean relation matrices, pp. 18-28 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974.
K. K.-H. Butler, The Number of Partially Ordered Sets, Journal of Combinatorial Theory (B) 13, 276-289 (1972).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Index entries for sequences related to posets

Cf. A000142, A001035.

a(n) = A000142(n) * A001035(n).

A046908 Number of irreducible posets with n labeled points.

Original entry on oeis.org

1, 1, 1, 7, 97, 2251, 80821, 4305127, 332273257, 36630174931, 5711638291981, 1249898984911567, 381230073532620577, 161042140788424003291, 93667063572594041040421, 74610767840852891620692727, 80997478506602342803118178457, 119313601058907927882431190269731, 237541348427311374857037021264415741

Offset: 0

John A. Wright

nonn

J. A. Wright, There are 718 6-point topologies, quasi-orderings and transgraphs, Notices Amer. Math. Soc., 17 (1970), p. 646, Abstract #70T-A106.

G. Brinkmann, B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179 (Table III, up to 18 points)
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences
Index entries for sequences related to posets

Cf. A046907.

A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]]; lg = Length[A001035];
B[x_] = Sum[A001035[[n + 1]] x^n/n!, {n, 0, lg - 1}];
A[x_] = 2 - 1/B[x];
CoefficientList[A[x] + O[x]^lg, x]*Range[0, lg - 1]! (* Jean-François Alcover, Jan 01 2020 *)

E.g.f.: A(x) = 2-1/B(x), where B(x) is e.g.f. of A001035. - Vladeta Jovovic, Jan 10 2006

More terms from Vladeta Jovovic, Jan 10 2006

a(16)-a(18) from A001035 by Jean-François Alcover, Jan 01 2020

A280202 Number of topologies on an n-set X such that for all x in X there is a y in X such that x and y are topologically indistinguishable.

Original entry on oeis.org

1, 0, 1, 1, 10, 31, 361, 2164, 32663, 313121, 6199024, 86219497, 2225685925, 42396094690, 1414152064833, 35520966967269, 1517860883350266, 48936884016265947, 2659543345912283917, 107827798819822505332, 7409614386025588874195, 371626299919138199117981

Offset: 0

Geoffrey Critzer, Dec 28 2016

nonn

Equivalently a(n) is the number of topologies on an n-set X such that for all x in X there is a y in X such that x and y have exactly the same neighborhoods.

			a(4) = 10 because letting X = {a,b,c,d} we have the trivial topology; {{},{b,c},{a,d},X} * 3; and {{},{a,b},X} *6.

Pontus von Brömssen, Table of n, a(n) for n = 0..37
Wikipedia, Topological indistinguishability.

Column k=0 of A280192.

Cf. A001035, A008299.

E.g.f.: A(exp(x) - 1 - x) where A(x) is the e.g.f. for A001035.

a(n) = Sum_{k=0..floor(n/2)} A008299(n,k)*A001035(k).

a(19)-a(21) from Pontus von Brömssen, Apr 05 2023

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

A124776 Number of labeled partially ordered sets associated with compositions in standard order.

Original entry on oeis.org

1, 1, 1, 2, 1, 9, 3, 6, 1, 28, 54, 60, 4, 36, 12, 24

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

The k-th term of the composition is the number of objects with rank k. The rank of an object is one more than the maximum rank of any smaller object in the ordering (1 for a minimal element), or equivalently the size of the largest chain of which the object is the maximal element.

			Composition number 11 is 2,1,1; there are 3 partial orders
associated with this (shown below); these can be labeled respectively
in 12, 24 and 24 ways, so a(11) = 12+24+24 = 60.
..O..*O..*..O
..|..*|..*./|
..O..*O..*O.|
./.\.*|..*|.|
O...O*O.O*O.O
The table starts:
1
1
1 2
1 9 3 6

Cf. A066099, A124775, A124777, A011782 (row lengths), A001035 (row sums).

cp's OEIS Frontend

A048172 Number of labeled series-parallel graphs with n edges.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A342587 Triangle, read by rows: T(n,k) is the number of labeled order relations on n nodes in which the longest chain has k nodes (n>=1, 1<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A055512 Lattices with n labeled elements.

Views

Author

Keywords

Links

Crossrefs

A340264 T(n, k) = Sum_{j=0..k} binomial(n, k - j)*Stirling2(n - k + j, j). Triangle read by rows, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A085628 Number of antisymmetric transitive binary relations on n labeled points.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A003425 n! times number of posets with n elements.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A046908 Number of irreducible posets with n labeled points.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A280202 Number of topologies on an n-set X such that for all x in X there is a y in X such that x and y are topologically indistinguishable.

Views

Author

Keywords

Comments

Examples