How to simplify $\sum _{l=1} ^{k} \sum_{j_1 \ge 1} \cdots \sum_{j_l \ge 1, j_1 + \cdots + j_l=k} \binom{k}{j_1 \cdots j_l} \binom{-2}{l} 2^l$

Question

I'm trying to simplify the following equation.

$$\sum _{l=1} ^{k} \sum_{j_1 \ge 1} \cdots \sum_{j_l \ge 1, j_1 + \cdots + j_l=k} \binom{k}{j_1 \cdots j_l} \binom{-2}{l} 2^l$$

Or more specifically, I'm solving for the MGF whose moment is defined as follows.

$$M_k = (-1)^k \sum _{l=1} ^{k} \sum_{j_1 \ge 1} \cdots \sum_{j_l \ge 1, j_1 + \cdots + j_l=k} \binom{k}{j_1 \cdots j_l} \binom{-2}{l} 2^l$$

I'm stuck in solving it, so I need a hint for it.

Any ideas?

Answer 1

EDIT

As @MarkusScheuer has pointed out, my original answer was incorrect. I misread $j_l\ge1$ as $j_1\ge1$ in the subscript. I think it's right now.

Well to start with, $$\sum _{l=1} ^{k} \sum_{j_1 \ge 1} \cdots \sum_{j_l \ge 1, j_1 + \cdots + j_l=k} \binom{k}{j_1 \cdots j_l} \binom{-2}{l} 2^l=\\ \sum _{l=1} ^{k}\binom{-2}{l} 2^l \sum_{j_1 \ge 1} \cdots \sum_{j_l \ge 1, j_1 + \cdots + j_l=k} \binom{k}{j_1 \cdots j_l} $$ Now we know$$\sum_{ j_1 + \cdots + j_l=k} \binom{k}{j_1 \cdots j_l}=l^k,$$ but we need to exclude the cases where one or more of the summands is $0.$ If some summand is $0$ then the remaining $l-1$ summands add up to $k$, and there are $l$ ways to choose the summand to set to $0,$ so we must subtract $l(l-1)^k.$ However, the cases where two of the summands are $0$ have been subtracted twice, so we have to add back $\binom{l}{2}(l-2)^k$ and so on. By the principle of inclusion and exclusion, we get $$\sum _{l=1} ^{k}\binom{-2}{l} 2^l\sum_{j=0}^l(-1)^j\binom{l}{j}(l-j)^k $$ The inner sum can be recognized as $$ l!S(k,l)=\sum_{j=0}^l(-1)^j\binom{l}{j}(l-j)^k, $$ where $S(k,l)={k\brace l}$ is a Stirling number of the second kind, described in the wiki article on inclusion-exclusion. Fortunately, there is a recurrence relation for the Stirling numbers of the second kind, so computing them isn't so bad, at least for reasonably small $k$ and $l$.

So we have $$ \sum _{l=1} ^{k}\binom{-2}{l} 2^l l!{k \brace l} $$
Now, $$\binom{-2}{l}=\frac{(-2)(-3)\dots(-l-1)}{l!}=\frac{(-1)^l(l+1)!}{l!}=(-1)^l(l+1),$$and we arrive at$$ \sum_{l=1}^k(-2)^l(l+1)!{k \brace l},$$ where ${k\brace l}$ is the Stirling number of the second kind.

If this can be simplified further, it takes someone more knowledgeable and talented than I am.