1
$\begingroup$

The number of set partitions of $[n]$ with $k$ blocks is called the Stirling number of the second kind $S(n, k)$. For example, there are $15$ set partitions of $[4]$, which are $1234, 123\mathrm{-}4, 124\mathrm{-}3, 134\mathrm{-}2, 234\mathrm{-}1, 12\mathrm{-}34, 13\mathrm{-}24, 14\mathrm{-}23, 12\mathrm{-}3\mathrm{-}4, 13\mathrm{-}2\mathrm{-}4, 14\mathrm{-}2\mathrm{-}3, 23\mathrm{-}1\mathrm{-}4, 24\mathrm{-}1\mathrm{-}3, 34\mathrm{-}1\mathrm{-}2, 1\mathrm{-}2\mathrm{-}3\mathrm{-}4$.

$$S(4, 1) = 1, S(4, 2) = 7, S(4, 3) = 6, S(4, 4) = 1$$

I am confused about how to start this problem, I would appreciate a lot if someone can help.

$\endgroup$
3
$\begingroup$

Consider a set partition of $[n+1]$ into $m+1$ parts. One of the parts is $\{n+1\}\cup A$ where $A\subseteq [n]$. The remaining parts form a partition of $[n]-A$ into $m$ parts. How many partitions of $[n+1]$ into $m+1$ parts result in $|[n]-A|=k$?

$\endgroup$
2
$\begingroup$

LHS $S(n+1, m+1)$ counts the number of set partitions of $n+1$ elements into $m+1$ blocks.

RHS counts the same thing but focuses on element $n+1$. Drop element $n+1$ in block $m+1$. Note that the $(m+1)$ block can have $k$ other elements where $0 \le k \le n-m$

Choose these $k$ other elements in $\binom{n}{k}$ ways. Spread the remaining $(n+1)-(k+1)$ elements into $m$ blocks in $S(n-k, m)$ ways

So total $$=\sum_{k=0}^{n-m} S(n-k, m) \binom{n}{k} = \sum_{k=m}^{n} S(k, m) \binom{n}{k}$$

Since both LHS and RHS are counting the same thing, they are equal.

$\endgroup$

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.