A365534 - OEIS

%I #26 Oct 21 2023 06:17:07

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

%N Number of convergent Boolean relation matrices on [n].

%C 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.

%H D. A. Gregory, S. Kirkland, and N. J. Pullman, <a href="https://doi.org/10.1016/0024-3795(93)90323-G">Power convergent Boolean matrices</a>, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.

%H G. Markowsky, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN001251775">Bounds on the index and period of a binary relation on a finite set</a>, Semigroup Forum, Vol 13 (1977), 253-259.

%H E. de Panafieu and S. Dovgal, <a href="https://arxiv.org/abs/1903.09454">Symbolic method and directed graph enumeration</a>, arXiv:1903.09454 [math.CO], 2019.

%H R. W. Robinson, <a href="http://cobweb.cs.uga.edu/~rwr/publications/components.pdf">Counting digraphs with restrictions on the strong components</a>, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

%H D. Rosenblatt, <a href="https://nvlpubs.nist.gov/nistpubs/jres/67B/jresv67Bn4p249_A1b.pdf">On the graphs of finite Boolean relation matrices</a>, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

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

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

%Y Cf. A070322, A002416.

%K nonn,more

%O 0,2

%A _Geoffrey Critzer_, Sep 08 2023