A365534 Number of convergent Boolean relation matrices on [n].

1, 2, 15, 465, 61068, 32453533, 67904955351

Offset: 0

Author

Geoffrey Critzer, Sep 08 2023

Keywords

• nonn
• more

Comments

A Boolean relation matrix R is convergent iff R^k = R^(k+1) for all sufficiently large k. In other words, iff the period of R is equal to 1. The digraph of R is such that all its maximal cyclic nets are primitive (A070322) iff R is convergent. Cf. Rosenblatt link. Also, R is convergent iff every diagonal block in its Frobenius normal form is either primitive or a 1 X 1 zero matrix, Theorem 1.1 in Gregory, Kirkland and Pullman.

Links

• 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.

Crossrefs

Cf. A070322, A002416.

Formula

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

A070322(n) <= a(n) <= 2^(n^2) = A002416(n).