2
$\begingroup$

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!

$\endgroup$
1
  • 1
    $\begingroup$ It's a big enough difference that the phrase "the only difference" is a bit suspect, but yes that is the only difference. (It's kind of like saying the only difference between $\binom{n}{k}$ and $2^k$ is that the former only counts $k$-subsets while the latter counts all subsets.) $\endgroup$ – runway44 Sep 12 '19 at 23:55
1
$\begingroup$

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*}

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much! $\endgroup$ – Bach Sep 13 '19 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.