cp's OEIS Frontend

A216242 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.

%I A216242 #21 Feb 13 2022 19:31:07
%S A216242 1,2,2,6,15,6,24,124,84,24,120,1185,1160,540,120,720,13086,17610,
%T A216242 10560,3960,720,5040,165361,296772,214410,104160,32760,5040,40320,
%U A216242 2363320,5536440,4692576,2686320,1115520,302400,40320,362880,37780497,113680800,111488328,72080064,35637840,12942720,3084480,362880
%N A216242 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 A216242 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 A216242 Row sums = n^n (A000312).
%C A216242 First column (k = 0) counts the n! bijective functions.
%C A216242 T(n,n-1) = n! (A000142).
%H A216242 Alois P. Heinz, <a href="/A216242/b216242.txt">Rows n = 1..75, flattened</a>
%F A216242 Define G(k) recursively by G(k) = x*exp(G(k-1)) for k>0, G(0) = 0.
%F A216242 E.g.f. for column k is 1/(1-G(k+1)) - 1/(1-G(k)).
%e A216242 Triangle T(n,k) begins:
%e A216242      1;
%e A216242      2,       2;
%e A216242      6,      15,       6;
%e A216242     24,     124,      84,      24;
%e A216242    120,    1185,    1160,     540,     120;
%e A216242    720,   13086,   17610,   10560,    3960,    720;
%e A216242   5040,  165361,  296772,  214410,  104160,  32760,   5040;
%e A216242   ...
%p A216242 G:= proc(k) G(k):= `if`(k=0, 0, x*exp(G(k-1))) end:
%p A216242 T:= (n, k)-> n!*coeff(series(1/(1-G(k+1))-1/(1-G(k)), x, n+1), x, n):
%p A216242 seq(seq(T(n, k), k=0..n-1), n=1..10); # _Alois P. Heinz_, Mar 14 2013
%t A216242 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 A216242 Cf. A001854, A034855.
%K A216242 nonn,tabl
%O A216242 1,2
%A A216242 _Geoffrey Critzer_, Mar 14 2013