$6S(n,3)+6S(n,2)+3S(n,1)=3^n$

Question

Find a simple proof for the following identity- $$6S(n,3)+6S(n,2)+3S(n,1)=3^n$$ where $S(n,k)$ is the Stirling numbers of second kind representing the number of partitions of $[n]$ into $k$ nonempty blocks.

By "simple proof", I think they want a combinatorial one.

From what I can understand, $3^n$ is the number of ways we can put $n$ distinct objects into $3$ distinct boxes. So, we need to show that the LHS also counts the same. Also, the $S(n,3)$ term in the LHS is the number of ways we can put $n$ distinct objects into $3$ identical boxes. But, I can't understand how to interpret the other two terms and the coefficients.

This line of thought aroused a related question-

Is it true that for all $k$, $$k^n=\sum_{i=1}^k c_iS(n,i)$$ for some suitable choice of constants $c_i$?

Answer 1

In the first term, $S(n,3)$ counts the ways to partition your set of $n$ objects into $3$ parts, to go into the $3$ boxes, and $6$ counts the ways to choose which piece goes into which box. In the second term, $S(n,2)$ counts the ways to partition your set of $n$ objects into $2$ parts, to go into $2$ of the $3$ boxes, and $6$ counts the ways to choose which piece goes into which box. In the third term, $S(n,1)$ counts the ways to partition your set of $n$ objects into $1$ part, to go into $1$ of the $3$ boxes, and $3$ counts the ways to choose which box.

Answer 2

$3^n$ is the number of functions from $[1,\ldots,n]$ to $[1,2,3]$. We may classify these functions according to the cardinality of their range:

1. $3\cdot S(n,1)$ is the number of functions whose range has $1$ element
2. $6\cdot S(n,2)$ is the number of functions whose range has $2$ elements
3. $6\cdot S(n,3)$ is the number of functions whose range has $3$ elements