How many distinct ways are there of splitting a finite set $X$ with $|X| = n$ into $k$ disjoint subsets of sizes $n_1, n_2, \dots, n_k$ with $\sum_{i=1}^k n_i = n$?
I would think the answer should be:
$$
\prod_{i=1}^k {n – \sum_{j=1}^{i-1} n_i\choose n_i}
$$
Because this is like first picking $n_1$ elements from $X$ in any order, then $n_2$ elements from the remaining $n – n_1$ elements of $X$ and so on.
Am I correct? And can I somehow simplify my solution?
Best Answer
Just the typo that your binomial is backwards. Then $$\binom{n}{n_1}\binom{n-n_1}{n_2}\cdots \binom{n_k}{n_k}=\frac{n!}{n_1!\cdot n_2!\cdots n_{k-1}!\cdot n_k!}.$$ That you can verify yourself by the definition of binomials using factorials i.e., $\binom{n}{k}=\frac{n!}{k!\cdot (n-k)!}.$
Now, do you care about the order of the sets? Notice that doing this the sets are labeled by the index of the sizes.