cp's OEIS Frontend

A231807 Number of endofunctions on [n] with distinct cardinalities of the nonempty preimages.

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