Computing $S(n,3)$, Stirling number of 2nd kind To compute this I used the fact that $S(n,2) = 2^{n-1}-1$ and used the recurrence relation $S(n,k) = kS(n-1,k) + S(n-1,k-1)$, and used induction to get that $S(n,3)=\dfrac{3^{n-1}+1}{2}-2^{n-1}$.
But is there a quicker way to do this? Is there a way to just see plainly, as in, just counting how many ways we could put $n$ distinguishable balls into $3$ indistinguishable boxes where no box is empty? I tried but it seems difficult.
 A: With Stirling numbers of the second kind we have the combinatorial
class
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\textsc{SET}_{=k}(\textsc{SET}_{\ge 1}(\mathcal{Z})).$$
This yields the EGF
$$\frac{(\exp(z)-1)^k}{k!}.$$
Setting $k=3$ we find
$${n\brace 3} = n! [z^n] \frac{1}{6} (\exp(z)-1)^3.$$
Extracting the coefficient with $n\ge 1$ we have
$$\frac{1}{6} n! [z^n]
(\exp(3z)-3\exp(2z)+3\exp(z)-1)
\\ = \frac{1}{6} n!
\left(\frac{3^n}{n!}
- 3 \frac{2^n}{n!} + 3 \frac{1}{n!} \right)
\\ = \frac{1}{6}
(3^n - 3 \times 2^n + 3).$$
This is the claim.
A: $3^{n-1}$ counts ternary sequences of length $n-1$, symbols in $\{0,1,2\}. $ 
$(3^{n-1}+1)/2$ counts ternary sequences whose first nonzero symbol is a $1$, because half of the nonzero sequences have their first nonzero symbol equal to $1$.
To translate such a sequence into a partition, scan the sequence from left to right.


*

*If symbol $i$ is a $0$, place $i+1$ in the same part as $1$.

*For the first $i^*$ that the $(i^*)^{th}$ symbol is a $1$, place $i^*+1$ in a new part. 
For subsequent $i$ whose $i^{th}$ symbol is $1$, place $i+1$ in the same part as $i^*+1$. 

*For the first $i^{**}$ that the $(i^{**})^{th}$ symbol is a $2$, place $i^{**}+1$ in a new part. For subsequent $i$ whose $i^{th}$ symbol is $2$, place $i+1$ in the same part as $i^{**}+1$. 
However, there is a small problem. If the ternary string only consists of $0$s and $1$s, then the resulting partition will only have $2$ parts. These strings must be subtracted. 
