login
Number of ways to partition an n-set into subsets of equal size.
122

%I #70 Sep 26 2024 12:58:14

%S 1,2,2,5,2,27,2,142,282,1073,2,32034,2,136853,1527528,4661087,2,

%T 227932993,2,3689854456,36278688162,13749663293,2,14084955889019,

%U 5194672859378,7905858780927,2977584150505252,13422745388226152,2,1349877580746537123,2

%N Number of ways to partition an n-set into subsets of equal size.

%C a(n) = 2 iff n is prime with a(p) = card{ 1|2|3|...|p-1|p, 123...p } = 2. - _Bernard Schott_, May 16 2019

%H Alois P. Heinz, <a href="/A038041/b038041.txt">Table of n, a(n) for n = 1..250</a>

%H Gus Wiseman, <a href="/A038041/a038041.txt">Sequences counting and ranking multiset partitions whose part lengths, sums, or averages are constant or strict.</a>

%F a(n) = Sum_{d divides n} (n!/(d!*((n/d)!)^d)).

%F E.g.f.: Sum_{k >= 1} (exp(x^k/k!)-1).

%e a(4) = card{ 1|2|3|4, 12|34, 14|23, 13|24, 1234 } = 5.

%e From _Gus Wiseman_, Jul 12 2019: (Start)

%e The a(6) = 27 set partitions:

%e {{1}{2}{3}{4}{5}{6}} {{12}{34}{56}} {{123}{456}} {{123456}}

%e {{12}{35}{46}} {{124}{356}}

%e {{12}{36}{45}} {{125}{346}}

%e {{13}{24}{56}} {{126}{345}}

%e {{13}{25}{46}} {{134}{256}}

%e {{13}{26}{45}} {{135}{246}}

%e {{14}{23}{56}} {{136}{245}}

%e {{14}{25}{36}} {{145}{236}}

%e {{14}{26}{35}} {{146}{235}}

%e {{15}{23}{46}} {{156}{234}}

%e {{15}{24}{36}}

%e {{15}{26}{34}}

%e {{16}{23}{45}}

%e {{16}{24}{35}}

%e {{16}{25}{34}}

%e (End)

%p A038041 := proc(n) local d;

%p add(n!/(d!*(n/d)!^d), d = numtheory[divisors](n)) end:

%p seq(A038041(n),n = 1..29); # _Peter Luschny_, Apr 16 2011

%t a[n_] := Block[{d = Divisors@ n}, Plus @@ (n!/(#! (n/#)!^#) & /@ d)]; Array[a, 29] (* _Robert G. Wilson v_, Apr 16 2011 *)

%t Table[Sum[n!/((n/d)!*(d!)^(n/d)), {d, Divisors[n]}], {n, 1, 31}] (* _Emanuele Munarini_, Jan 30 2014 *)

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t Table[Length[Select[sps[Range[n]],SameQ@@Length/@#&]],{n,0,8}] (* _Gus Wiseman_, Jul 12 2019 *)

%o (PARI) /* compare to A061095 */

%o mnom(v)=

%o /* Multinomial coefficient s! / prod(j=1, n, v[j]!) where

%o s= sum(j=1, n, v[j]) and n is the number of elements in v[]. */

%o sum(j=1, #v, v[j])! / prod(j=1, #v, v[j]!)

%o A038041(n)={local(r=0);fordiv(n,d,r+=mnom(vector(d,j,n/d))/d!);return(r);}

%o vector(33,n,A038041(n)) /* _Joerg Arndt_, Apr 16 2011 */

%o (Maxima) a(n):= lsum(n!/((n/d)!*(d!)^(n/d)),d,listify(divisors(n)));

%o makelist(a(n),n,1,40); /* _Emanuele Munarini_, Feb 03 2014 */

%o (Python)

%o import math

%o def a(n):

%o count = 0

%o for k in range(1, n + 1):

%o if n % k == 0:

%o count += math.factorial(n) // (math.factorial(k) ** (n // k) * math.factorial(n // k))

%o return count # _Paul Muljadi_, Sep 25 2024

%Y Cf. A061095 (same but with labeled boxes), A005225, A236696, A055225, A262280, A262320.

%Y Column k=1 of A208437.

%Y Row sums of A200472 and A200473.

%Y Cf. A000110, A007837 (different lengths), A035470 (equal sums), A275780, A317583, A320324, A322794, A326512 (equal averages), A326513.

%K nonn,easy

%O 1,2

%A _Christian G. Bower_

%E More terms from _Erich Friedman_