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

1, 2, 2, 5, 2, 27, 2, 142, 282, 1073, 2, 32034, 2, 136853, 1527528, 4661087, 2, 227932993, 2, 3689854456, 36278688162, 13749663293, 2, 14084955889019, 5194672859378, 7905858780927, 2977584150505252, 13422745388226152, 2, 1349877580746537123, 2

Offset

1,2

Comments

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

Links

Alois P. Heinz, Table of n, a(n) for n = 1..250

Gus Wiseman, Sequences counting and ranking multiset partitions whose part lengths, sums, or averages are constant or strict.

Formula

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

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

Example

a(4) = card{ 1|2|3|4, 12|34, 14|23, 13|24, 1234 } = 5.
From Gus Wiseman, Jul 12 2019: (Start)
The a(6) = 27 set partitions:
  {{1}{2}{3}{4}{5}{6}}  {{12}{34}{56}}  {{123}{456}}  {{123456}}
                        {{12}{35}{46}}  {{124}{356}}
                        {{12}{36}{45}}  {{125}{346}}
                        {{13}{24}{56}}  {{126}{345}}
                        {{13}{25}{46}}  {{134}{256}}
                        {{13}{26}{45}}  {{135}{246}}
                        {{14}{23}{56}}  {{136}{245}}
                        {{14}{25}{36}}  {{145}{236}}
                        {{14}{26}{35}}  {{146}{235}}
                        {{15}{23}{46}}  {{156}{234}}
                        {{15}{24}{36}}
                        {{15}{26}{34}}
                        {{16}{23}{45}}
                        {{16}{24}{35}}
                        {{16}{25}{34}}
(End)

Maple

A038041 := proc(n) local d;
add(n!/(d!*(n/d)!^d), d = numtheory[divisors](n)) end:
seq(A038041(n), n = 1..29); # Peter Luschny, Apr 16 2011

Mathematica

a[n_] := Block[{d = Divisors@ n}, Plus @@ (n!/(#! (n/#)!^#) & /@ d)]; Array[a, 29] (* Robert G. Wilson v, Apr 16 2011 *)
Table[Sum[n!/((n/d)!*(d!)^(n/d)), {d, Divisors[n]}], {n, 1, 31}] (* Emanuele Munarini, Jan 30 2014 *)
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
Table[Length[Select[sps[Range[n]], SameQ@@Length/@#&]], {n, 0, 8}] (* Gus Wiseman, Jul 12 2019 *)

Prog

(PARI)  /* compare to A061095 */
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]!)
A038041(n)={local(r=0); fordiv(n, d, r+=mnom(vector(d, j, n/d))/d!); return(r); }
vector(33, n, A038041(n)) /* Joerg Arndt, Apr 16 2011 */
(Maxima) a(n):= lsum(n!/((n/d)!*(d!)^(n/d)), d, listify(divisors(n)));
makelist(a(n), n, 1, 40); /* Emanuele Munarini, Feb 03 2014 */

Crossrefs

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

Column k=1 of A208437.

Row sums of A200472 and A200473.

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

Sequence in context: A324505 A226135 A284464 * A197591 A097891 A097611

Adjacent sequences: A038038 A038039 A038040 * A038042 A038043 A038044

Keyword

nonn,easy

Author

Christian G. Bower

Extensions

More terms from Erich Friedman

Status

approved