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,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

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

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.

Cf. A000009, A000312, A231812.

Sequence in context: A042455 A245546 A074875 * A351118 A097718 A180232

Adjacent sequences: A231804 A231805 A231806 * A231808 A231809 A231810

Keyword

nonn

Author

Alois P. Heinz, Nov 13 2013

Status

approved