login
Triangular array read by rows. T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} that have exactly k recurrent elements whose preimage contains only one element, n>=0, 0<=k<=n.
0

%I #10 Jan 17 2013 09:17:05

%S 0,0,1,2,0,2,9,12,0,6,88,72,72,0,24,985,1000,540,480,0,120,13956,

%T 13980,10080,4320,3600,0,720,233149,243684,169470,104160,37800,30240,

%U 0,5040,4519824,4835824,3544128,2049600,1142400,362880,282240,0,40320,99606609,109239120,81840024,50452416,25779600,13426560,3810240,2903040,0,362880

%N Triangular array read by rows. T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} that have exactly k recurrent elements whose preimage contains only one element, n>=0, 0<=k<=n.

%C A functional digraph of a function f:{1,2,...,n}->{1,2,...,n} is a directed graph on vertex set {1,2,...,n} with an arrow from i to j if f(i)=j. Every connected component of the digraph contains a unique cycle and every vertex i of this cycle is the root of a rooted tree directed towards i. T(n,k) is the number k of rooted trees that consist of a single vertex over all cycles in all functional digraphs on {1,2,...,n}. Definition from Stanley, page 83.

%C Row sums = n^n

%D R. Stanley, Enumerative Combinatorics Vol II, Cambridge Univ. Press, 1999.

%F E.g.f.:1/(1 - x*(exp(T(x) -1 +y)) where T(x) is the e.g.f. for A000169.

%e 0,

%e 0, 1,

%e 2, 0, 2,

%e 9, 12, 0, 6,

%e 88, 72, 72, 0, 24,

%e 985, 1000, 540, 480, 0, 120,

%e 13956, 13980, 10080, 4320, 3600, 0, 720

%t nn=6;f[list_]:=Select[list,#>0&];t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Prepend[Drop[Map[Insert[#,0,-2]&,Map[f,Range[0,nn]!CoefficientList[Series[1/(1-x(Exp[t]-1+y)),{x,0,nn}],{x,y}]]],1],{0}]//Grid

%K nonn,tabl

%O 0,4

%A _Geoffrey Critzer_, Dec 08 2012