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

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

Offset

0,2

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

Table of n, a(n) for n=0..6.

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.

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

Crossrefs

Cf. A070322, A002416.

Sequence in context: A363834 A013059 A013098 * A158109 A370014 A357856

Adjacent sequences: A365531 A365532 A365533 * A365535 A365536 A365537

Keyword

nonn,more

Author

Geoffrey Critzer, Sep 08 2023

Status

approved