A061095 Number of ways of dividing n labeled items into labeled boxes with an equal number of items in each box.

1, 3, 7, 31, 121, 831, 5041, 42911, 364561, 3742453, 39916801, 486891175, 6227020801, 87859375033, 1307843292757, 21004582611871, 355687428096001, 6415015584161757, 121645100408832001, 2435278206317164781, 51091124681475552961, 1124549556257968545433

Offset: 1

Author

Henry Bottomley, May 29 2001

Keywords

• nonn
• nice
• easy

Examples

			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.
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..449
• Kévin Perrot, Sylvain Sené, and Léah Tapin, On countings and enumerations of block-parallel automata networks, arXiv:2304.09664 [cs.DM], 2023.

Crossrefs

Cf. A038041, A060538.

Column k=1 of A327803.

Programs

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 *)

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

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