login
Triangular array read by rows: T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} with a height of k; n>=1, 0<=k<=n-1.
2

%I #21 Feb 13 2022 19:31:07

%S 1,2,2,6,15,6,24,124,84,24,120,1185,1160,540,120,720,13086,17610,

%T 10560,3960,720,5040,165361,296772,214410,104160,32760,5040,40320,

%U 2363320,5536440,4692576,2686320,1115520,302400,40320,362880,37780497,113680800,111488328,72080064,35637840,12942720,3084480,362880

%N Triangular array read by rows: T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} with a height of k; n>=1, 0<=k<=n-1.

%C Here, the height of a function f (represented as a directed graph) is the maximum distance from a recurrent element to any non-recurrent element. An element x in {1,2,...,n} is a recurrent element if there is some k such that f^k(x) = x where f^k(x) denotes iterated functional composition. In other words, a recurrent element is in a cycle of the functional digraph.

%C Row sums = n^n (A000312).

%C First column (k = 0) counts the n! bijective functions.

%C T(n,n-1) = n! (A000142).

%H Alois P. Heinz, <a href="/A216242/b216242.txt">Rows n = 1..75, flattened</a>

%F Define G(k) recursively by G(k) = x*exp(G(k-1)) for k>0, G(0) = 0.

%F E.g.f. for column k is 1/(1-G(k+1)) - 1/(1-G(k)).

%e Triangle T(n,k) begins:

%e 1;

%e 2, 2;

%e 6, 15, 6;

%e 24, 124, 84, 24;

%e 120, 1185, 1160, 540, 120;

%e 720, 13086, 17610, 10560, 3960, 720;

%e 5040, 165361, 296772, 214410, 104160, 32760, 5040;

%e ...

%p G:= proc(k) G(k):= `if`(k=0, 0, x*exp(G(k-1))) end:

%p T:= (n, k)-> n!*coeff(series(1/(1-G(k+1))-1/(1-G(k)), x, n+1), x, n):

%p seq(seq(T(n, k), k=0..n-1), n=1..10); # _Alois P. Heinz_, Mar 14 2013

%t nn=8;a=NestList[x Exp[#]&,0,nn];f[list_]:=Sum[list[[i]]*i,{i,1,Length[list]}];g[list_]:=Select[list,#>0&];Map[g,Transpose[Table[Range[0,nn]!CoefficientList[Series[1/(1-a[[i+1]])-1/(1-a[[i]]),{x,0,nn}],x],{i,1,nn-1}]]]//Grid

%Y Cf. A001854, A034855.

%K nonn,tabl

%O 1,2

%A _Geoffrey Critzer_, Mar 14 2013