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 multinomial-type sum over compositions of an integer
$$ 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](http://oeis.org) for this integer sequence and it wasn't there, so I sent the first 10 terms of this integer sequence to [Superseeker](https://oeis.org/ol.html) 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.


