A001035 -id:A001035 - cp's OEIS frontend

A369799 Number of binary relations R on [n] such that q(R) is a quasi-order and s(R) is a strict partial order (where q(R) and s(R) are defined below).

1, 2, 13, 237, 11590, 1431913, 424559959, 292150780260, 456213083587511, 1589279411184268465, 12188163803127032036308, 203538148644721100472292979, 7336995548182992341725851094195, 566597426371900580541745092349604750, 93154354372753215966288131247384428212545, 32423220989898980232206367503220063835343283713

Offset: 0

Geoffrey Critzer, Feb 01 2024

nonn

For a relation R on [n], let E = domain(R intersect R^(-1)) and let F = [n]\E. Then q(R) := R intersect E X E and let s(R) := R intersect F X F.

E. Norris, The structure of an idempotent relation, Semigroup Forum, Vol 18 (1979), 319-329.

Cf. A369778, A369776, A001035, A000798.

nn = 18; posets =Select[Import["https://oeis.org/A001035/b001035.txt", "Table"],
   Length@# == 2 &][[All, 2]]; p[x_] := Total[posets Table[x^i/i!, {i, 0, 18}]]; Map[Total, (Map[Select[#, # > 0 &] &,Table[n!, {n, 0, nn}] CoefficientList[
      Series[ p[Exp[ y  x] - 1]*p[ x], {x, 0, nn}], {x, y}]])*
  Table[Table[3^(k (n - k)), {k, 0, n}], {n, 0, nn}]]

a(n) = Sum_{k=0..n} A369776(n,k) * 3^(k*(n-k)).

A046906 Number of connected irreducible posets with n labeled points.

Original entry on oeis.org

1, 1, 0, 0, 24, 1080, 52440, 3281880, 277953144, 32418855000, 5239070305080, 1173944480658840, 363936227764858584, 155521768202208047640, 91218870039317505477720, 73113879800794757415243480, 79743817918540500914682249144, 117883366412734188786535902826200, 235329353612778837110901775412557560

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.

S. R. Finch, Series-parallel networks
S. R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences
Index entries for sequences related to posets

A003431 gives isomorphism classes of these posets.

nn = 18; A[x_] := Total[Cases[Import["https://oeis.org/A001035/b001035.txt",
      "Table"], {, }][[All, 2]]*Table[x^(i - 1)/(i - 1)!, {i, 1, 19}]];
Range[0, nn]! CoefficientList[ Series[(1 + Log[A[x]]) - A[ x] (1 - 1/A[x])^2 , {x, 0, nn}], x] (* Geoffrey Critzer, Jul 09 2022 *)

From Geoffrey Critzer, Jul 09 2022: (Start)
E.g.f.: 1 + log(A(x)) - A(x)(1-1/A(x))^2  where A(x) is the e.g.f. for A001035.
a(n) = A001927(n) - Sum_{k>=2} A354615(n,k). (End)

a(8)-a(18) from Geoffrey Critzer, Jul 09 2022

a(0) changed to 1 by Geoffrey Critzer, Jul 10 2022

A066302 Reduced partially ordered sets (posets) with n labeled elements.

Original entry on oeis.org

1, 1, 1, 7, 75, 1531, 50673, 2613703, 202180723, 22853355895, 3701983130913, 846741042881779, 270316009546766571, 119343586350194910211, 72325998629777739416209, 59798727157327673157936319

Offset: 0

Christian G. Bower, Dec 12 2001

nonn

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 57 (1.4.70).

Index entries for sequences related to posets

E.g.f.: A(x)=B(x/(1+x)) where B(x) is e.g.f. of A001035.

E.g.f.: A(x)=exp(B(x)) where B(x) is e.g.f. of A066303.

A173311 a(n) is the number of regular D classes in the semigroup of all binary relations on [n].

Original entry on oeis.org

1, 2, 4, 9, 25, 88, 406, 2451, 19450, 202681, 2769965, 49519392, 1154411138, 34978238590, 1373171398361, 69648249299517, 4552778914494604

Offset: 0

Jonathan Vos Post, Feb 16 2010

Previous name was: Partial sums of A000112.

K. K.-H. Butler and G. Markowsky, The Number of Maximal Subgroups of the Semigroup of Binary Relations, Kyungpook Math. J. Vol 12, June 1972.

Cf. A000112, A000798 (labeled topologies), A001035 (labeled posets), A001930 (unlabeled topologies), A006057, A079263, A079265, A007903.

Cases[Import["https://oeis.org/A000112/b000112.txt", "Table"], {, }][[All, 2]] // Accumulate (* Jean-François Alcover, Jan 01 2020 *)

a(n) = Sum_{i=0..n} A000112(i).

New name from Geoffrey Critzer, May 22 2022

A213430 The number of n X n upper triangular (0,1)-matrices M with all diagonal entries 1 such that M = f(M^2) and sum(row 1) >= sum(row 2) >= ... >= sum(row n-1) >= sum(row n) = 1 and f maps any nonzero entry to 1.

Original entry on oeis.org

1, 2, 6, 26, 159, 1347, 15593, 244173, 5131436

Offset: 1

N. J. A. Sloane, Jun 11 2012

A006455 is equivalent to this sequence without the nonincreasing condition on the row sums. - Petros Hadjicostas, Jul 20 2024

Collected papers of Professor Hansraj Gupta. Edited by R. J. Hans-Gill and Madhu Raka. Ramanujan Mathematical Society Collected Works Series, 3. See pp. 554-564.
Hansraj Gupta, Number of topologies in a finite set, Research Bulletin of the Panjab University, Vol. 19 (1968), p. 240. MR0268836.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

Hansraj Gupta, Number of topologies in a finite set, Research Bulletin of the Panjab University, Vol. 19 (1968), p. 240. MR0268836.
Sean A. Irvine, Java program
Wikipedia, Finite topological space.
zbMATH, Review of Gupta article.

Cf. A000798, A001035, A006455.

a(7) and new name from Petros Hadjicostas, Jul 20 2024

a(8)-a(9) from Sean A. Irvine, Jul 20 2024

A247232 Triangular array read by rows: T(n,k) is the number of pre-orders on an n-set with exactly k connected components in its digraph representation, n>=1, 1<=k<=n.

Original entry on oeis.org

1, 3, 1, 19, 9, 1, 233, 103, 18, 1, 4851, 1735, 325, 30, 1, 158175, 43201, 7320, 785, 45, 1, 7724333, 1567783, 218491, 22960, 1610, 63, 1, 550898367, 82142943, 8856974, 818461, 59570, 2954, 84, 1, 56536880923, 6187176225, 496368181, 37205658, 2518131, 135198, 4998, 108, 1

Offset: 1

Geoffrey Critzer, Nov 27 2014

The Bell transform of A001929(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016

			1;
3,         1;
19,        9,        1;
233,       103,      18,      1;
4851,      1735,     325,     30,     1;
158175,    43201,    7320,    785,    45,    1;
7724333,   1567783,  218491,  22960,  1610,  63,   1;
550898367, 82142943, 8856974, 818461, 59570, 2954, 84, 1;

Column 1 = A001929.

Row sums = A000798.

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

# uses[bell_matrix from A264428]
# Adds a column 1,0,0,0, ... at the left side of the triangle.
topo = oeis('A001929')  # Fetch the data via Internet.
A001929List = topo.first_terms()
A001929 = lambda n: A001929List[n]
bell_matrix(lambda n: A001929(n+1), 10) # Peter Luschny, Jan 18 2016, updated Mar 25 2020

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

A265042 a(n) = the unique number k such that T(p + n) == k mod p for all primes p, where T(n) = A000798(n) = number of topologies on n points.

Original entry on oeis.org

2, 7, 51, 634, 12623

Offset: 0

N. J. A. Sloane, Dec 16 2015

From Altug Alkan, Dec 20 2015: (Start)
From the inequality in the formula section, since A000798(6) = 209527, we have 209527 < a(5) < 419054. The same inequality shows that a(17) has 36 digits (A000798 is currently known only for n <= 18).
If we want to analyze more deeply,
A000798(p + 5) == a(5) mod p for all primes p.
A000798(7) == a(5) mod 2, that is, 9535241 == a(5) mod 2. So a(5) mod 2 == 1.
A000798(8) == a(5) mod 3, that is, 642779354 == a(5) mod 3. So a(5) mod 3 == 2.
A000798(10) == a(5) mod 5, that is, 8977053873043 == a(5) mod 5. So a(5) mod 5 == 3.
A000798(12) == a(5) mod 7, that is, 519355571065774021 == a(5) mod 7. So a(5) mod 7 == 5.
A000798(16) == a(5) mod 11, that is, 93411113411710039565210494095 == a(5) mod 11. So a(5) mod 11 == 5.
A000798(18) == a(5) mod 13, that is, 261492535743634374805066126901117203 == a(5) mod 13. So a(5) mod 13 == 2.
In conclusion, a(5) is a number of the form 2*3*5*7*11*13*n - 2767, that is, 30030*n - 2767. Moreover we know that 209527 < a(5) < 419054. So a(5) is one of these numbers: 237473, 267503, 297533, 327563, 357593, 387623, 417653. If we take into consideration the first four inequalities, which are 4 < 7 < 8, 29 < 51 < 58, 355 < 634 < 710, 6942 < 12623 < 13884, then 387623 seems a strong candidate for a(5) because of relevant proportions in inequalities.
(End)

			From _Altug Alkan_, Dec 17 2015: (Start)
A000798(p^k) == k+1 mod p for all primes p. If k=1, A000798(p^1) == 2 mod p, that is, A000798(p) == 2 mod p. So a(0) = 2.
a(1) = 7 because A000798(p + 1) == 7 mod p for all primes p.
(End)

M. Y. Kizmaz, On The Number Of Topologies On A Finite Set, arXiv preprint arXiv:1503.08359 [math.NT], 2015.

Cf. A000798, A001035.

A000798(n+1) < a(n) < 2*A000798(n+1), for n > 0. - Altug Alkan, Dec 17 2015

a(0) = 2 prepended by Altug Alkan, Dec 17 2015

A281547 Total number of subsets of X that are both open and closed summed over all distinct topological spaces X that can be placed on an n-set.

Original entry on oeis.org

1, 2, 10, 82, 1038, 19754, 561778, 23890766, 1516425978, 142478603490, 19560464078774, 3868751287074546, 1088233853378616578, 430599111941369628326, 237480490462200909980594, 181131722604060126010422898, 189780362331001773747253412782, 271553393666987988551182068682458, 527932854364810523962111033565618786

Offset: 0

Geoffrey Critzer, Jan 23 2017

nonn

			a(2) = 10.  Let X = {a,b}.  There are four distinct topologies (A000798) that can be placed on X: {{},X}  {{},{a},X}  {{}, {b},X}  {{},{a},{b},X}.  These topologies have 2 + 2 + 2 + 4 sets respectively that are both open and closed.

Wikipedia, Clopen set.

Cf. A000798, A001035, A247232.

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

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

a(n) = Sum_{k=1..n} A247232(n,k)*2^k.

A343882 Triangular array read by rows: T(n,k) is the number of transitive relations on n labeled nodes with exactly k connected components.

Original entry on oeis.org

1, 0, 2, 0, 9, 4, 0, 109, 54, 8, 0, 2647, 1115, 216, 16, 0, 110481, 36280, 6790, 720, 32, 0, 7291543, 1801927, 287475, 32020, 2160, 64, 0, 726434549, 133060816, 16873619, 1718290, 129080, 6048, 128, 0, 106312974249, 14380028959, 1387285830, 118346473, 8584240, 467488, 16128, 256

Offset: 0

Geoffrey Critzer, May 02 2021

T(n,n) = 2^n since each node is reflexive or not.

			Triangular array T(n,k) begins:
  1;
  0,      2;
  0,      9,     4;
  0,    109,    54,    8;
  0,   2647,  1115,  216,  16;
  0, 110481, 36280, 6790, 720, 32;
  ...

Geoffrey Critzer, Finite Topologies

Cf. A245731 (column k=1), A006905 (row sums), A001035.

A[x_] := Total[Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]]* Table[x^(i - 1)/(i - 1)!, {i, 1, 19}]]; nn = 10;
Range[0, nn]! CoefficientList[ Series[Exp[y Log[A[ x + Exp[ x] - 1]]], {x, 0, nn}], {x,y}] // Grid;Table[Take[(Range[0, nn]! CoefficientList[Series[Exp[y Log[A[ x + Exp[ x] - 1]]], {x, 0, nn}], {x, y}])[[i, All]], i], {i, 1, nn}] // Grid
  (* Import function in code after Jean-François Alcover *)

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

A352399 Triangular array read by rows: T(n,k) is the number of partial order relations on [n] that have exactly k components, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 12, 6, 1, 0, 146, 60, 12, 1, 0, 3060, 970, 180, 20, 1, 0, 101642, 24180, 3750, 420, 30, 1, 0, 5106612, 901334, 110040, 10990, 840, 42, 1, 0, 377403266, 49347228, 4567976, 376320, 27020, 1512, 56, 1, 0, 40299722580, 3923052354, 269812620, 17322648, 1071000, 58716, 2520, 72, 1

Offset: 0

Geoffrey Critzer, Jul 05 2022

			Triangle T(n,k) begins:
  1;
  0,    1;
  0,    2,   1;
  0,   12,   6,   1;
  0,  146,  60,  12,  1;
  0, 3060, 970, 180, 20, 1;
  ...

Cf. A001927 (column 1), A001035 (row sums), A046908.

nn = 8; A[x_] := Total[Cases[Import["https://oeis.org/A001035/b001035.txt",
      "Table"], {, }][[All, 2]]* Table[x^(i - 1)/(i - 1)!, {i, 1, 19}]];
Table[Take[(Range[0, nn]! CoefficientList[Series[A[x]^y, {x, 0, nn}], {x, y}])[[i]], i], {i, 1, nn}] // Grid

E.g.f.: A(x)^y where A(x) is the e.g.f. for A001035.

cp's OEIS Frontend

A369799 Number of binary relations R on [n] such that q(R) is a quasi-order and s(R) is a strict partial order (where q(R) and s(R) are defined below).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A046906 Number of connected irreducible posets with n labeled points.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A066302 Reduced partially ordered sets (posets) with n labeled elements.

Views

Author

Keywords

References

Links

Formula

A173311 a(n) is the number of regular D classes in the semigroup of all binary relations on [n].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A213430 The number of n X n upper triangular (0,1)-matrices M with all diagonal entries 1 such that M = f(M^2) and sum(row 1) >= sum(row 2) >= ... >= sum(row n-1) >= sum(row n) = 1 and f maps any nonzero entry to 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A247232 Triangular array read by rows: T(n,k) is the number of pre-orders on an n-set with exactly k connected components in its digraph representation, n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Sage

Formula

A265042 a(n) = the unique number k such that T(p + n) == k mod p for all primes p, where T(n) = A000798(n) = number of topologies on n points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A281547 Total number of subsets of X that are both open and closed summed over all distinct topological spaces X that can be placed on an n-set.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula