5
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ Very nice but hard to understand. Thank you very much for your efforts! $\endgroup$ – user90369 Jul 28 '16 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$ – Marko Riedel Jul 28 '16 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 '18 at 19:45
  • $\begingroup$ I guess it should have been Cayley's formula as opposed to "theorem". Also consult Lambert W function. $\endgroup$ – Marko Riedel Nov 25 '18 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.