Partitioning a set of cardinal $np$

Question

I wish to compute the number of possible partitions $S$ of a set of cardinal $np$ into $n$ subsets of cardinal $p$. It is easy to obtain the formula : $\displaystyle S=\sum_{k=0}^n {{pk}\choose{p}}$. However i am getting stucked here without recouring to algebra . I have in fact used generating functions to compute the sum, but i am looking for a non-algebraic argument (for example double couting ?) that could help me to compute this sum directly as i am sure there's a way to.

Answer 1

You are closed, but not quite. Just put your $n\cdot p$ objects in a line and permute them. Then divide them from left to right taking $p$ at a time and divide by the order in each group and for the order of the pairings, you will get $$\frac{(n\cdot p)!}{n!\cdot (p!)^n}$$

Answer 2

"I wish to compute the number of possible partitions S of a set of cardinal np into n subsets of cardinal p."

Hint: Stirling numbers of 2nd kind: $S(n,k)$ is the number of partitions of an $n$ element set into $k$ subsets.

"It is easy to obtain the formula : $S=\sum_{k=0}^n{np\choose p}$." Summand is independent of $k$.