I would like to find a closed formula for the Stirling numbers of the second kind $S(n,3)$ or the number of ways to partition a set of 3 elements into 3 sets. I know that $S(n,3)=3S(n-1,3)+S(n-1,2)$
Where we know $S(n,2)=2S(n-1,2)+1$
We can also see the latter recurrence leads to $S(n,2)=2^{n-1}-1$
So we get $S(n,2)=2s(n-1,2)+2^{n-1}-1$
Let $\left\{\begin{matrix}n\\k\end{matrix}\right\}$ denote the Stirling number of the second kind, i.e. the ways to partition an $n$-set into $k$ parts.
We know that $\left\{\begin{matrix}n\\k\end{matrix}\right\}=k\left\{\begin{matrix}n-1\\k\end{matrix}\right\}+ \left\{\begin{matrix}n-1\\k-1\end{matrix}\right\}$
Let $$f_k(x)=\sum\limits_{n\geqslant 0}\left\{\begin{matrix}n\\k\end{matrix}\right\}x^n$$
The recurrence gives $$f_k(x)=\frac {x}{1-kx}f_{k-1}(x)$$
Thus $$f_k(x)=x^k\prod_{j=1}^k\frac 1{1-jx}$$
Specializing for $k=3$ we get $$f_3(x)=\frac{x^3}{(1-x)(1-2x)(1-3x)}$$
Now, we have $$\tag 1 \frac{1}{{\left( {1 - x} \right)\left( {1 - 2x} \right)\left( {1 - 3x} \right)}} = \frac{1}{2}\frac{1}{{1 - x}} - \frac{4}{{1 - 2x}} + \frac{9}{2}\frac{1}{{1 - 3x}}$$
Thus, $\left\{\begin{matrix}n\\3\end{matrix}\right\}$ will be the coefficient of $n-3$ in $(1)$. Hence since $$\frac{1}{2}\frac{1}{{1 - x}} - \frac{4}{{1 - 2x}} + \frac{9}{2}\frac{1}{{1 - 3x}} = \sum\limits_{n \geqslant 0} {\left( {\frac{1}{2}\left( {{3^{n + 2}} + 1} \right) - {2^{n + 2}}} \right){x^n}} $$ we get that $\left\{\begin{matrix}n\\3\end{matrix}\right\}=0$ for $n=0,1,2$ and $$\left\{\begin{matrix}n\\3\end{matrix}\right\}=\frac{1}{2}\left( {{3^{n - 1}} + 1} \right) - {2^{n - 1}}$$ for $n\geqslant 3$.