A245958 Number T(n,k) of endofunctions f on [n] satisfying f^3(i) = i for all i in [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 4, 2, 1, 27, 11, 5, 3, 256, 88, 36, 18, 9, 3125, 925, 335, 141, 57, 21, 46656, 12096, 3912, 1440, 516, 186, 81, 823543, 189679, 55377, 18279, 6003, 2079, 837, 351, 16777216, 3473408, 924160, 277824, 84624, 27672, 10116, 3690, 1233

Offset: 0

Author

Alois P. Heinz, Aug 08 2014

Keywords

• nonn
• tabl

Examples

			Triangle T(n,k) begins:
0 :       1;
1 :       1,      1;
2 :       4,      2,     1;
3 :      27,     11,     5,     3;
4 :     256,     88,    36,    18,    9;
5 :    3125,    925,   335,   141,   57,   21;
6 :   46656,  12096,  3912,  1440,  516,  186,  81;
7 :  823543, 189679, 55377, 18279, 6003, 2079, 837, 351;
     ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Column k=0 gives A000312.

T(2n,n) gives A245959.

Main diagonal gives A001470.

Cf. A241015.

Programs

Maple

with(combinat): M:=multinomial:
T:= proc(n, k) local l, g; l, g:= [1, 3],
      proc(k, m, i, t) option remember; local d, j; d:= l[i];
        `if`(i=1, n^m, add(M(k, k-(d-t)*j, (d-t)$j)/j!*
         (d-1)!^j *M(m, m-t*j, t$j) *g(k-(d-t)*j, m-t*j,
        `if`(d-t=1, [i-1, 0], [i, t+1])[]), j=0..min(k/(d-t),
        `if`(t=0, [][], m/t))))
      end; g(k, n-k, nops(l), 0)
    end:
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

M[n_, m_, k_List] := n!/Times @@ (Join[{m}, k]!);
T[0, 0] = 1; T[n_, k_] := T[n, k] = Module[{l = {1, 3}, g}, g[k0_, m_, {i_, t_}] := g[k0, m, i, t]; g[k0_, m_, i_, t_] := g[k0, m, i, t] = Module[ {d}, d = l[[i]]; If[i == 1, n^m, Sum[M[k0, k0 - (d-t)*j, Table[(d-t), {j}]]/j!*(d-1)!^j*M[m, m - t*j, Table[t, {j}]]*g[k0 - (d-t)*j, m - t*j, If[d-t == 1, {i-1, 0}, {i, t+1}]], {j, 0, Min[k0/(d-t), If[t == 0, Infinity, m/t]]}]]]; g[k, n-k, Length[l], 0]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 03 2019, after Alois P. Heinz *)