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.

1, 2, 2, 6, 15, 6, 24, 124, 84, 24, 120, 1185, 1160, 540, 120, 720, 13086, 17610, 10560, 3960, 720, 5040, 165361, 296772, 214410, 104160, 32760, 5040, 40320, 2363320, 5536440, 4692576, 2686320, 1115520, 302400, 40320, 362880, 37780497, 113680800, 111488328, 72080064, 35637840, 12942720, 3084480, 362880

Offset: 1

Author

Geoffrey Critzer, Mar 14 2013

Keywords

• nonn
• tabl

Comments

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.

Row sums = n^n (A000312).

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

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

Examples

			Triangle T(n,k) begins:
     1;
     2,       2;
     6,      15,       6;
    24,     124,      84,      24;
   120,    1185,    1160,     540,     120;
   720,   13086,   17610,   10560,    3960,    720;
  5040,  165361,  296772,  214410,  104160,  32760,   5040;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..75, flattened

Crossrefs

Cf. A001854, A034855.

Programs

Maple

G:= proc(k) G(k):= `if`(k=0, 0, x*exp(G(k-1))) end:
T:= (n, k)-> n!*coeff(series(1/(1-G(k+1))-1/(1-G(k)), x, n+1), x, n):
seq(seq(T(n, k), k=0..n-1), n=1..10); # Alois P. Heinz, Mar 14 2013

Mathematica

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

Formula

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

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