|
%I #19 Dec 10 2020 17:37:33
%S 1,1,2,21,52,305,7836,24703,155688,1034433,67124260,235173191,
%T 1728147312,11309344813,106962615592,14055613872945,55558358852176,
%U 450373499691137,3156524223157332,28327606849223119,307533111218771040,81782486813477643501
%N Number of endofunctions on [n] with distinct cardinalities of the nonempty preimages.
%C Number of endofunctions f:{1,...,n}-> {1,...,n} such that (1<=i<j<=n and |f^(-1)(i)|>0 and |f^(-1)(j)|>0) implies |f^(-1)(i)| != |f^(-1)(j)|.
%H Alois P. Heinz, <a href="/A231807/b231807.txt">Table of n, a(n) for n = 0..637</a>
%F a(n) = n! * Sum_{lambda} multinomial(n;lambda)/(n-|lambda|)!, where lambda ranges over all partitions of n into distinct parts (A118457).
%e a(3) = 3! * (multinomial(3;3)/2! + multinomial(3;2,1)/1!) = 3+18 = 21: (1,1,1), (2,2,2), (3,3,3), (1,1,2), (1,1,3), (1,2,1), (1,3,1), (2,1,1), (3,1,1), (2,2,1), (2,2,3), (2,1,2), (2,3,2), (1,2,2), (3,2,2), (3,3,1), (3,3,2), (3,1,3), (3,2,3), (1,3,3), (2,3,3).
%e a(4) = 52: (1,1,1,1), (1,1,1,2), (1,1,1,3), ..., (4,4,4,2), (4,4,4,3), (4,4,4,4).
%p b:= proc(t, i, u) option remember; `if`(t=0, 1, `if`(i<1, 0,
%p b(t, i-1, u) +`if`(i>t, 0, b(t-i, i-1, u-1)*u*binomial(t,i))))
%p end:
%p a:= n-> b(n$3):
%p seq(a(n), n=0..25);
%t b[t_, i_, u_] := b[t, i, u] = If[t == 0, 1, If[i < 1, 0, b[t, i - 1, u] + If[i > t, 0, b[t - i, i - 1, u - 1] u Binomial[t, i]]]];
%t a[n_] := b[n, n, n];
%t a /@ Range[0, 25] (* _Jean-François Alcover_, Dec 10 2020, after _Alois P. Heinz_ *)
%Y Column k=1 of A231915.
%Y Cf. A000009, A000312, A231812.
%K nonn
%O 0,3
%A _Alois P. Heinz_, Nov 13 2013
|
