login
A231807
Number of endofunctions on [n] with distinct cardinalities of the nonempty preimages.
3
1, 1, 2, 21, 52, 305, 7836, 24703, 155688, 1034433, 67124260, 235173191, 1728147312, 11309344813, 106962615592, 14055613872945, 55558358852176, 450373499691137, 3156524223157332, 28327606849223119, 307533111218771040, 81782486813477643501
OFFSET
0,3
COMMENTS
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)|.
LINKS
FORMULA
a(n) = n! * Sum_{lambda} multinomial(n;lambda)/(n-|lambda|)!, where lambda ranges over all partitions of n into distinct parts (A118457).
EXAMPLE
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).
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).
MAPLE
b:= proc(t, i, u) option remember; `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))))
end:
a:= n-> b(n$3):
seq(a(n), n=0..25);
MATHEMATICA
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]]]];
a[n_] := b[n, n, n];
a /@ Range[0, 25] (* Jean-François Alcover, Dec 10 2020, after Alois P. Heinz *)
CROSSREFS
Column k=1 of A231915.
Sequence in context: A042455 A245546 A074875 * A351118 A097718 A180232
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Nov 13 2013
STATUS
approved