A006905 -id:A006905 - cp's OEIS frontend

A341473 The number of antitransitive relations on n labeled nodes.

1, 1, 4, 39, 921, 47462, 5205915, 1161039833, 516101770210

Offset: 0

Peter Kagey, Feb 13 2021

A relation is antitransitive if xRy and yRz implies "not xRz". As such, antitransitive relations are always irreflexive.

Wikipedia, Intransitivity.

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

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

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.

A348634 Number of transitive relations on an n-set with exactly five ordered pairs.

Original entry on oeis.org

0, 0, 0, 27, 768, 8771, 63468, 340620, 1470784, 5371002, 17153352, 49075521, 128066400, 309124101, 697874996, 1486830618, 3011414784, 5833686340, 10863883728, 19532496375, 34028554944, 57623258007, 95101946940, 153331834040, 241997811264, 374544148830, 569365964440, 851301035325, 1253479866912, 1819599953913, 2606698902276

Offset: 0

Firdous Ahmad Mala, Dec 13 2021

nonn

			No relation containing exactly five ordered pairs on a 2-element set exists. Thus a(2)=0.
Also, there are 27 transitive relations with exactly five ordered pairs on a 3-set. One such relation is {(1,1),(1,2),(1,3),(2,2),(3,2)} on the 3-set {1,2,3}.

Cf. A349919, A349927, A349849, A006905.

def A348634(n): return n*(n - 2)*(n - 1)*(n*(n*(n*(n*(n*(n*(n - 17) + 167) - 965) + 3481) - 7581) + 9060) - 4608)//120 # Chai Wah Wu, Jan 06 2022

a(n) = 27*C(n,3) + 660*C(n,4) + 5201*C(n,5) + 21822*C(n,6) + 54600*C(n,7) + 84000*C(n,8) + 75600*C(n,9) + 30240*C(n,10).
a(n) = (1/120)*(n^10 - 20*n^9 + 220*n^8 - 1500*n^7 + 6710*n^6 - 19954*n^5 + 38765*n^4 - 46950*n^3 + 31944*n^2 - 9216*n).
a(n) = C(n,3)*(n^7 - 17*n^6 + 167*n^5 - 965*n^4 + 3481*n^3 - 7581*n^2 + 9060*n - 4608)/20. - Chai Wah Wu, Jan 06 2022

a(9) corrected by Georg Fischer, Mar 19 2023

A296105 a(n) is the number of connected transitive relations over n unlabeled nodes.

Original entry on oeis.org

1, 2, 5, 25, 157, 1325, 14358, 199763, 3549001, 80673244, 2352747542, 88240542454, 4261209044877, 264988507673267, 21207485269909946, 2182146922863398203

Offset: 0

Daniele P. Morelli, Dec 04 2017

Inverse Euler transform of A091073. Here "connected" means that it is possible to reach any vertex starting from any other vertex by traversing edges in some direction, i.e., not necessarily in the direction in which the edges point, as in weakly connected digraphs.

			a(2) = 5 because there are five connected transitive relations up to isomorphism: a->b with no loops, a->b with a loop on a, a->b with a loop on b, a->b->a with no loops, and a->b->a with loops on both a and b.

Cf. A091073 (all unlabeled transitive relations). For the labeled case, see A245731 (connected labeled transitive relations) and A006905 (all labeled transitive relations).

A091073 = Cases[Import["https://oeis.org/A091073/b091073.txt", "Table"], {, }][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
{1} ~Join~ EulerInvTransform[A091073 // Rest] (* Jean-François Alcover, Dec 29 2019, updated Mar 17 2020 *)

A345317 Number of transitive but not symmetric relations on an n-set.

Original entry on oeis.org

0, 0, 8, 156, 3942, 154100, 9414312, 878218390, 122207682476, 24890747805972, 7307450298831718, 3053521546328889460, 1797003559223742679800, 1476062693867018935173990, 1679239558149570227773844452, 2628225174143857306613215434524, 5626175867513779058706923151723150

Offset: 0

Firdous Ahmad Mala, Oct 02 2021

nonn

The number of relations on n elements that are symmetric and transitive is the same as the number of equivalence relations on n+1 elements. Consequently, the number of relations that are transitive but not symmetric is obtained by subtracting the terms in the sequence of Bell numbers from that of the sequence of number of labeled transitive relations.

a(n) is even for all n.

			For n=3, a(3) = A006905(3) - A000110(4) = 171 - 15 = 156.

Des MacHale and Peter MacHale, Relations on Sets, The Mathematical Gazette, Vol. 97, No. 539 (July 2013), pp. 224-233 (10 pages).
Firdous Ahmad Mala, Some New Integer Sequences of Transitive Relations, J. Appl. Math. Comp. (2023) Vol. 7, No. 1, 108-111.

Cf. A006905, A000110.

a(n) = A006905(n) - A000110(n+1).

A347914 Number of quasitransitive relations on n labeled nodes.

Original entry on oeis.org

1, 2, 16, 400, 28544, 5531648, 2818499584

Offset: 0

Dave Palfrey, Sep 19 2021

Quasitransitivity is weaker than transitivity.

Wikipedia, Quasitransitive relation

Cf. A006905 (number of transitive relations on n labeled nodes).

A348137 Number of transitive relations involving all the elements of an n-set.

Original entry on oeis.org

1, 1, 10, 137, 3381, 135922, 8546045, 815422505, 115437178060, 23821722677391, 7063938719374373, 2974488705436714248, 1760838176228838354751, 1452937749988032952760937, 1658737103542768935354921618, 2603190753864086778265813466485, 5584324950136613655245377359839793

Offset: 0

Firdous Ahmad Mala, Oct 02 2021

nonn

			a(3) = A006905(3) - 1 - 3 - 30 = 137, where the numbers of transitive relations involving 0,1,2 elements on a 3-set are 1,3,30.

Firdous Ahmad Mala, Some New Integer Sequences of Transitive Relations, J. Appl. Math. Comp. (2023) Vol. 7, No. 1, 108-111.

Cf. A006905.

a(n) = Sum_{k=0..n} (-1)^k*binomial(n,k)*A006905(n-k).

A355783 Triangular array read by rows. T(n,k) is the number of labeled transitive relations on [n] that have exactly k symmetric points.

Original entry on oeis.org

1, 2, 0, 12, 0, 1, 152, 0, 18, 1, 3504, 0, 456, 24, 10, 135392, 0, 17520, 760, 600, 31, 8321472, 0, 1015440, 35040, 40560, 2316, 361, 784621952, 0, 87375456, 2369360, 3615360, 185556, 52682, 2164, 110521185024, 0, 10984707328, 233001216, 441616000, 19052992, 7723408, 384992, 32663

Offset: 0

Geoffrey Critzer, Jul 16 2022

Let R be a binary relation on [n]. Then x in [n] is a symmetric point of R if there is a y in [n] with x != y and both (x,y),(y,x) in R.

			       1,
       2, 0,
      12, 0,     1,
     152, 0,    18,   1,
    3504, 0,   456,  24,  10,
  135392, 0, 17520, 760, 600, 31

Cf. A280202 (main diagonal), A085628 (column k=0), A006905 (row sums).

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

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

cp's OEIS Frontend

A341473 The number of antitransitive relations on n labeled nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A348634 Number of transitive relations on an n-set with exactly five ordered pairs.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python

Formula

Extensions

A296105 a(n) is the number of connected transitive relations over n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A345317 Number of transitive but not symmetric relations on an n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A347914 Number of quasitransitive relations on n labeled nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

A348137 Number of transitive relations involving all the elements of an n-set.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A355783 Triangular array read by rows. T(n,k) is the number of labeled transitive relations on [n] that have exactly k symmetric points.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula