A186081 -id:A186081 - cp's OEIS frontend

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

Geoffrey Critzer, Dec 05 2023

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.

			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.

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.

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

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

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

A340264 T(n, k) = Sum_{j=0..k} binomial(n, k - j)*Stirling2(n - k + j, j). Triangle read by rows, 0 <= k <= n.

Original entry on oeis.org

1, 0, 2, 0, 1, 4, 0, 1, 6, 8, 0, 1, 11, 24, 16, 0, 1, 20, 70, 80, 32, 0, 1, 37, 195, 340, 240, 64, 0, 1, 70, 539, 1330, 1400, 672, 128, 0, 1, 135, 1498, 5033, 7280, 5152, 1792, 256, 0, 1, 264, 4204, 18816, 35826, 34272, 17472, 4608, 512

Offset: 0

Peter Luschny, Jan 08 2021

A006905(n) = Sum_{k=0..n} A001035(k) * T(n, k). - Michael Somos, Jul 18 2021

T(n, k) is the number of idempotent relations R on [n] containing exactly k strongly connected components such that the following conditional statement holds for all x, y in [n]: If x, y are in distinct strongly connected components of R then (x, y) is not in R. - Geoffrey Critzer, Jan 10 2024

			[0] 1;
[1] 0, 2;
[2] 0, 1,   4;
[3] 0, 1,   6,    8;
[4] 0, 1,  11,   24,    16;
[5] 0, 1,  20,   70,    80,    32;
[6] 0, 1,  37,  195,   340,   240,    64;
[7] 0, 1,  70,  539,  1330,  1400,   672,   128;
[8] 0, 1, 135, 1498,  5033,  7280,  5152,  1792,  256;
[9] 0, 1, 264, 4204, 18816, 35826, 34272, 17472, 4608, 512;

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Štefan Schwarz, On idempotent binary relations on a finite set, Czechoslovak Mathematical Journal, Vol. 20 (1970), No. 4, 696-702.
Eric Weisstein's World of Mathematics, Bell Polynomial.

Sum of row(n) is A000110(n+1).
Sum of row(n) - 2^n is A058681(n).
Alternating sum of row(n) is A109747(n).
Cf. A001035, A006905, A137375, A186081, A121337.

egf := exp(t*(exp(-x) - x - 1));
ser := series(egf, x, 22):
p := n -> coeff(ser, x, n);
seq(seq((-1)^n*n!*coeff(p(n), t, k), k=0..n), n = 0..10);
# Alternative:
T := (n, k) -> add(binomial(n, k - j)*Stirling2(n - k + j, j), j=0..k):
seq(seq(T(n, k), k = 0..n), n=0..9); # Peter Luschny, Feb 09 2021

T[ n_, k_] := Sum[ Binomial[n, k-j] StirlingS2[n-k+j, j], {j, 0 ,k}]; (* Michael Somos, Jul 18 2021 *)

T(n, k) = sum(j=0, k, binomial(n, j)*stirling(n-j, k-j, 2)); /* Michael Somos, Jul 18 2021 */

T(n, k) = (-1)^n * n! * [t^k] [x^n] exp(t*(exp(-x) - x - 1)).

n-th row polynomial R(n,x) = exp(-x)*Sum_{k >= 0} (x + k)^n * x^k/k! = Sum_{k = 0..n} binomial(n,k)*Bell(k,x)*x^(n-k), where Bell(n,x) denotes the n-th Bell polynomial. - Peter Bala, Jan 13 2022

New name from Peter Luschny, Feb 09 2021

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A340264 T(n, k) = Sum_{j=0..k} binomial(n, k - j)*Stirling2(n - k + j, j). Triangle read by rows, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions