How to use bijective proof to prove $S(n+1, m+1) = \sum\limits_{k=m}^n S(k, m) × \binom{n}{k}$

Question

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.

Answer 1

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$?

Answer 2

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.