A350452 Number T(n,k) of endofunctions on [n] with exactly k connected components and no fixed points; triangle T(n,k), n>=0, 0<=k<=floor(n/2), read by rows.

1, 0, 0, 1, 0, 8, 0, 78, 3, 0, 944, 80, 0, 13800, 1810, 15, 0, 237432, 41664, 840, 0, 4708144, 1022252, 34300, 105, 0, 105822432, 27098784, 1286432, 10080, 0, 2660215680, 778128336, 47790540, 648900, 945, 0, 73983185000, 24165049920, 1815578160, 36048320, 138600

Offset

0,6

Comments

For k >= 2 and p prime, T(p,k) == 0 (mod 4*p*(p-1)). - Mélika Tebni, Jan 20 2023

Links

Alois P. Heinz, Rows n = 0..200, flattened

Formula

From Mélika Tebni, Jan 20 2023: (Start)

E.g.f. column k: (LambertW(-x) - log(1 + LambertW(-x)))^k / k!.

-Sum_{k=1..n/2} (-1)^k*T(n,k) = A071720(n+1), for n > 0.

-Sum_{k=1..n/2} (-1)^k*T(n,k) / (n-1) = A007830(n-2), for n > 1.

T(n,k) = Sum_{j=k..n} n^(n-j)*binomial(n-1, j-1)*A106828(j, k) for n > 0. (End)

Example

Triangle T(n,k) begins:
  1;
  0;
  0,          1;
  0,          8;
  0,         78,         3;
  0,        944,        80;
  0,      13800,      1810,       15;
  0,     237432,     41664,      840;
  0,    4708144,   1022252,    34300,    105;
  0,  105822432,  27098784,  1286432,  10080;
  0, 2660215680, 778128336, 47790540, 648900, 945;
  ...

Maple

c:= proc(n) option remember; add(n!*n^(n-k-1)/(n-k)!, k=2..n) end:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
      b(n-i)*binomial(n-1, i-1)*x*c(i), i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n/2))(b(n)):
seq(T(n), n=0..12);

Mathematica

c[n_] := c[n] = Sum[n!*n^(n - k - 1)/(n - k)!, {k, 2, n}];
b[n_] := b[n] = Expand[If[n == 0, 1, Sum[
     b[n - i]*Binomial[n - 1, i - 1]*x*c[i], {i, 1, n}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n/2}]][b[n]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Mar 18 2022, after Alois P. Heinz *)

Prog

(PARI) \\ here AS1(n, k) gives associated Stirling numbers of 1st kind.
AS1(n, k)={(-1)^(n+k)*sum(i=0, k, (-1)^i * binomial(n, i) * stirling(n-i, k-i, 1) )}
T(n, k) = {if(n==0, k==0, sum(j=k, n, n^(n-j)*binomial(n-1, j-1)*AS1(j, k)))} \\ Andrew Howroyd, Jan 20 2023

Crossrefs

Columns k=0-1 give: A000007, A000435.

Row sums give A065440.

T(2n,n) gives A001147.

Cf. A060281, A061356, A350446.

Cf. A071720, A007830, A106828.

Sequence in context: A167318 A186979 A067817 * A079137 A181689 A221887

Adjacent sequences: A350449 A350450 A350451 * A350453 A350454 A350455

Keyword

nonn,tabf

Author

Alois P. Heinz, Dec 31 2021

Status

approved