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,2

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.

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

Table of n, a(n) for n=1..15.

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

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

Example

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.

Crossrefs

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

Sequence in context: A071291 A049330 A274040 * A369187 A266363 A068542

Adjacent sequences: A367945 A367946 A367947 * A367949 A367950 A367951

Keyword

nonn,tabl,more

Author

Geoffrey Critzer, Dec 05 2023

Status

approved