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

Author

Geoffrey Critzer, Feb 24 2023

Keywords

• nonn

Comments

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

Links

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

Crossrefs

Cf. A360743, A001831, A121337, A002031.

Programs

Mathematica

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]

Formula

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.