A multinomial-type sum over compositions of an integer I find myself needing to compute (or asymptotically estimate) the following sum over the $2^{S-1}$ compositions of $S$. I am hoping an expert in combinatorics (I am a computer scientist) will recognise this summation.
Let $B_{S,k}$ denote the set of compositions that have exactly $k$ parts, and define $T_{k}$ as,
$$T_{k}=\sum_{a \in B_{S,k}}\frac{a_{1}^{a_{2}}a_{2}^{a_{3}}...a_{k-1}^{a_{k}}}{a_{1}!a_{2}!...a_{k}!},\:\: \text{with}\:\: T_{1}=1.$$ 
The sum that I am interested in is $\sum_{k}T_{k}$. 
Does an expression in terms of $S$ (either exact, or asymptotic) exist, or can it be found?
 A: $$ 1 + \frac{(n+1)^{n-1}-1}{n!}.$$
For the record, I'll mention how I found this formula. First I wrote a Maple procedure for it (about 5 Maple statements).  Then I noticed it seemed to be integer$(n)/(n-1)!$. I checked OEIS for this integer sequence and it wasn't there, so I sent the first 10 terms of this integer sequence to Superseeker and that suggested that A125598 is related.
Incidentally, this suggests that $T_1=1/n!$ would be a more natural choice, corresponding to what the formula actually gives via the convention that null products equal 1.
And here is how to prove it. Consider rooted trees with $n+1$ vertices. Define $a_1,\ldots,a_k$ to be the number of vertices at distance $1,\ldots,k$ from the root, where $k$ is the maximum distance.  The ways to choose the vertices in each level are multinomial coefficients $\binom{n+1}{1,a_1,\ldots,a_k}$, which gives you the factorials in the denominator. Each vertex at distance $i$ from the root is joined to exactly one vertex at distance $i-1$, which gives the factors $a_{i-1}^{a_i}$.  Finally, as everyone knows, there are $(n+1)^n$ rooted labelled trees on $n+1$ vertices.
