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

%I #19 Aug 11 2014 05:06:02

%S 1,1,3,20,186,2229,32790,572018,11541600,264370473,6776462320,

%T 192163455384,5972728750560,201906797867085,7375152706023648,

%U 289473254317393110,12149690892777901568,543010240381452000273,25746662043469525754880,1290829803802550504743036

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

%H Alois P. Heinz, <a href="/A212789/b212789.txt">Table of n, a(n) for n = 0..300</a>

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

%e 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.

%p with(combinat):

%p b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*

%p b(n-i*j, i-1), j=0..min(1, n/i))))

%p end:

%p a:= n-> add(binomial(n-1, j-1)*n^(n-j)*b(j$2), j=0..n):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Aug 10 2014

%t 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]

%Y Cf. A241980.

%K nonn

%O 0,3

%A _Geoffrey Critzer_, May 27 2012

%E Terms a(8)-a(19) recomputed by _Alois P. Heinz_, Aug 10 2014