A360743 -id:A360743 - cp's OEIS frontend

A360718 Number of idempotent Boolean relation matrices on [n] that have no proper power primitive.

1, 2, 9, 52, 459, 5526, 91161, 2039024, 62264215, 2618031658, 153147765333, 12544274587956, 1443661355799075, 233590364506712318, 53152637809972391281, 17010099259539378971368, 7660283773351147860024879, 4856904906875123474086041426

Offset: 0

Geoffrey Critzer, Feb 24 2023

nonn

A Boolean relation matrix R is said to be convergent in its powers if in the sequence {R, R^2, R^3, ...} there is an m such that R^m = R^(m+1).
An idempotent Boolean relation matrix E is said to have a proper power primitive iff there is a convergent relation R with limit matrix E where R is not equal to E.
Let P = C_1 + C_2 + ... + C_k + S be a poset with rank(P) <= 1 (A001831) where each C_i is a weakly connected component of size 2 or more and S is a set of isolated points. Let A be a subset of [n] and let E = P - {(x, x): x in A}. Then E is an idempotent relation with no proper power primitive iff A satisfies exactly one of the following conditions:
  i) A is a nonempty subset of domain(E) and A contains at most one point in domain(C_i) for 1 <= i <= k.
  ii) A is a nonempty subset of image(E) and A contains at most one point in image(C_i) for 1 <= i <= k.
  iii) A contains at most one point in S.
The first term in the e.g.f. below counts the number of such relations for which condition i) or ii) is satisfied.  The second term in the e.g.f. counts the number of such relations for which condition iii) is satisfied. - Geoffrey Critzer, Feb 11 2024

David Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research, National Bureau of Standards, Vol 67B No. 4 Oct-Dec 1963.

Cf. A360743, A001831, A121337, A002031.

nn = 17; A[x_] := Sum[x^n/n! Exp[(2^n - 1) x], {n, 0, nn}]; c[x_] := Log[A[x]] - x; Range[0, nn]! CoefficientList[Series[2 (Exp[x D[c[x], x]/2] - 1) Exp[c[x]] Exp[x] + Exp[c[x]] D[x Exp[x], x], {x, 0, nn}], x]

E.g.f.: 2(exp(x * c'(x)/2) - 1) exp(c(x)) exp(x) + exp(c(x))*(x exp(x))' where c(x) is the e.g.f. for A002031.

A370208 Triangular array read by rows. T(n,k) is the number of idempotent binary relations on [n] having no proper power primitive (A360718) with exactly k irreflexive points.

Original entry on oeis.org

1, 1, 1, 3, 6, 13, 39, 87, 348, 24, 841, 4205, 480, 11643, 69858, 9420, 240, 227893, 1595251, 206640, 9240, 6285807, 50286456, 5389552, 299040, 3360, 243593041, 2192337369, 172041408, 9848160, 211680

Offset: 0

Geoffrey Critzer, Feb 11 2024

			 Triangle begins
      1;
      1,       1;
      3,       6;
     13,      39;
     87,     348,     24;
    841,    4205,    480;
  11643,   69858,   9420,  240;
 227893, 1595251, 206640, 9240;
 ...

David Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research, National Bureau of Standards, Vol 67B No. 4 Oct-Dec 1963.

Cf. A360718 (row sums), A001831 (column k=0), A360743 (T(n,0) + T(n,1) ), A151817 (T(2n,n) for n>=2), A002031.

nn = 9; A[x_] := Sum[x^n/n! Exp[(2^n - 1) x], {n, 0, nn}];
c[x_] := Log[A[x]] - x; Map[Select[#, # > 0 &] &,
 Range[0, nn]! CoefficientList[
   Series[2 (Exp[ y x D[c[ x], x]/2] - 1) Exp[c[x]] Exp[ x] +
     Exp[c[ x]] (y x Exp[  x] + Exp[ x]), {x, 0, nn}], {x, y}]]

E.g.f.: 2(exp(y*x*c'(x)/2)-1)*exp(c(x))*exp(x) + exp(c(x))*(y*x*exp(x) + exp(x)) where c(x) is the e.g.f. for A002031.

cp's OEIS Frontend

A360718 Number of idempotent Boolean relation matrices on [n] that have no proper power primitive.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula