Consider the theorem
Let $A_1,\ldots,A_n$ be $n$ sets of cardinalities $N_1\ldots,N_n$, and $S:=A_1\times \ldots\times A_n$. Then $|S|=N_1\cdot \ldots \cdot N_n$.
How do I have to apply this theorem to prove the following statement:
Let $A$ be a set of size $n$. Then there are $\frac{n!}{k_{1}!\cdot\ldots\cdot k_{t}!}$ ways to partition this set into $t$ nonempty set of sizes $k_{i}$.
I have only the following proof: There are $\binom{n}{k_1}$ ways to pick the first partition, $\binom{n-k_1}{k_2}$ ways to pick the second partition, $\binom{n-k_1 - k_2}{k_3}$ ways to pick the third partition ans so on. Calculating $\binom{n}{k_1} \binom{n-k_1}{k_2} \binom{n-k_1 - k_2}{k_3}\ldots$gives the answer.
Where have we applied the above theorem in this proof ? My guess is that we actually implicitly defined in this proof $A_1$ as the set of all subsets of $A$ of size $k_1$ (so that $|A_1|=\binom{n}{k_1}$) and $A_2$ and so in a similar fashion to make use of the above theorem to get that product - but already for $A_2$ I don't know how to define it (such that $|A_2|=\binom{n-k_1}{k_2}$, since $A_2$ doesn't know which of the subset I already removed from $A$...)