login
Triangular array read by rows, T(n,k) = number of partial functions on {1,2,...,n} with exactly k cycles.
1

%I #14 Nov 07 2014 05:27:39

%S 1,1,1,3,5,1,16,35,12,1,125,328,149,22,1,1296,3894,2125,425,35,1,

%T 16807,56221,35044,8555,970,51,1,262144,958152,661878,186809,26180,

%U 1918,70,1,4782969,18849384,14145858,4467092,731059,66836,3430,92,1

%N Triangular array read by rows, T(n,k) = number of partial functions on {1,2,...,n} with exactly k cycles.

%C Here we consider the directed graphs of partial functions on {1,2,...,n} where the undefined points are mapped to a special value (forming a forest).

%C Row sums = (n+1)^n.

%H Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, Cambridge Univ. Press, 2009, page 132.

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

%e 1,

%e 1, 1,

%e 3, 5, 1,

%e 16, 35, 12, 1,

%e 125, 328, 149, 22, 1,

%e 1296, 3894, 2125, 425, 35, 1,

%e 16807, 56221, 35044, 8555, 970, 51, 1

%t nn=6; t=Sum[n^(n-1)x^n/n!, {n,1,nn}]; Range[0,nn]! CoefficientList[Series[Exp[t]/(1-t)^y, {x,0,nn}], {x,y}] //Grid

%K nonn,tabl

%O 0,4

%A _Geoffrey Critzer_, Sep 08 2012