Prove $6\begin{Bmatrix} n\\ 3 \end{Bmatrix}+6\begin{Bmatrix} n\\ 2 \end{Bmatrix}+ 3\begin{Bmatrix} n\\ 1 \end{Bmatrix}=3^n$

Question

Prove $6\begin{Bmatrix} n\\ 3 \end{Bmatrix}+6\begin{Bmatrix} n\\ 2 \end{Bmatrix}+ 3\begin{Bmatrix} n\\ 1 \end{Bmatrix}=3^n$

I need a combinatorial proof of this identity. The right hand side must be a sequence of length $n$ but I dont know how to link that to the left side? Note: $\begin{Bmatrix} n\\ k \end{Bmatrix}$ is the Stirling number of the second kind meaning it is the number of ways to partition $[n]$ into $k$ subsets.

Answer 1

The three terms from left to right represent the number of ways to partition $n$ distinct items into $3$ distinct subsets, of which $3,2,1$ are non-empty respectively. The Stirling number counts the number of partitions into $3,2,1$ non-empty subsets and the $6$ or $3$ counts the number of distinct ways to permute the subsets. (For $1$ non-empty subset, the two empty subsets are identical, so we divide by $2$; otherwise all $3!=6$ permutations are distinct.)

The sum of these three terms is the number of ways to partition $n$ items into $3$ subsets without restrictions, which is equal to the RHS of $3^n$.

Answer 2

Putting Parcly's answer differently: To choose a function $[n]\to[3]$, we first choose the size $k$ of its range, then partition the inputs into $k$ nonempty groups, then assign a distinct value to each group.