3
$\begingroup$

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?

$\endgroup$

1 Answer 1

5
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .