A212789 Number of endofunctions on [n] with distinct cycle lengths.

1, 1, 3, 20, 186, 2229, 32790, 572018, 11541600, 264370473, 6776462320, 192163455384, 5972728750560, 201906797867085, 7375152706023648, 289473254317393110, 12149690892777901568, 543010240381452000273, 25746662043469525754880, 1290829803802550504743036

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..300

Formula

E.g.f.: A(T(x)) where A(x) is e.g.f. for A007838 and T(x) is e.g.f. for A000169.

Example

a(3)=20 because there are 27 functions f:{1,2,3}->{1,2,3} but 7 of these have at least two cycles of equal length: (1,2,3);(1,2,1);(1,2,2);(1,1,3);(1,3,3);(2,2,3)(3,2,3) where the functions are represented by their values.

Maple

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..min(1, n/i))))
    end:
a:= n-> add(binomial(n-1, j-1)*n^(n-j)*b(j$2), j=0..n):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 10 2014

Mathematica

nn = 20; p = Product[1 + t^n/n, {n, 1, nn}]; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; Range[0, nn]! CoefficientList[Series[p, {x, 0, nn}], x]

Crossrefs

Cf. A241980.

Sequence in context: A129840 A358214 A085390 * A065980 A302581 A305460

Adjacent sequences: A212786 A212787 A212788 * A212790 A212791 A212792

Keyword

nonn

Author

Geoffrey Critzer, May 27 2012

Extensions

Terms a(8)-a(19) recomputed by Alois P. Heinz, Aug 10 2014

Status

approved