OFFSET
0,3
COMMENTS
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
LINKS
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.
FORMULA
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
EXAMPLE
[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;
MAPLE
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
MATHEMATICA
T[ n_, k_] := Sum[ Binomial[n, k-j] StirlingS2[n-k+j, j], {j, 0 , k}]; (* Michael Somos, Jul 18 2021 *)
PROG
(PARI) T(n, k) = sum(j=0, k, binomial(n, j)*stirling(n-j, k-j, 2)); /* Michael Somos, Jul 18 2021 */
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Jan 08 2021
EXTENSIONS
New name from Peter Luschny, Feb 09 2021
STATUS
approved