How many partitions of $n$ different objects into equinumerous parts are there?

Question

How many partitions of $n$ distinct objects are there, given that all parts are equinumerous? (Let us not consider the empty partition and the identity partition.)

The cases when $n$ is the unit, or when $n$ is prime, are trivial. In these cases we have $0$ partition and $1$ partition respectively.

So treat this question as asking about the number of such partitions for composite $n.$

In particular, the case when $n = p^2$ with $p$ prime is very interesting. For example, when $n = 4,$ we have $3$ such partitions. What of when $n$ is $9,$ or $25,$ or $49,$ and so on?

Thank you.

Answer 1

If $m$ divides $n$, then there are $\frac{n!}{(m!)^{n/m}(n/m)!}$ to partition $n$ objects into parts each having size $m$. Proof: such a partition can be formed by ordering the $n$ objects in a row ($n!$ ways) and letting the first $m$ objects be the first part of the partition, the next $m$ objects being the second part, and so on. To account for overcounting, you must divide by $m!$ for each part (since you don't care about the order within each part of the partition) and divide by $(n/m)!$ (since you don't care about the order of the parts of the partition).

For instance when $n=4$ and $m=2$, we have $\frac{4!}{(2!)^2 (4/2)!} = \frac{24}{8}=3$. More generally, when $n=p^2$ and $m=p$, we have $$\frac{(p^2)!}{(p!)^{p+1}}.$$

Then you have to sum over all divisors $m$ of $n$ (and exclude the case $m=1$ and $m=n$ if you want to avoid those trivial partitions). $$\left(\sum_{m \mid n} \frac{n!}{(m!)^{n/m}(n/m)!}\right) - 2$$

Answer 2

You can arrange the numbers from $1$ to $p^2$ in $(p^2)!$ ways. Thinking of each group of $p$ numbers as a bucket in a partition, rearranging the numbers in each bucket does not change the partition ($p$ buckets, each of which can be rearranged in $p!$ ways), nor does rearranging the buckets themselves ($p!$ arrangements). So there should be $$\frac{(p^2)!}{(p!)^p\cdot p!} = \frac{(p^2)!}{(p!)^{p+1}}$$ such partitions excluding the two trivial partitions.

Answer 3

Number of ways to partition an $n$-set into subsets of equal size is tabulated at http://oeis.org/A038041 where there are formulas, programs, and links to the literature.

Answer 4

Well, for $p^2$ we can divide into $p^2$ classes of $1$ objects (one way) or $1$ class of $p^2$ objects (ditto) of of $p$ classes of $p$ objects.

How many ways to do the latter? Well there are ${p^2 \choose p}$ ways to choose the first class and ${p^2-p\choose p}$ ways to choose the second and so one but the order of the classes doesn't matter so there will be $\frac {\prod_{k=0}^{p-1}{p^2-kp\choose p}}{p!}$.

Example there are $\frac {{9\choose 3}{6\choose 3}}{3!} = \frac {\frac {9*8*7}6\frac {6*5*4}6}6= 280$

In general to find the number of partitions for a number $n$ you must calculate how many ways there are do a partition for each particular factoring of $n=a*b$.

So the answer would be $\sum\limits_{n = a*b}\frac {\prod\limits_{k=0}^{b-1}{n-ka \choose a}}{a!}$