Putnam 1967 A2

Define $S_0$ to be $1.$ For $n \geq 1$ , let $S_n$ be the number of $n\times n$ matrices whose elements are nonnegative integers with the property that $a_{ij}=a_{ji}$ (for $i,j=1,2,\ldots, n$ ) and where $\sum_{i=1}^{n} a_{ij}=1$ (for $j=1,2,\ldots, n$ ). Prove that a) $S_{n+1}=S_{n} +nS_{n-1}.$ b) $\sum_{n=0}^{\infty} S_{n} \frac{x^{n}}{n!} =\exp \left(x+\frac{x^{2}}{2}\right).$