A231812 Number of endofunctions on [n] where all nonempty preimages have the same cardinality.

1, 1, 4, 9, 64, 125, 2826, 5047, 218688, 504009, 32216950, 39916811, 7585223196, 6227020813, 2424646536326, 1813027195995, 1072898135852416, 355687428096017, 616925243565037854, 121645100408832019, 441395941479128984940, 72313131901887676821

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(2) = 4: (1,1), (1,2), (2,1), (2,2).
a(3) = 9: (1,1,1), (1,2,3), (1,3,2), (2,1,3), (2,2,2), (2,3,1), (3,1,2), (3,2,1), (3,3,3).
a(4) = 64: (1,1,1,1), (1,1,2,2), (1,1,3,3), ..., (4,4,3,3), (4,4,4,4).
		

Links

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

Crossrefs

Main diagonal of A231915.

Cf. A000312, A005095, A231807.

Programs

Maple

with(numtheory): with(combinat): C:= binomial:
a:= n-> `if`(n=0, 1, add(multinomial(n, n/d$d)*C(n, d), d=divisors(n))):
seq(a(n), n=0..25);

Mathematica

multinomial[n_, k_List] := n!/Times @@ (k!); a[n_] := If[n == 0, 1, Sum[multinomial[n, Array[n/d&, d]]*Binomial[n, d], {d, Divisors[n]}]]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

Formula

a(n) = Sum_{d|n} multinomial(n; {n/d}^d)*C(n,d) for n>0, a(0) = 1.

a(n) = n! + n = A005095(n) for prime n.