Partition Problems and Stirling numbers of 2nd kind combinatorial proof

Question

![One identity that I was thinking might be relevant is in the 2nd picture. Just note the different restriction in the identity. ]2

Answer 1

On the left hand side you have partitions $\pi$ of $[n]=\{1,2,\cdots ,n\}$ in the way $\pi = \{B_1,\cdots , B_k\}$ where each block is non empty, so $|B_i|>0.$
Now, as a summand, on the right hand side you have the number $\binom{n}{\lambda _1,\cdots ,\lambda _k}$ which is the way to distribute $[n]$ into $k$ colors with $\lambda _i$ elements colored with color $i$. Of course the blocks on the LHS are the colors of the RHS hence you can not have $\lambda_i\leq 0.$ Also it is clear that $\cup _{i=1}^k B_i=[n]$ and hence, $\sum _{i=1}^k{\lambda _i}=n.$ The only problem on coloring is that order matters, and so you have to cancel out the order of groups of the same size and thats exactly why you are dividing by $a_1!\dots a_n!.$

Being that said, the combinatorial argument is to do a bijection from partitions to colorings and using the sum rule to get the complete sum there.
Using your identity: you can prove (using basically the same argument as before) that functions $\{f:[n]\longrightarrow [k]\}$ is like coloring but sometimes (when functions are not surjective) you do not color with all your colors(that's why $\lambda _i=0$) so you can think about Stirling numbers of the second kind in the way of surjective functions where your elements on $[k]$ are not ordered in any sense.

Answer 2

The summand $\binom{n}{\lambda_{\large 1},\cdots,\lambda_{\large k}}$ counts the number of ways to put $n$ labelled balls into $k$ labelled urns with $\lambda_1$ in the first urn, $\lambda_2$ in the second, and so on. This is because taking a permutation of $\{1,\cdots,n\}$ and stratifying it into the first $\lambda_1$ numbers, the next $\lambda_2$ numbers, and so on overcounts by a factor of $\lambda_1!\cdots\lambda_k!$, the number of ways of permuting the numbers within each block.

If we add all the summands together (over all possible $\lambda$s with $\lambda_1+\cdots+\lambda_k=n$) we count the number of ways of putting $n$ labelled balls into $k$ labelled urns, which is equivalent to functions $\{1,\cdots,n\}\to\{1,\cdots,k\}$. An alternative way to count this is with the fundamental counting principle: there are $k$ choices of which urn to put the first ball in, $k$ choices of where to put the second ball, and so on, yielding $k\times k\times\cdots\times k=k^n$. Therefore,

$$ k^n=\sum_{\lambda} \binom{n}{\lambda_1,\cdots,\lambda_k}. \tag{1}$$

Now, $\binom{n}{\lambda_1,\cdots,\lambda_k}$ overcounts the number of ways of putting $n$ labelled balls into $k$ unlabelled urns with multiplicities $\lambda_1,\cdots,\lambda_k$. By how much? By $a_1!\cdots a_k!$, corresponding to the number of ways of permuting labelled urns that have the same number of balls in them. Thus,

$$ S(n,k)=\sum_{\lambda} \binom{n}{\lambda_1,\cdots,\lambda_k}\frac{1}{a_1!\cdots a_k!}. \tag{2}$$

There is an important distinction to be made between the two sums: the first has $\lambda=(\lambda_1,\cdots,\lambda_k)$, an ordered $k$-tuple, vary over all solutions to $\lambda_1+\cdots+\lambda_k=n$, whereas the second varies over all multisets $\{\lambda_1,\cdots,\lambda_k\}$ subject to $\lambda_1+\cdots+\lambda_k=n$. So technically the original identity is incorrectly written (at least as I interpret it), because it would say $S(3,2)=\binom{3}{1,2}+\binom{3}{2,1}$ when it should just be $S(3,2)=\binom{3}{1,2}$.