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

1, 1, 2, 21, 52, 305, 7836, 24703, 155688, 1034433, 67124260, 235173191, 1728147312, 11309344813, 106962615592, 14055613872945, 55558358852176, 450373499691137, 3156524223157332, 28327606849223119, 307533111218771040, 81782486813477643501

Offset: 0

Author

Alois P. Heinz, Nov 13 2013

Keywords

• nonn

Comments

Number of endofunctions f:{1,...,n}-> {1,...,n} such that (1<=i0 and |f^(-1)(j)|>0) implies |f^(-1)(i)| != |f^(-1)(j)|.

Examples

			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).
		

Links

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

Crossrefs

Column k=1 of A231915.

Cf. A000009, A000312, A231812.

Programs

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 *)

Formula

a(n) = n! * Sum_{lambda} multinomial(n;lambda)/(n-|lambda|)!, where lambda ranges over all partitions of n into distinct parts (A118457).