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..300
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.
EXAMPLE
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).
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Nov 13 2013
STATUS
approved