A360743 Number of idempotent binary relation matrices E on [n] such that E contains an identity matrix of order n-1 and (E - I_n)^2 = 0.

1, 2, 9, 52, 435, 5046, 81501, 1823144, 56572263, 2435930410, 145888123953, 12173595399516, 1418664206897691, 231298954644947294, 52860840028599821445, 16957903154151836822608, 7647128139328190245443279, 4852236755345544324027858258

Offset: 0

Author

Geoffrey Critzer, Feb 18 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.

If an idempotent Boolean relation matrix E contains an identity matrix of order n-1 and (E-I_n)^2 = 0 then E has no proper power primitive. The converse is not true for n>=4. Consider {{1,0,1,0}, {0,1,0,1}, {0,0,0,0}, {0,0,0,0}}. The converse is erroneously stated and proved in Rosenblatt, Theorem 4.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..113
• 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. A001831, A121337.

Programs

Maple

a:= n-> (n+1)*add(binomial(n, k)*(2^k-1)^(n-k), k=0..n):
seq(a(n), n=0..18);  # Alois P. Heinz, Feb 18 2023

Mathematica

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

Formula

a(n) = (n + 1)*A001831(n).

E.g.f.: x*A'(x) + A(x) where A(x) = Sum_{n>=0} x^n/n! exp((2^n-1)*x) is the e.g.f. for A001831.

Extensions

Corrected by Geoffrey Critzer, Feb 24 2023