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

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

Author

Peter Luschny, Jan 08 2021

Keywords

• nonn
• tabl

Comments

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

Examples

			[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;
		

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.

Crossrefs

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.

Programs

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

PARI

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

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

Extensions

New name from Peter Luschny, Feb 09 2021