> [!NOTE] Theorem > Let $A$ be a [[Finite Set|finite set]] with [[Cardinality|cardinality]] $n\in \mathbb{N}^{+}.$ Let $r\in \mathbb{N}$ with $r\leq n.$ Then the number of [[Partition of a Set|partitions]] of $A$ into $k$ subsets $A_{1},A_{2},\dots, A_{r}$ such that $|A_{1}|=k_{1},|A_{2}|=k_{2},\dots,A_{k}=k_{r}$ is given by $\frac{n!}{k_{1}!k_{2}!\dots k_{r}!}$where $n!$ denotes the $n$th [[Factorial|factorial]]. **Proof**: Note $k_{1},k_{2},\dots,k_{r}>0$ since $A_{i}$ is non-empty for $i=1,2,\dots,r.$ Also by [[Cardinality of Union of Disjoint Sets]], $k_{1}+k_{2}+\dots+k_{r}=n.$ Every partition of $A$ satisfying the assumptions can be uniquely determined via the following steps: 1. Choose $A_{1} \subset A$ such that $|A_{1}|=k_{1}.$ There are ${n \choose k}$ choices for this step by [[Number of k-Combinations of n Letters]]. 2. Choose $A_{2} \subset A$ such that $|A_{2}|=k_{2}$ and $A_{1} \cap A_{2}= \emptyset$ which implies that $A_{2} \subset A\setminus A_{1}.$ There are ${n-k_{1} \choose k_{2}}$ choices for this step. 3. Choose $A_{3} \subset A\setminus(A_{1} \cup A_{2})$ such that $|A_{3}|=k_{3}.$ There are ${n-k_{1}-k_{2} \choose k_{3}}$ choices for this step. $\vdots$ 4. Finally, choose the remaining set $A_{r}\setminus (A_{1} \cup A_{2} \cup \dots \cup A_{r-1}).$ There are ${n-(k_{1}+k_{2}+\dots k_{r-1}) \choose k_{r} }$ choices for this step. Thus by [[Product Rule for Counting (Fundamental Counting Principle)]], the number of partitions of $A$ into $r$ subsets $\{ A_{1},A_{2},\dots,A_{r} \}$ with $|A_{1}|=k_{1},\dots,|A_{r}|=k_{r}$ with $k_{1}+k_{2}+\dots+k_{r}=n$ is $\begin{align} &{n \choose k_{1}}{n-k_{1} \choose k_{2}}\dots{n - (k_{1}+k_{2}+\dots+k_{r-1}) \choose k} \\ &= \frac{n!}{k_{1}!(n-k_{1})!} \frac{(n-k_{1})!}{k_{2}!(n-k_{1}-k_{2})!} \dots \frac{(n-(k_{1}+k_{2}+\dots k_{r-1}))!}{k_{r}!(k_{1}!k_{2}!\dots k_{r}!)} \\ &= \frac{n!}{k_{1}!k_{2}!\cdots k_{r}!} \end{align}$where the last equality comes by the cancellation of the fractions and noticing that $(n-(k_{1}+k_{2}+\dots+k_{r}))! =(n-n)! = 0! = 1.$ # Applications See [[Number of Partitions of Multiset]].