A006905 -id:A006905 - cp's OEIS frontend

A349919 Number of transitive relations on an n-set with exactly two ordered pairs.

0, 0, 5, 27, 90, 230, 495, 945, 1652, 2700, 4185, 6215, 8910, 12402, 16835, 22365, 29160, 37400, 47277, 58995, 72770, 88830, 107415, 128777, 153180, 180900, 212225, 247455, 286902, 330890, 379755, 433845, 493520, 559152, 631125, 709835, 795690, 889110, 990527, 1100385, 1219140, 1347260, 1485225, 1633527, 1792670

Offset: 0

Firdous Ahmad Mala, Dec 05 2021

			a(2) = 5. The five relations on a 2-set are {(1,1),(1,2)}, {(1,1),(2,1)}, {(1,1),(2,2)}, {(1,2),(2,2)} and {(2,1),(2,2)}.

Firdous Ahmad Mala, Counting Transitive Relations with Two Ordered Pairs, Journal of Applied Mathematics and Computation, 5(4), 247-251.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A006905, A336535, A349927.

This is a diagonal of the array A285192.

LinearRecurrence[{5,-10,10,-5,1},{0,0,5,27,90},50] (* Harvey P. Dale, Oct 23 2022 *)

a(n) = 5*C(n,2) + 12*C(n,3) + 12*C(n,4).
a(n) = (1/2)*(n^4 - 2*n^3 + 4*n^2 - 3*n).
a(n) = A336535(n) - 1.
From Elmo R. Oliveira, Aug 26 2025: (Start)
G.f.: x^2*(5 + 2*x + 5*x^2)/(1 - x)^5.
E.g.f.: x^2*(5 + 4*x + x^2)*exp(x)/2.
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5). (End)

A245731 Number of connected labeled transitive relations on an n-set.

Original entry on oeis.org

1, 2, 9, 109, 2647, 110481, 7291543, 726434549, 106312974249, 22465350835849, 6771847676632679, 2883916106465622053, 1720792953946798909927, 1427968172285571102335605, 1637002867699829205840095585, 2577011453377960519672777065693, 5541005747990556022043234479371823, 16195114271558690956785525865003941945, 64068293759315414337050896928055465961863

Offset: 0

Geoffrey Critzer, Jul 30 2014

nonn

			a(2) = 9. There are 13 transitive relations on the set {1,2}. Four of these are not connected: {}, {(1,1)}, {(2,2)}, {(1,1),(2,2)}. 13-4=9.

Cf. A001035, A006905.

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

A245767 Triangular array read by rows: T(n,k) is the number of transitive relations on {1,2,...,n} that have exactly k reflexive points, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 3, 6, 4, 19, 57, 66, 29, 219, 876, 1428, 1116, 355, 4231, 21155, 44500, 49070, 28405, 6942, 130023, 780138, 2013810, 2858700, 2354415, 1068576, 209527, 6129859, 42909013, 131457522, 228345565, 242894155, 158322528, 58628647, 9535241

Offset: 0

Geoffrey Critzer, Jul 31 2014

Row sums give A006905.
Column k=0 is A001035.
T(n,n) = A000798(n).

			T(2,1) = 6 because we have: {(1,1)}, {(2,2)}, {(1,1),(1,2)}, {(1,1),(2,1)}, {(2,2),(1,2)}, {(2,2),(2,1)}.
Triangle T(n,k) begins:
       1;
       1,      1;
       3,      6,       4;
      19,     57,      66,      29;
     219,    876,    1428,    1116,     355;
    4231,  21155,   44500,   49070,   28405,    6942;
  130023, 780138, 2013810, 2858700, 2354415, 1068576, 209527;
  ...

Alois P. Heinz, Rows n = 0..18, flattened

Cf. A000798, A001035, A006905.

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[#, y]& /@ (CoefficientList[A[x + Exp[y*x]-1] + O[x]^lg, x]* Range[0, lg-1]!) // Flatten (* Jean-François Alcover, Jan 01 2020 *)

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

A280192 Triangle read by rows: T(n,k) = number of topologies on an n-set X such that there are exactly k elements in X that are topologically distinguishable, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 1, 0, 3, 1, 9, 0, 19, 10, 12, 114, 0, 219, 31, 300, 190, 2190, 0, 4231, 361, 1158, 10140, 4380, 63465, 0, 130023, 2164, 26341, 46389, 451920, 148085, 2730483, 0, 6129859, 32663, 192496, 1930852, 2381624, 27601000, 7281288, 171636052, 0, 431723379

Offset: 0

Geoffrey Critzer, Dec 28 2016

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

Equivalently, T(n,k) is the number of labeled quasi-orders R on [n] with exactly k singletons in the equivalence relation R intersect R^(-1), cf. Schein link. - Geoffrey Critzer, Apr 18 2023

			Triangle begins:
     1;
     0,     1;
     1,     0,     3;
     1,     9,     0,     19;
    10,    12,   114,      0,    219;
    31,   300,   190,   2190,      0,    4231;
   361,  1158, 10140,   4380,  63465,       0, 130023;
  2164, 26341, 46389, 451920, 148085, 2730483,      0, 6129859;
  ...

Alois P. Heinz, Rows n = 0..18, flattened
B. M. Schein, A construction for idempotent binary relations, Proc. Japan Acad., Vol. 46, No. 3 (1970), pp. 246-247.
Wikipedia, Topological indistinguishability.

Right border gives A001035.
Row sums give A000798.
Column k=0 gives A280202.
Cf. A006905.

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[#, y]& /@ (CoefficientList[A[Exp[x] - 1 - x + y*x] + O[x]^lg, x]*Range[0, lg - 1]!) // Flatten (* Jean-François Alcover, Jan 01 2020 *)

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

Sum_{k=0..n} T(n,k)*2^k = A006905(n). - Geoffrey Critzer, Apr 18 2023

A349849 Number of transitive relations on an n-set with exactly four ordered pairs.

Original entry on oeis.org

0, 0, 1, 45, 549, 3755, 18120, 69006, 220710, 616554, 1545435, 3544915, 7552611, 15119325, 28699034, 52032540, 90643260, 152465316, 248625765, 394404489, 610396945, 923906655, 1370595996, 1996425530, 2859913794, 4034751150, 5612802975, 7707539151, 10457928495

Offset: 0

Firdous Ahmad Mala, Dec 06 2021

			a(2) = binomial(2,2) = 1. The only transitive relation with four ordered pairs on the 2-set {1,2} is {(1,1),(1,2),(2,1),(2,2)}.

Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Cf. A349919, A349927, A006905.

a(n) = C(n,2) + 42*C(n,3) + 375*C(n,4) + 1450*C(n,5) + 2940*C(n,6) + 3360*C(n,7) + 1680*C(n,8).

a(n) = (1/24)*(n^8 - 12*n^7 + 84*n^6 - 340*n^5 + 814*n^4 - 1130*n^3 + 829*n^2 - 246*n).

A366194 Number of limit dominating binary relations on [n].

Original entry on oeis.org

1, 2, 13, 177, 4486

Offset: 0

Geoffrey Critzer, Oct 03 2023

A relation R is limit dominating iff R converges to a single limit L (A365534) and R contains L.  See Gregory, Kirkland, and Pullman.
A convergent relation R is limit dominating iff the following implication holds for all x,y in [n].  If there is a cyclic traverse from x to y in G(R) then (x,y) is in R, where G(R) is the directed graph with loops associated to R.
A relation R is limit dominating iff it converges to L, the biggest dense relation (A355730) contained in R.  In which case L is the intersection of R^i for all i>=1. - Geoffrey Critzer, Dec 03 2023

			Every idempotent relation (A121337) is limit dominating.
Every transitive relation (A006905) is limit dominating.
Every nilpotent relation (A003024) is limit dominating.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

Cf. A365534, A121337, A006905, A003024, A366722.

A366722 Number of limit dominated binary relations on [n].

Original entry on oeis.org

1, 2, 13, 399, 55894

Offset: 0

Geoffrey Critzer, Oct 17 2023

A relation R is limit dominated iff R converges to a single limit L (A365534) and R is contained in L.
A convergent relation R is limit dominated iff the following implication holds for all x,y in [n].  If (x,y) is in R then there is a cyclic traverse from x to y in G(R), where G(R) is the directed graph with loops associated to R.
A relation R is limit dominated iff it converges to L, the smallest transitive relation (A006905) containing R. In which case, L is the union of R^i for all i >= 1. - Geoffrey Critzer, Dec 03 2023

			Every idempotent relation (A121337) is limit dominated.
Every dense relation (A355730) is limit dominated.
Every primitive relation (A070322) is limit dominated.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, pp. 105-117.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

Cf. A365534, A121337, A006905, A366194, A355730, A070322.

A369776 Triangular array read by rows. T(n,k) is the number of inequivalent (as defined below) transitive binary relations R on [n] such that |domain(R intersect R^(-1))| = k, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 3, 2, 4, 19, 9, 12, 29, 219, 76, 72, 116, 355, 4231, 1095, 760, 870, 1775, 6942, 130023, 25386, 13140, 11020, 15975, 41652, 209527, 6129859, 910161, 355404, 222285, 236075, 437346, 1466689, 9535241, 431723379, 49038872, 14562576, 6871144, 5442150, 7386288, 17600268, 76281928, 642779354

Offset: 0

Geoffrey Critzer, Jan 31 2024

For a transitive relation R on [n], let E = domain(R intersect R^(-1)) and let F = [n]\E. Let q(R) = R intersect E X E and let s(R) = R intersect F X F. Let ~ be the equivalence relation on the set of transitive binary relations on [n] defined by: R_1 ~ R_2 iff q(R_1) = q(R_2) and s(R_1) = s(R_2). Here, two transitive relations are inequivalent if they are in distinct equivalence classes under ~. q(R) is a quasi-order (A000798) and s(R) is a strict partial order (A001035). The relation q(R) union s(R) may be taken as its class representative. See Norris link.

			Triangle begins
    1;
    1,    1;
    3,    2,   4;
   19,    9,  12,  29;
  219,   76,  72, 116,  355;
 4231, 1095, 760, 870, 1775, 6942;
 ...

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

Cf. A001035 (column k=0), A000798 (main diagonal), A006059 (column k=1), A369778 (row sums), A006905, A369799.

nn = 8; 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[Select[#, # > 0 &] &,Table[n!, {n, 0, nn}] CoefficientList[Series[ p[Exp[ y  x] - 1]*p[ x], {x, 0, nn}], {x, y}]] // Grid

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

A369778 Number of inequivalent (as defined below) transitive binary relations on [n].

Original entry on oeis.org

1, 2, 9, 69, 838, 15673, 446723, 19293060, 1251685959, 120386313553, 16900121126060, 3411142115103803, 977085613480027515, 392874276568326733742, 219743920204264577507581, 169664195991510052549565897, 179646979835553234783655867894, 259379781267410563698300438118605, 508142540645401577520522108019282903

Offset: 0

Geoffrey Critzer, Jan 31 2024

nonn

For a transitive relation R on [n], let E = domain(R intersect R^(-1)) and let F = [n]\E.  Let q(R) = R intersect E X E and let s(R) = R intersect F X F.  Let ~ be the equivalence relation on the set of transitive binary relations on [n] defined by: R_1 ~ R_2 iff q(R_1) = q(R_2) and s(R_1) = s(R_2).  Here, two transitive relations are inequivalent if they are in distinct equivalence classes under ~.  q(R) is a quasi-order (A000798) and s(R) is a strict partial order (A001035). See Norris link.
Equivalently, with E,F as defined above, a(n) is the number of transitive relations R on [n] such that if (x,y) is in R then x and y are both in E or x and y are both in F.
Conjecture:  lim_{n->oo} a(n)/A001035(n) = 2.

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

Cf. A000798, A001035, A006905, A369799,

Row sums of A369776.

nn = 16; 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}]];
Table[n!, {n, 0, nn}] CoefficientList[Series[ p[Exp[   x] - 1]*p[ x], {x, 0, nn}], x]

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

A341471 Number of antisymmetric, antitransitive relations on n labeled nodes.

Original entry on oeis.org

1, 1, 3, 21, 317, 9735, 583907, 66226033, 13837055261

Offset: 0

Peter Kagey, Feb 13 2021

An antisymmetric, antitransitive relation is one where xRy implies "not yRx" and xRy and yRz implies "not xRz". All antitransitive relations are irreflexive, so this sequence is counting "anti-equivalence relations".
a(n) < A047656(n).
Idea thanks to Richard Arratia, who saw, verbatim in an editorial, "False equivalences? There were almost too many to count."

			There are a(3) = 21 antisymmetric, antitransitive relations on n = 3 letters:
  - the empty relation,
  - all six relations containing only a single pair (x,y) (with x != y),
  - all twelve relations {(x1,y1), (x2,y2)} containing exactly two ordered pairs, neither of which is (y1,x1) or (y2,x2), and
  - two relations containing three ordered pairs: {(1,2), (2,3), (3,1)} and {(1,3), (3,2), (2,1)}.

Wikipedia, Binary relation

Number of relations on labeled nodes: A000110 (equivalence), A001831 (transitive and antitransitive), A002416 (unrestricted), A006125 (symmetric), A006905 (transitive), A047656 (reflexive and antisymmetric), A083667 (antisymmetric), A341473 (antitransitive).

a(6)-a(8) from Bert Dobbelaere, Feb 27 2021

cp's OEIS Frontend

A349919 Number of transitive relations on an n-set with exactly two ordered pairs.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A245731 Number of connected labeled transitive relations on an n-set.

Views

Author

Keywords

Examples

Crossrefs

Formula

A245767 Triangular array read by rows: T(n,k) is the number of transitive relations on {1,2,...,n} that have exactly k reflexive points, n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A280192 Triangle read by rows: T(n,k) = number of topologies on an n-set X such that there are exactly k elements in X that are topologically distinguishable, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A349849 Number of transitive relations on an n-set with exactly four ordered pairs.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A366194 Number of limit dominating binary relations on [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A366722 Number of limit dominated binary relations on [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A369776 Triangular array read by rows. T(n,k) is the number of inequivalent (as defined below) transitive binary relations R on [n] such that |domain(R intersect R^(-1))| = k, n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A369778 Number of inequivalent (as defined below) transitive binary relations on [n].

Views

Author

Keywords

Comments