Ytukyg

How can one proof the equality
$$sumlimits_{v=0}^k frac{k^v}{v!}=sumlimits_{v=0}^k frac{v^v (k-v)^{k-v}}{v!(k-v)!}$$
for $kinmathbb{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):=sumlimits_{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}$.

Recall the combinatorial class of labeled trees which is

$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{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)
quadtext{or}quad
z = T(z) exp(-T(z)).$$

By Cayley's theorem we have

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

This yields

$$T'(z) = sum_{qge 1} q^{q-1} frac{z^{q-1}}{(q-1)!}
= frac{1}{z} sum_{qge 1} q^{q-1} frac{z^{q}}{(q-1)!}
= frac{1}{z} sum_{qge 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_{qge 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 {kchoose 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_{nge 0} a_n frac{z^n}{n!}
sum_{nge 0} b_n frac{z^n}{n!}
= sum_{nge 0}
sum_{k=0}^n frac{1}{k!}frac{1}{(n-k)!} a_k b_{n-k} z^n\
= sum_{nge 0}
sum_{k=0}^n frac{n!}{k!(n-k)!} a_k b_{n-k} frac{z^n}{n!}
= sum_{nge 0}
left(sum_{k=0}^n {nchoose 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 {nchoose 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 {kchoose v} v^v (k-v)^{k-v}
= k! [z^k] frac{1}{(1-T(z))^2}.$$

To compute this introduce

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

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

$$frac{k!}{2pi i}
int_{|w|=gamma}
frac{exp((k+1)w)}{w^{k+1}} frac{1}{(1-w)^2}
(exp(-w)-wexp(-w)) ; dw
\ = frac{k!}{2pi 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.