A185070 Triangular array read by rows. T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} that have exactly k 3-cycles. n>=0, 0<=k<=floor(n/3).

1, 1, 4, 25, 2, 224, 32, 2625, 500, 38056, 8560, 40, 657433, 164150, 1960, 13178880, 3526656, 71680, 300585601, 84389928, 2442720, 2240, 7683776000, 2232672000, 83328000, 224000, 217534555161, 64830707370, 2931500880, 14907200

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

Links

Table of n, a(n) for n=0..29.

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

Cf. A185025, A055134, A190314.

Sequence in context: A058230 A162187 A103644 * A272680 A082202 A283452

Adjacent sequences: A185067 A185068 A185069 * A185071 A185072 A185073

Keyword

nonn,tabf

Author

Geoffrey Critzer, Dec 25 2012

Status

approved