login
A231812
Number of endofunctions on [n] where all nonempty preimages have the same cardinality.
4
1, 1, 4, 9, 64, 125, 2826, 5047, 218688, 504009, 32216950, 39916811, 7585223196, 6227020813, 2424646536326, 1813027195995, 1072898135852416, 355687428096017, 616925243565037854, 121645100408832019, 441395941479128984940, 72313131901887676821
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) = 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
Main diagonal of A231915.
Sequence in context: A140483 A124683 A077163 * A069711 A062067 A110256
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Nov 13 2013
STATUS
approved