# Equality of the sums $\sum\limits_{v=0}^k \frac{k^v}{v!}$ and $\sum\limits_{v=0}^k \frac{v^v (k-v)^{k-v}}{v!(k-v)!}$

How can one proof the equality $$\sum\limits_{v=0}^k \frac{k^v}{v!}=\sum\limits_{v=0}^k \frac{v^v (k-v)^{k-v}}{v!(k-v)!}$$ for $k\in\mathbb{N}_0$?

Induction and generating functions don't seem to be useful.

The generation function of the right sum is simply $f^2(x)$ with $\displaystyle f(x):=\sum\limits_{k=0}^\infty \frac{(xk)^k}{k!}$

but for the left sum I still don't know.

It is $\displaystyle f(x)=\frac{1}{1-\ln g(x)}$ with $\ln g(x)=xg(x)$ for $\displaystyle |x|<\frac{1}{e}$.

• Try multiplying both sides by $k!$ are rewriting all of the factorials on the right as a binomial coefficient. (Not sure where that'll take you) – Simply Beautiful Art Jul 28 '16 at 20:08
• Sorry, I wrote a mistake. Now it's correct. – user90369 Jul 28 '16 at 20:10
• How do I correct the headline ? – user90369 Jul 28 '16 at 20:14
• You just edit it when you hit "edit"... – Simply Beautiful Art Jul 28 '16 at 20:23
• Thank you - sometimes I cannot see the wood for the trees. :-) – user90369 Jul 28 '16 at 20:28

Recall the combinatorial class of labeled trees which is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = \mathcal{Z}\times \textsc{SET}(\mathcal{T})$$

which immediately produces the functional equation

$$T(z) = z \exp T(z) \quad\text{or}\quad z = T(z) \exp(-T(z)).$$

By Cayley's theorem we have

$$T(z) = \sum_{q\ge 1} q^{q-1} \frac{z^q}{q!}.$$

This yields

$$T'(z) = \sum_{q\ge 1} q^{q-1} \frac{z^{q-1}}{(q-1)!} = \frac{1}{z} \sum_{q\ge 1} q^{q-1} \frac{z^{q}}{(q-1)!} = \frac{1}{z} \sum_{q\ge 1} q^{q} \frac{z^{q}}{q!}.$$

The functional equation yields

$$T'(z) = \exp T(z) + z \exp T(z) T'(z) = \frac{1}{z} T(z) + T(z) T'(z)$$

which in turn yields

$$T'(z) = \frac{1}{z} \frac{T(z)}{1-T(z)}$$

so that

$$\sum_{q\ge 1} q^{q} \frac{z^{q}}{q!} = \frac{T(z)}{1-T(z)}.$$

Now we are trying to show that

$$\sum_{v=0}^k \frac{v^v (k-v)^{k-v}}{v! (k-v)!} = \sum_{v=0}^k \frac{k^v}{v!}.$$

Multiply by $$k!$$ to get

$$\sum_{v=0}^k {k\choose v} v^v (k-v)^{k-v} = k! \sum_{v=0}^k \frac{k^v}{v!}.$$

Start by evaluating the LHS.

Observe that when we multiply two exponential generating functions of the sequences $$\{a_n\}$$ and $$\{b_n\}$$ we get that

$$A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$

i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

In the present case we have $$A(z) = B(z) = 1 + \frac{T(z)}{1-T(z)} = \frac{1}{1-T(z)}$$ by inspection.

We added the constant term to account for the fact that $$v^v=1$$ when $$v=0$$ in the convolution. We thus have

$$\sum_{v=0}^k {k\choose v} v^v (k-v)^{k-v} = k! [z^k] \frac{1}{(1-T(z))^2}.$$

To compute this introduce

$$\frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \frac{1}{(1-T(z))^2} \; dz$$

Using the functional equation we put $$z=w\exp(-w)$$ so that $$dz = (\exp(-w)-w\exp(-w)) \; dw$$ and obtain

$$\frac{k!}{2\pi i} \int_{|w|=\gamma} \frac{\exp((k+1)w)}{w^{k+1}} \frac{1}{(1-w)^2} (\exp(-w)-w\exp(-w)) \; dw \\ = \frac{k!}{2\pi i} \int_{|w|=\gamma} \frac{\exp(kw)}{w^{k+1}} \frac{1}{1-w} \; dw$$

Extracting the coefficient we get

$$k! \sum_{v=0}^k [w^v] \exp(kw) [w^{k-v}] \frac{1}{1-w} = k! \sum_{v=0}^k \frac{k^v}{v!}$$

as claimed.

Remark. This all looks very familiar but I am unable to locate the duplicate among my papers at this time.

• Very nice but hard to understand. Thank you very much for your efforts! – user90369 Jul 28 '16 at 22:42
• This is very kind. Here is a MSE link to a similar computation. Maybe it helps. These types of problems (convolutions of terms in the labeled tree function) actually appear quite frequently. – Marko Riedel Jul 28 '16 at 22:47
• It's not necessary to understand for what follows, but I'd still like to know how precisely you apply Cayleys Theorem to obtain $$T(z) = \sum_{q\ge 1} q^{q-1} \frac{z^q}{q!} \, .$$ – Diger Nov 24 '18 at 19:45
• I guess it should have been Cayley's formula as opposed to "theorem". Also consult Lambert W function. – Marko Riedel Nov 25 '18 at 13:31