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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.