|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|