login
Triangular array read by rows. T(n,k) is the number of strongly connected binary relations on [n] (A186081) with period k, n >= 1, 1<=k<=n.
3

%I #19 Dec 12 2023 16:39:31

%S 1,3,1,139,3,2,25575,103,12,6,18077431,4815,230,60,24

%N Triangular array read by rows. T(n,k) is the number of strongly connected binary relations on [n] (A186081) with period k, n >= 1, 1<=k<=n.

%C Let A be a strongly connected binary relation on [n] with period k. Then k is equal to the greatest common divisor (GCD) of the lengths of the cycles in G(A) the directed graph (self loops allowed) associated to A. See section 5.2 in Ki Hang Kim reference. Also, k is equal to the GCD of all the integers e >=1 such that G(A^e) has at least one self loop. See Theorem 6.6 in Schwarz link. Also, for each pair of vertices x,y in G(A) the lengths of the directed walks from x to y are congruent modulo k. See Lemma 3.4.1 in Brualdi and Ryser reference. Finally, the idempotent in {A^i:i>=1} is the equivalence relation ~ defined by: For all x,y in [n], x ~ y iff the lengths of the xy-walks in G(A) are congruent to 0 modulo k. The equivalence relation ~ partitions [n] into exactly k blocks. See Theorem 7.3 in Schwarz link.

%D R. Brualdi and H. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1991, pages 53-96.

%D Ki Hang Kim, Boolean Matrix Theory and Applications, Marcel Dekker, 1982, pages 177-226.

%H S. Schwarz, <a href="http://dx.doi.org/10.21136/CMJ.1970.100989">On the semigroup of binary relations on a finite set</a>, Czechoslovak Mathematical Journal, 1970.

%F T(n,1) = A070322(n).

%F T(n,n) = (n-1)! counts relations that are simple cycles.

%F Sum_{k=1..n} T(n,k) = A186081(n).

%e Triangle begins ...

%e 1;

%e 3, 1;

%e 139, 3, 2;

%e 25575, 103, 12, 6;

%e 18077431, 4815, 230, 60, 24;

%e ...

%e T(4,3) = 12. Let A be the strongly connected relation on [4] whose adjacency matrix is {{0,0,0,1},{0,0,0,1},{1,1,0,0},{0,0,1,0}}. It is easy to check that the period of A is 3. Also, G(A) contains two cycles of length 3 so that the GCD of its cycle length is 3. Also {A^i:i>=1} contains the equivalence relation corresponding to the set partition {1,2}{3}{4}. There are 12 relations in the same isomorphism class as A so that T(4,3) = 12.

%Y Cf. A186081 (row sums), A070322 (column k=1).

%K nonn,tabl,more

%O 1,2

%A _Geoffrey Critzer_, Dec 05 2023