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

  • $\begingroup$ 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) $\endgroup$ Jul 28, 2016 at 20:08
  • $\begingroup$ Sorry, I wrote a mistake. Now it's correct. $\endgroup$
    – user90369
    Jul 28, 2016 at 20:10
  • $\begingroup$ How do I correct the headline ? $\endgroup$
    – user90369
    Jul 28, 2016 at 20:14
  • $\begingroup$ You just edit it when you hit "edit"... $\endgroup$ Jul 28, 2016 at 20:23
  • $\begingroup$ Thank you - sometimes I cannot see the wood for the trees. :-) $\endgroup$
    – user90369
    Jul 28, 2016 at 20:28

1 Answer 1


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.

  • $\begingroup$ Very nice but hard to understand. Thank you very much for your efforts! $\endgroup$
    – user90369
    Jul 28, 2016 at 22:42
  • $\begingroup$ 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. $\endgroup$ Jul 28, 2016 at 22:47
  • $\begingroup$ 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!} \, .$$ $\endgroup$
    – Diger
    Nov 24, 2018 at 19:45
  • $\begingroup$ I guess it should have been Cayley's formula as opposed to "theorem". Also consult Lambert W function. $\endgroup$ Nov 25, 2018 at 13:31

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.