Understanding the difference between the multinomial coefficients and the Stirling number of the 2nd kind

Question

I am trying to understand the difference between the multinomial coefficients and the Stirling number of the 2nd kind more clearly.

---

The multinomial coefficient $$ {r\choose k_1,k_2,...,k_l} $$ denotes the number of ways of writing the set $R$ with cardinality $r=|R|$ into ordered partitions $$ R=X_1\cup X_2\cup\cdots\cup X_l$$ with $ |X_i|=k_i\in\mathbb Z_{\ge 0} $

---

The Stirling number of the second kind $S(n,r)$ denotes the unordered partitions of $N$ with cardinality $n=|N|$ into exactly $r$ nonempty parts.

---

So it seems to me that the only difference is that we have specified the number of each component in the multinomial coefficient and empty sets are allowed. Is that correct? Thank you!

Answer 1

Lets try looking at a small example : How can we partition a $5$ element set into $3$ (non empty) parts ?

First observe that there are $2$ different "shapes"; $2+2+1$ and $3+1+1$. The multinomial coefficient for the first one gives \begin{eqnarray*} \binom{5}{2,2,1}=30. \end{eqnarray*} That is to say there are $30$ ways to split a $5$ element set into a $2$ set, another $2$ set (considered in that order) and a singleton. Of course we are not worried about the order of the parts, so we need to divide by $2$. So there are $15$ ways to split a $5$ set into $2+2+1$ parts.

Similarly $3+1+1$ gives $10$ ways. Now add these to give $S(5,3)=25$.

More generally \begin{eqnarray*} S(n,k) =\sum \prod_{i=1}^{n} \frac{1}{a_i !} \binom{n}{1^{a_1} 2^{a_2} \cdots n^{a_n}} \end{eqnarray*} where the sum is over partitions of $n$ into $k$ parts, i.e. \begin{eqnarray*} \sum_{i=1}^{n} i a_i =n \\ \sum_{i=1}^{n} a_i =k. \\ \end{eqnarray*}