Deriving a formula for the number of ways to partition a set

Question

I'm working on a question below:

Let $H(n,k)$ denote the number of ways to partition a set with $n$ elements into $k$ subsets of the same size. Derive a formula for $H(n,k)$.

Thanks in advance for any hints! :D

Answer 1

Ok, so you want to partition a set of n elements into k subsets. for starters we know k|n. let $m=\frac{n}{k}$

Take any permutation of the n elements. and make the first set the elements in position $1,2,...k$, the second set in the partition is made of the elements in the position $k+1,k+2...,2k$. in general make the $i$'th set the one with elements $(i-1)k+j$ for $j\in{1,2,....k}$.

let permutations $\alpha$ and $\beta$ give the same partitions in the same order. Then the only difference between them is how the elements inside the blocks are arranged, and there are $k!^m$ ways to do that

now we know there are $k!^n$ permutations that give the same blocks in the same order. Clearly if $\alpha$ and $\beta$ are distinct permutations that give the same blocks in the same order it means at least one of the blocks is ordered differently in $\beta$ than in $\alpha$, so if we arange the blocks around they will stil be distinct permutations that give the same partition. There are m! ways to permute the blocks of any given permutation.

Therefore for each partition there are $m!k!^m$ permutations that give that partition.

Clearly every permutation gives a unique partition, and there are $m!k!^m $ permutations that give the same partition, therefore the number of partitions is $$\frac{n!}{m!k!^m}$$

Answer 2

Suppose that $n=mk$, where $m\in\Bbb Z^+$. There are $\binom{n}k$ ways to choose one block of the partition. Once it’s been chosen, there are $n-k$ elements left, so there are $\binom{n-k}k$ ways to choose the next block. It’s not hard to see that in the end we’ll have

$$\binom{n}k\binom{n-k}k\binom{n-2k}k\ldots\binom{k}k=\frac{n!}{k!^m}\tag{1}$$

ways to choose a sequence of $m$ blocks to form the partition. But a partition isn’t actually an ordered sequence of blocks: it’s just a set of blocks. Thus, $(1)$ overcounts the desired number by a factor of ... what?