A350446 Number T(n,k) of endofunctions on [n] with exactly k cycles of length larger than 1; triangle T(n,k), n>=0, 0<=k<=floor(n/2), read by rows.

1, 1, 3, 1, 16, 11, 125, 128, 3, 1296, 1734, 95, 16807, 27409, 2425, 15, 262144, 499400, 61054, 945, 4782969, 10346328, 1605534, 42280, 105, 100000000, 240722160, 44981292, 1706012, 11025, 2357947691, 6222652233, 1351343346, 67291910, 763875, 945

Offset

0,3

Links

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

Formula

From Mélika Tebni, Mar 23 2023: (Start)

E.g.f. of column k: (W(-x)-log(1 + W(-x)))^k / (exp(W(-x))*k!), W(x) the Lambert W-function.

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

T(n,k) = Sum_{j=k..n} (n-j+1)^(n-j-1)*binomial(n,j)*A350452(j,k).

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

Sum_{k=0..n/2} 2^k*T(n,k) = A217701(n). (End)

Example

Triangle T(n,k) begins:
           1;
           1;
           3,          1;
          16,         11;
         125,        128,          3;
        1296,       1734,         95;
       16807,      27409,       2425,       15;
      262144,     499400,      61054,      945;
     4782969,   10346328,    1605534,    42280,    105;
   100000000,  240722160,   44981292,  1706012,  11025;
  2357947691, 6222652233, 1351343346, 67291910, 763875, 945;
  ...

Maple

c:= proc(n) option remember; add(n!*n^(n-k-1)/(n-k)!, k=2..n) end:
t:= proc(n) option remember; n^(n-1) end:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
      b(n-i)*binomial(n-1, i-1)*(c(i)*x+t(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);
# second Maple program:
egf := k-> (LambertW(-x)-log(1+LambertW(-x)))^k/(exp(LambertW(-x))*k!):
A350446 := (n, k)-> n! * coeff(series(egf(k), x, n+1), x, n):
seq(print(seq(A350446(n, k), k=0..n/2)), n=0..10); # Mélika Tebni, Mar 23 2023

Mathematica

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

Crossrefs

Column k=0 gives A000272(n+1).

Row sums give A000312.

T(2n,n) gives A001147.

Cf. A055134, A060281, A349454, A350452.

Cf. A136394, A190314, A217701.

Sequence in context: A222029 A038675 A264902 * A156653 A048159 A276640

Adjacent sequences: A350443 A350444 A350445 * A350447 A350448 A350449

Keyword

nonn,tabf

Author

Alois P. Heinz, Dec 31 2021

Status

approved