A365534 -id:A365534 - cp's OEIS frontend

A366218 Number of convergent binary relations on [n] (A365534) that converge to an equivalence relation (A000110).

1, 1, 4, 149, 26177, 18211032, 47135163595

Offset: 0

Geoffrey Critzer, Oct 04 2023

Equivalently, a(n) is the number of Boolean relation matrices whose Frobenius normal form is such that all the diagonal blocks are primitive (A070322) and all the off diagonal blocks are 0-blocks. See Gregory, Kirkland, Pullman.

The limit of a convergent binary relation R is an equivalence relation iff every vertex and every edge in G(R) is on a cycle, where G(R) is the directed graph with loops associated to R. See Corollary to Theorem 1 in Rosenblatt.

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. A070322, A365534, A000110.

nn = 13; B[n_] := 2^Binomial[n, 2] n!; primitive = Select[Import["https://oeis.org/A070322/b070322.txt", "Table"],
Length@# == 2 &][[All, 2]];pr[x_] := Total[primitive Table[x^i/i!, {i, 0, 6}]];Table[n!, {n, 0, nn}] CoefficientList[Series[Exp[pr[x] - 1], {x, 0, nn}], x]

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

A366252 Number of convergent binary relations on [n] (A365534) that converge to a quasi-order relation (A000798).

Original entry on oeis.org

1, 1, 6, 227, 37617, 23750562, 56091061929

Offset: 0

Geoffrey Critzer, Oct 05 2023

Equivalently, a(n) is the number of convergent Boolean relation matrices whose Frobenius normal form is such that all the diagonal blocks are primitive (A070322).

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.
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

Cf. A070322, A365534, A000798, A366218.

nn = 6; B[n_] := 2^Binomial[n, 2] n!; pr[x_] := Total[primitive Table[x^i/i!, {i, 0, 6}]];ggf[egf_] := Normal[Series[egf, {x, 0, nn}]] /.
 Table[x^i ->x^i/2^Binomial[i, 2], {i, 0, nn}];Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggf[Exp[- (pr[x] - 1)]], {x, 0, nn}], x]

Sum_{n>=0} a_n*x^n/(2^n*binomial(n,2)) = 1/(E(x) @ exp(-(p(x)-1))) where E(x) = Sum_{n>=0} x^n/(2^n*binomial(n,2)), p(x) is the e.g.f. for A070322, and @ is the exponential Hadamard product (see Panafieu and Dovgal).

A334282 Number of properly colored labeled graphs on n nodes so that the color function is surjective onto {c_1,c_2,...,c_k} for some k, 1<=k<=n.

Original entry on oeis.org

1, 1, 5, 73, 2849, 277921, 65067905, 35545840513, 44384640206849, 124697899490480641, 778525887500557625345, 10693248499002776513697793, 320453350845793018626300755969, 20807125028666778079876193487790081, 2909872870574162514727072641529432735745

Offset: 0

Geoffrey Critzer, Apr 21 2020

nonn

Also 1 together with the row sums of A046860.

A binary relation R on [n] is periodic iff there is a d>=2 such that R^d = R. Let A be the class of non-arcless strongly connected periodic relations (A000629). Then a(n) is the number of binary relations on [n] whose strongly connected components are in A. - Geoffrey Critzer, Dec 12 2023

Alois P. Heinz, Table of n, a(n) for n = 0..77

Cf. A046860, A322280, A011266, A361560, A003024, A365534, A365590.

b:= proc(n, k) option remember; `if`([n, k]=[0$2], 1,
      add(binomial(n, r)*2^(r*(n-r))*b(r, k-1), r=0..n-1))
    end:
a:= n-> add(b(n,k), k=0..n):
seq(a(n), n=0..15);  # Alois P. Heinz, Apr 21 2020

nn = 15; e2[x_] := Sum[x^n/(n! 2^Binomial[n, 2]), {n, 0, nn}];
Table[n! 2^Binomial[n, 2], {n, 0, nn}] CoefficientList[Series[1/(1 - (e2[x] - 1)), {x, 0, nn}], x]

Sum_{n>=0} a_n*x^n/(n!*2^C(n,2)) = 1/(2-Sum_{n>=0} x^n/(n!*2^C(n,2))).

A365590 Number of n X n Boolean relation matrices such that each of the diagonal blocks of its Frobenius normal form is either a 1 block or a 0 block.

Original entry on oeis.org

1, 2, 13, 243, 11998, 1477763, 436610299, 300960642300, 474171878424571, 1680899431189662775, 13241419272545722904788, 229482664065433754849099977, 8677282817864146616211588609715, 710901968198799834001047038898570250

Offset: 0

Geoffrey Critzer, Sep 10 2023

nonn

A 1(0) block is such that every entry in the block is 1(0). See Gregory, Kirkland, Pullman for a description of Frobenius normal form.

a(n) is also the number of labeled digraphs (with loops allowed A002416) on [n] such that every strongly connected component is either complete or a single vertex without a loop.

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.
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.

Cf. A355612, A365593, A365534.

nn = 13; B[n_] := n! 2^Binomial[n, 2]; ggf[egf_] := Normal[Series[egf, {x, 0, nn}]] /. Table[x^i -> x^i/2^Binomial[i, 2], {i, 0, nn}]; Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggf[Exp[-(Exp[x] - 1 + x)]], {x, 0, nn}], x]

Sum_{n>=0} a(n)*x^n/(n!*2^binomial(n,2)) = 1/(E(x) @ exp(-(exp(x)-1+x))) where E(x)=Sum_{n>=0} x^n/(n!*2^binomial(n,2)) and @ is the exponential Hadamard product (see Panafieu and Dovgal).

A365593 Number of n X n Boolean relation matrices such that every block of its Frobenius normal form is either a 0 block or a 1 block.

Original entry on oeis.org

1, 2, 13, 219, 9322, 982243, 249233239, 148346645212, 202688186994599, 624913864623500599, 4289324010827093793808, 64841661094150427710360745, 2140002760057211517052090865983, 153082134018816602622335941790247946, 23590554099141037133024176892280338280237

Offset: 0

Geoffrey Critzer, Sep 10 2023

nonn

A 1(0) block is such that every entry in the block is 1(0). If a Boolean relation matrix R is limit dominating then it must be that every block of R is either a 0 block or a 1 block. See Theorem 1.2 in Gregory, Kirkland, and Pullman.

Conjecture: lim_n->inf a(n)/(A003024(n)*2^n) = 1. In other words, almost all of the relations counted by this sequence have n strongly connected components. - Geoffrey Critzer, Sep 30 2023

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.

Cf. A003024, A355612, A365534, A365590, A366141.

nn = 12; d[x_] :=Total[Cases[Import["https://oeis.org/A003024/b003024.txt",
      "Table"], {, }][[All, 2]]*Table[x^(i - 1)/(i - 1)!, {i, 1, 41}]];
Range[0, nn]! CoefficientList[Series[d[Exp[x] - 1 + x], {x, 0, nn}],x]

E.g.f.: D(exp(x)-1+x) where D(x) is the e.g.f. for A003024.

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.

A363834 Number of labeled digraphs (with self loops allowed) on [n] such that every strongly connected component of size at least 2 contains a vertex with a self loop.

Original entry on oeis.org

1, 2, 15, 452, 58023, 31083662, 66296957895, 554842541248592, 18340342731323665263, 2411916363098805776251322, 1266238008719333748929247025455, 2657054767893996575723268008873476172, 22295054304671836968688374028608806896204023

Offset: 0

Geoffrey Critzer, Oct 19 2023

nonn

The sequence gives a good lower bound for the number of convergent binary relations (A365534) which is only known for n <= 6.

			a(2) = 15 because there are 16 labeled digraphs with self loops on [2] and all of them are good except: [1->2,2->1].

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.

Cf. A365534, A070322, A003030.

nn = 12; B[n_] := 2^Binomial[n, 2] n!; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"], Length@# == 2 &][[All, 2]]; sm[x_] :=  Total[Table[2^n - 1, {n, 1, Length[strong]}] strong Table[ x^i/i!, {i, 1, 58}]]; ggf[egf_] := Normal[Series[egf, {x, 0, nn}]] /.
  Table[x^i -> x^i/2^Binomial[i, 2], {i, 0, nn}];Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggf[Exp[-(sm[x] + x)]], {x, 0, nn}], x]

Sum_{n>=0} a(n)*x^n/(n!*2^binomial(n,2)) = 1/(E(x) @ exp(-(sm(x)-1+x))) where E(x) = Sum_{n>=0} x^n/(n!*2^binomial(n,2)), sm(x) = Sum_{n>=0} (2^n-1)*A003030(n)*x^n/n! and @ is the exponential Hadamard product (see Panafieu and Dovgal).

A365547 Triangular array read by rows. T(n,k) is the number of convergent Boolean relation matrices on [n] containing exactly k strongly connected components, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 0, 2, 0, 3, 12, 0, 139, 126, 200, 0, 25575, 17517, 9288, 8688, 0, 18077431, 8457840, 3545350, 1435920, 936992, 0, 47024942643, 14452288791, 4277647665, 1422744780, 485315280, 242016192

Offset: 0

Geoffrey Critzer, Sep 08 2023

			 Triangle begins ...
  1;
  0,        2;
  0,        3,      12;
  0,      139,     126,     200;
  0,    25575,   17517,    9288,    8688;
  0, 18077431, 8457840, 3545350, 1435920, 936992;
  ...

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.
G. Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum, Vol 13 (1977), 253-259.
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.
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 (row sums), A070322, A003024.

nn = 6; B[n_] := n! 2^Binomial[n, 2]; primitive = Select[Import["https://oeis.org/A070322/b070322.txt", "Table"], Length@# == 2 &][[All, 2]]; pr[x_] := Total[primitive Table[x^i/i!, {i, 0, 6}]];
ggf[egf_] := Normal[Series[egf, {x, 0, nn}]] /. Table[x^i -> x^i/2^Binomial[i, 2], {i, 0, nn}];Table[Take[(Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggf[Exp[-(y pr[x] - y + y x)]], {x, 0, nn}], {x, y}])[[i]], i], {i, 1, 7}] // Grid

For n>=2, T(n,1) = A070322(n) and T(n,n) = A003024(n)*2^n.

A369397 Number of binary relations R on [n] such that the (unique) idempotent in {R,R^2,R^3,...} is an equivalence relation.

Original entry on oeis.org

1, 1, 5, 157, 26345, 18218521, 47136254765, 451286947588597, 16264532016440908625, 2253156851039460378774961, 1219026648017155982267265596885, 2601923405098893502520360223043594957, 22040885615442635622424409144799379027505465

Offset: 0

Geoffrey Critzer, Jan 22 2024

nonn

Equivalently, a(n) is the number of binary relations R on [n] such that the Frobenius normal form has no 0-blocks on the diagonal and all off diagonal blocks are 0-blocks.

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.
S. Schwarz, On the semigroup of binary relations on a finite set , Czechoslovak Mathematical Journal, 1970.

Cf. A366866 (binary relations R on [n] such that the (unique) idempotent in {R,R^2,R^3,...} is a quasiorder), A365534, A366218, A365590, A355612, A365593, A366252, A366350, A366218.

nn = 12; strong =Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]]; s[x_] := Total[strong Table[x^i/i!, {i, 1, 58}]];
Table[n!, {n, 0, nn}] CoefficientList[Series[Exp [s[2 x] - x], {x, 0, nn}], x]

E.g.f.: exp(s(2x)-x) where s(x) is the e.g.f. for A003030.

cp's OEIS Frontend

A366218 Number of convergent binary relations on [n] (A365534) that converge to an equivalence relation (A000110).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A366252 Number of convergent binary relations on [n] (A365534) that converge to a quasi-order relation (A000798).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A334282 Number of properly colored labeled graphs on n nodes so that the color function is surjective onto {c_1,c_2,...,c_k} for some k, 1<=k<=n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A365590 Number of n X n Boolean relation matrices such that each of the diagonal blocks of its Frobenius normal form is either a 1 block or a 0 block.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A365593 Number of n X n Boolean relation matrices such that every block of its Frobenius normal form is either a 0 block or a 1 block.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

A363834 Number of labeled digraphs (with self loops allowed) on [n] such that every strongly connected component of size at least 2 contains a vertex with a self loop.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A365547 Triangular array read by rows. T(n,k) is the number of convergent Boolean relation matrices on [n] containing exactly k strongly connected components, n>=0, 0<=k<=n.