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

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

Offset: 1

Author

Geoffrey Critzer, Dec 05 2023

Keywords

• nonn
• tabl
• more

Comments

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.

Examples

			Triangle begins ...
        1;
        3,    1;
      139,    3,   2;
    25575,  103,  12,  6;
 18077431, 4815, 230, 60, 24;
 ...
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.
		

References

• R. Brualdi and H. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1991, pages 53-96.
• Ki Hang Kim, Boolean Matrix Theory and Applications, Marcel Dekker, 1982, pages 177-226.

Links

• S. Schwarz, On the semigroup of binary relations on a finite set, Czechoslovak Mathematical Journal, 1970.

Crossrefs

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

Formula

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

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

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