# 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?

$$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.