OFFSET
0,3
COMMENTS
The total number of 3-cycles over all functions on {1,2,...,n} is 2*binomial(n,3)*n^(n-3). So we see that as n gets large the probability that a random function would contain k 3-cycles is a Poisson distribution with mean = 1/3. Generally, the total number of j-cycles over all functions on {1,2,...,n} is (j-1)!*binomial(n,j)*n^(n-j).
FORMULA
E.g.f.: exp(T(x)^3/3*(y - 1))/(1-T(x)) where T(x) is the e.g.f. for A000169.
EXAMPLE
1;
1;
4;
25, 2;
224, 32;
2625, 500;
38056, 8560, 40;
657433, 164150, 1960;
13178880, 3526656, 71680;
300585601, 84389928, 2442720, 2240;
...
MATHEMATICA
nn=10; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; Range[0, nn]!CoefficientList[ Series[Exp[t^3/3(y-1)]/(1-t), {x, 0, nn}], {x, y}]//Grid
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Geoffrey Critzer, Dec 25 2012
STATUS
approved