login
A061095
Number of ways of dividing n labeled items into labeled boxes with an equal number of items in each box.
18
1, 3, 7, 31, 121, 831, 5041, 42911, 364561, 3742453, 39916801, 486891175, 6227020801, 87859375033, 1307843292757, 21004582611871, 355687428096001, 6415015584161757, 121645100408832001, 2435278206317164781, 51091124681475552961, 1124549556257968545433
OFFSET
1,2
LINKS
Kévin Perrot, Sylvain Sené, and Léah Tapin, On countings and enumerations of block-parallel automata networks, arXiv:2304.09664 [cs.DM], 2023.
FORMULA
a(n) = Sum_{d|n} n!/(n/d)!^d.
E.g.f.: Sum_{k>0} x^k/(k!-x^k). - Vladeta Jovovic, Oct 13 2003
a(n) ~ n!. - Vaclav Kotesovec, Jul 21 2019
EXAMPLE
a(6) = 720+90+20+1 = 831 since 720 ways of evenly distributing six labeled items into six labeled boxes, 90 into three, 20 into two and 1 into one.
MAPLE
A061095 := n -> add(n!/(n/d)!^d, d = numtheory[divisors](n));
seq(A061095 (n), n = 1..17); # Peter Luschny, Apr 13 2011
MATHEMATICA
Table[Sum[n!/(n/d)!^d, {d, Divisors[n]}], {n, 1, 20}] (* Geoffrey Critzer, Aug 18 2011 *)
PROG
(PARI) /* compare to A038041 */
mnom(v)=
/* Multinomial coefficient s! / prod(j=1, n, v[j]!) where
s= sum(j=1, n, v[j]) and n is the number of elements in v[]. */
sum(j=1, #v, v[j])! / prod(j=1, #v, v[j]!)
A061095(n)={local(r=0); fordiv(n, d, r+=mnom(vector(d, j, n/d))); return(r); }
vector(33, n, A061095(n)) /* Joerg Arndt, Apr 16 2011 */
(PARI) a(n)=sumdiv(n, d, n!/(n/d)!^d ); \\ Joerg Arndt, Feb 23 2014
CROSSREFS
Column k=1 of A327803.
Sequence in context: A373755 A306831 A105765 * A357296 A103901 A089162
KEYWORD
nonn,nice,easy
AUTHOR
Henry Bottomley, May 29 2001
STATUS
approved